Bidirected graph

From Wikipedia, the free encyclopedia

In the mathematical domain of graph theory, a bidirected graph is a graph in which each edge is given an independent orientation (or direction, or arrow) at each end. Thus, there are three kinds of bidirected edges: those where the arrows point outward, towards the vertices, at both ends; those where both arrows point inward, away from the vertices; and those in which one arrow points away from its vertex and towards the opposite end, while the other arrow points in the same direction as the first, away from the opposite end and towards its own vertex.

Edges of these three types may be called, respectively, extraverted, introverted, and directed. The "directed" edges are the same as ordinary directed edges in a directed graph; thus, a directed graph is a special kind of bidirected graph.

It is sometimes desirable to have also edges with only one end (half-edges); these get only one arrow. An edge with no ends (a loose edge) has no arrows. The edges that are neither half nor loose edges may be called ordinary edges.

The ordinary edges of a bidirected graph are signed; thus, a bidirected graph is the same as an oriented signed graph. (Signed graph theory gives some of the reasons to consider half and loose edges.) The incidence matrix of a bidirected graph is simply its incidence matrix as an oriented signed graph.