Cycle (graph theory)

Cyclic graph with circle (b, c, d, e, b)

In graph theory, a cycle is a path in a graph in which the start and end nodes are the same. A cyclic graph is a graph with at least one cycle. Cycles in a graph can be found algorithmically through modified depth-first search , e.g. through modified topological sorting .

Definitions

cycle

If a graph , then a path is called with for cycle if ${\displaystyle G=(V,E)}$ ${\displaystyle (v_{1},\ldots ,v_{n})}$ ${\displaystyle v_{i}\in V}$ ${\displaystyle i=1,\ldots ,n}$

${\displaystyle v_{1}=v_{n}}$

applies. In one cycle, the start and end nodes of the route must match. A cycle in a directed graph is called a directed cycle and in an undirected graph is called an undirected cycle .

circle

Correspondingly, a cycle in a graph is called a circle if there is a path . A circle is thus a cycle in which only the start and end nodes are the same, so it also applies ${\displaystyle (v_{1},\ldots ,v_{n})}$ ${\displaystyle (v_{1},\ldots ,v_{n-1})}$

${\displaystyle v_{i}\neq v_{j}}$

for with . A circle in a directed graph is called a directed circle and in an undirected graph an undirected circle . An edge that connects two nodes of a circle but is not itself part of the circle is called the chord of the circle. ${\displaystyle i,j\in \{1,\ldots ,n-1\}}$ ${\displaystyle i\neq j}$

length

In graphs without edge weights is the length of a cycle or circle . The number of associated edges is thus clearly counted . In an edge-weighted graph, the length of a cycle or circle is the sum of the edge weights of all associated edges. ${\displaystyle n-1}$ ${\displaystyle (v_{1},\ldots ,v_{n})}$

Special graphs

Cyclic graph

A graph with at least one cycle is called cyclic . Graphs without cycles are called acyclic or forest . A cycle or circle is called trivial if it contains fewer than three nodes. Trivial circles or cycles are usually not considered when analyzing graphs. A circle that contains exactly three nodes is called a triangle . A graph without a triangle is then called triangle-free . The waist size of a graph is the length of a shortest non-trivial circle. If the graph does not have a circle, the waist size is set to infinity. The simplest cyclic graphs are the circular graphs .

Panzercyclic graph

A graph is called edge pancyclic if every edge lies on a circle of length for all . A graph is called node-pancyclic if each node lies on a circle of length for all . A graph is called pan-cyclic if it has a circle of length for all . Edge pancyclic graphs are thus also pancyclic node and pancyclic node pancyclic graphs. Panzercyclic graphs are in particular Hamiltonian . ${\displaystyle p}$ ${\displaystyle p\in \{1,2,\ldots ,|V(G)|\}}$ ${\displaystyle p}$ ${\displaystyle p\in \{1,2,\ldots ,|V(G)|\}}$ ${\displaystyle p\in \{3,4,\ldots ,|V(G)|\}}$ ${\displaystyle p}$

Cycle space

For any given numbering of the edges , an element is called the incidence vector for the edge set , if ${\displaystyle A=\{a_{1},a_{2},\ldots ,a_{m}\}}$ ${\displaystyle x=(x_{i})\in \mathbb {R} ^{m}}$ ${\displaystyle M}$

${\displaystyle x_{i}={\begin{cases}0&{\mbox{, falls }}a_{i}\notin M\land {a_{i}}^{-1}\notin M\\1&{\mbox{, falls }}a_{i}\in M\\-1&{\mbox{, falls }}{a_{i}}^{-1}\in M\\\end{cases}}}$

applies. If the edges also have a non-negative weight, the entries in the vector are multiplied by this weight. The set of all circles described in this way form the cycle space , a subspace of the . The fundamental circles are a basis of the cycle space . Each fundamental circle is created by adding an edge to a spanning tree . ${\displaystyle \mathbb {F} _{2}^{m}}$

The cocycle space is the vector space of all incidence vectors generated by cuts. It is also a subspace of the and, in direct sum with the cycle space, gives the whole space. The fundamental cuts are a basis of the cocyclic space . Every fundamental cut is created by leaving out an edge of a spanning tree as a connected component . ${\displaystyle \mathbb {F} _{2}^{m}}$

Cycle detection using depth first search

Für jeden Knoten v: visited(v) = false, finished(v) = false
Für jeden Knoten v:
  DFS(v)

DFS(v):
  if finished(v)
    return
  if visited(v)
    "Zyklus gefunden" und Abbruch
  visited(v) = true
  für jeden Nachfolger w
    DFS(w)
  finished(v) = true

Successor means for both directed and undirected graphs all nodes connected to v, except for the one that called DFS (v). This prevents the algorithm from also capturing the trivial cycles, which is always the case in any undirected graph with a non-empty set of edges.

literature

• R. Diestel: Graph theory. 3. Edition. Springer, Heidelberg 2005. ISBN 3-540-67656-2