A single graph cannot simultaneously contain both directed and undirected edges under the strict definitions of directed and undirected graphs. However, a special type of structure known as a mixed graph allows both types of edges to coexist. In a mixed graph, some edges have direction (as in a directed graph), while others are bidirectional (as in an undirected graph). These are not commonly used in basic graph theory but may be applied in advanced systems where different relationships exist between different nodes. For instance, in a transport system, one road might allow traffic in both directions (undirected), while another is a one-way street (directed). While this flexibility is useful, it introduces complexity in traversal and representation. Mixed graphs are not standard in many algorithms, which are typically designed for either purely directed or purely undirected graphs. Therefore, they require careful handling, often by treating the directed and undirected portions separately in algorithmic processing.

In traditional graph theory, a graph is considered either weighted or unweighted, not both. However, in practical applications, some systems may model graphs with a mixture of weighted and unweighted edges, although this is less common and generally discouraged in formal graph implementations. In such cases, unweighted edges are usually treated as having a default weight, often assumed to be 1. This approach helps maintain consistency in algorithms that rely on weights, such as Dijkstra’s algorithm or A* search. For example, in a network model, certain connections might have a specific bandwidth (weight), while others are generic and treated equally. In code or adjacency matrices, this would mean assigning explicit weights to some edges and implicit default values to others. It’s important to remember that mixing these types can lead to ambiguity in algorithm results and may require custom logic to ensure all edges are handled consistently during traversal or optimisation.

When a weighted graph contains negative edge weights, it introduces special considerations for algorithms that process paths. Negative weights can represent scenarios such as refunds, energy savings, or backtracking costs. However, not all pathfinding algorithms can handle them correctly. For example, Dijkstra’s algorithm assumes all edge weights are non-negative and will produce incorrect results if negative edges are present. In such cases, algorithms like the Bellman-Ford algorithm are used instead, as they are designed to detect and handle negative weights properly. If a graph contains a negative weight cycle (a cycle whose total weight adds up to less than zero), it means a traveller can keep looping indefinitely while reducing the path cost, which is often problematic. Bellman-Ford can also detect these cycles, allowing the system to raise an error or stop execution. In practice, designers avoid negative edge weights unless the algorithm in use explicitly supports them and the logic of the system requires them.

A self-loop is an edge that connects a node to itself. Whether or not self-loops are allowed depends on the type of graph and the context in which it is used. In undirected graphs, a self-loop is represented as a single edge from a node back to itself and is usually drawn as a small loop. It is considered to increase the degree of the node by two, since the node connects to itself at both ends of the undirected edge. In directed graphs, the self-loop is a directed edge where the source and destination are the same node. In this case, it increases the node’s in-degree and out-degree by one each. Self-loops are allowed in most graph representations unless explicitly excluded by the problem definition. In adjacency matrices, a self-loop appears at the diagonal element (i, i), and in adjacency lists, it appears as the node having itself as a neighbour. These can have valid use cases, such as representing recursive dependencies or feedback mechanisms.

A multigraph is a type of graph that allows multiple edges between the same pair of nodes. This contrasts with a standard graph, which permits at most one edge between any two vertices. In a multigraph, each edge can carry its own properties, such as a different weight or label. Multigraphs are useful in situations where multiple distinct relationships or interactions exist between the same two entities. For example, in a public transport system, multiple bus routes (edges) might connect the same two locations (nodes), each with different travel times or schedules. In adjacency list representations, multigraphs can store several entries for the same neighbouring vertex. However, standard algorithms like Dijkstra’s or BFS may need modification to handle parallel edges correctly. Multigraphs are commonly used in network modelling, transport systems, and communication networks where redundancy or multiple connection paths need to be explicitly represented. Their flexibility comes with added complexity in representation and algorithmic handling.