Directedundirected

Directedundirected, commonly called a mixed graph, is a graph that contains both directed edges (arcs) and undirected edges between vertices. Formally, a mixed graph G can be described as G = (V, D, U) where V is a set of vertices, D ⊆ V × V is the set of directed edges, and U ⊆ {{u, v} | u, v ∈ V, u ≠ v} is the set of undirected edges. Each undirected edge connects its two endpoints without a specified direction, while each directed edge has a specified tail and head.

In a mixed graph, local measures generalize those of directed and undirected graphs. For a vertex v, the outdegree is the number of directed edges leaving v, the indegree is the number of directed edges entering v, and the undirected degree is the number of undirected edges incident to v. A walk or path can traverse directed edges in their specified direction and undirected edges in either direction.

Connectivity concepts extend to mixed graphs with appropriate interpretations. Reachability follows the direction of directed edges and treats undirected edges as bidirectional. The notion of strong connectivity can be adapted to require a directed-path route between vertices that respects arc directions, possibly using undirected edges to bridge gaps. Mixed graphs may contain directed cycles, undirected cycles, or mixed cycles.

Algorithms on mixed graphs often adapt standard techniques. Shortest-path algorithms can treat undirected edges as bidirectional with the same weight, or replace each undirected edge by two opposite directed edges. Network flow problems can model undirected links by introducing reciprocal directed edges with equal capacity, enabling the use of traditional flow methods.

Applications of directedundirected graphs include road and transportation networks with one-way and two-way streets, social and information networks with asymmetric and mutual relations, and various modeling scenarios in biology and engineering where both directional and bidirectional interactions are present.