# Cycle (graph theory)

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

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

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.

### 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.

## 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 .

## Cycle space

For any given numbering of the edges , an element is called the **incidence vector** for the edge set , if

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 .

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 .

## 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