Bidirected graph
Encyclopedia
In the mathematical
domain of graph theory
, a bidirected graph (introduced by ) 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
domain of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a bidirected graph (introduced by ) is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
; 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.