Bidirected Graph on:
[Wikipedia]
[Google]
[Amazon]
In the
In the mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
domain of graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a bidirected graph (introduced by ). Reprinted in ''Combinatorial Optimization — Eureka, You Shrink!'', Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27–30, .
is a graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
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.
A skew-symmetric graph
In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is graph isomorphism, isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution (math ...
is the double covering graph of a bidirected graph.
A bidirected graph may be regarded as an orientation of a signed graph
In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.
A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the no ...
, similarly to how a directed graph may be viewed as an orientation of an ordinary undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
.
Other meanings
A symmetric directed graph (that is, a directed graph in which the reverse of every edge is also an edge) is sometimes also called a "bidirected graph".See also
*Skew-symmetric graph
In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is graph isomorphism, isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution (math ...
* Signed graph
In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.
A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the no ...
References
Extensions and generalizations of graphs {{graph-stub