Cycle Detection (graph Theory)
   HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a cycle in 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 discre ...
is a non-empty
trail A trail, also known as a path or track, is an unpaved lane or small road usually passing through a natural area. In the United Kingdom and the Republic of Ireland, a path or footpath is the preferred term for a pedestrian or hiking trail. Th ...
in which only the first and last vertices are equal. A directed cycle in a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an ''acyclic graph''. A directed graph without directed cycles is called a ''
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
''. A
connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
without cycles is called a ''
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
''.


Definitions


Circuit and cycle

* A circuit is a non-empty
trail A trail, also known as a path or track, is an unpaved lane or small road usually passing through a natural area. In the United Kingdom and the Republic of Ireland, a path or footpath is the preferred term for a pedestrian or hiking trail. Th ...
in which the first and last vertices are equal (''closed trail''). : Let be a graph. A circuit is a non-empty trail with a vertex sequence . * A cycle or simple circuit is a circuit in which only the first and last vertices are equal.


Directed circuit and directed cycle

* A directed circuit is a non-empty directed trail in which the first and last vertices are equal (''closed directed trail''). : Let be a directed graph. A directed circuit is a non-empty directed trail with a vertex sequence . * A directed cycle or simple directed circuit is a directed circuit in which only the first and last vertices are equal.


Chordless cycle

A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
of a graph hole. Chordless cycles may be used to characterize
perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...
s: by the strong perfect graph theorem, a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...
, a special type of perfect graph, has no holes of any size greater than three. The
girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...
of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth. A
peripheral cycle In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygo ...
is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.


Cycle space

The term ''cycle'' may also refer to an element of the
cycle space In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs. This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...
of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the ''binary cycle space'' (usually called simply the ''cycle space''), which consists of the edge sets that have even degree at every vertex; it forms a
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
over the two-element
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
. By
Veblen's theorem In mathematics, Veblen's theorem, introduced by , states that the set of edges of a finite graph can be written as a union of disjoint simple cycles if and only if every vertex has even degree. Thus, it is closely related to the theorem of that ...
, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A
cycle basis In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be exp ...
of the graph is a set of simple cycles that forms a
basis Basis may refer to: Finance and accounting * Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting ...
of the cycle space.. Using ideas from
algebraic topology Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...
, the binary cycle space generalizes to vector spaces or
modules Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a sy ...
over other
rings Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
such as the integers, rational or real numbers, etc..


Cycle detection

The existence of a cycle in directed and undirected graphs can be determined by whether
depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
(DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only ''O''(''n'') time is required to find a cycle in an ''n''-vertex graph, since at most ''n'' − 1 edges can be tree edges. Many
topological sorting In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For ins ...
algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into
strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
s, cycles only exist within the components and not between them, since cycles are strongly connected. For directed graphs, distributed message-based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a
computer cluster A computer cluster is a set of computers that work together so that they can be viewed as a single system. Unlike grid computers, computer clusters have each node set to perform the same task, controlled and scheduled by software. The comp ...
(or supercomputer). Applications of cycle detection include the use of
wait-for graph A wait-for graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems. In computer science, a system that allows concurrent operation of multiple processes and locking of resourc ...
s to detect
deadlock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...
s in concurrent systems.


Algorithm

For every vertex v: visited(v) = false, finished(v) = false For every vertex v: DFS(v) DFS(v): if finished(v) return if visited(v) "Cycle found" and return visited(v) = true for every neighbour w DFS(w) finished(v) = true Neighbour means for both directed and undirected graphs all vertices connected to ''v'', except for the one that called ''DFS(v)''. This avoids the algorithm also catching trivial cycles, which is the case in every undirected graph with at least one edge.


Programming

The following example in the
Programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
C# shows one implementation of an undirected graph using
Adjacency list In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is ...
s. The undirected graph is declared as
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
''UndirectedGraph''. Executing the program uses the ''Main''
method Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to: *Scien ...
, which - if one exists - prints the shortest, non-trivial cycle to the console. using System; using System.Collections.Generic; // Declares the class for the vertices of the graph class Node // Declares the class for the undirected graph class UndirectedGraph class Program


Covering graphs by cycle

In his 1736 paper on the
Seven Bridges of Königsberg The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and prefigured the idea of topology. The city of Königsberg in Prussia (n ...
, widely considered to be the birth of graph theory,
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be
strongly connected In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...
and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an
Eulerian trail In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is
Veblen's theorem In mathematics, Veblen's theorem, introduced by , states that the set of edges of a finite graph can be written as a union of disjoint simple cycles if and only if every vertex has even degree. Thus, it is closely related to the theorem of that ...
. When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by solving the
route inspection problem In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undire ...
. The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a
Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
, and determining whether it exists is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is
Ore's theorem Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilto ...
that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph. The cycle double cover conjecture states that, for every
bridgeless graph In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connec ...
, there exists a
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem..


Graph classes defined by cycle

Several important classes of graphs can be defined by or characterized by their cycles. These include: *
Bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
, a graph without odd cycles (cycles with an odd number of vertices) *
Cactus graph In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ( ...
, a graph in which every nontrivial biconnected component is a cycle *
Cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
, a graph that consists of a single cycle *
Chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...
, a graph in which every induced cycle is a triangle *
Directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
, a directed graph with no directed cycles *
Line perfect graph In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected compon ...
, a graph in which every odd cycle is a triangle *
Perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...
, a graph with no induced cycles or their complements of odd length greater than three *
Pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...
, a graph in which each connected component has at most one cycle *
Strangulated graph In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph. That is, they are the graphs in which every peripheral cycle i ...
, a graph in which every peripheral cycle is a triangle *
Strongly connected graph In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
, a directed graph in which every edge is part of a cycle *
Triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
, a graph without three-vertex cycles


See also

*
Cycle space In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs. This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...
*
Cycle basis In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be exp ...
*
Cycle detection In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function that maps a finite set to itself, and any initial value in , the sequence of itera ...
in a sequence of iterated function values


References

* * {{cite book , last1=Bender , first1=Edward A. , last2=Williamson , first2=S. Gill , date=2010 , title=Lists, Decisions and Graphs. With an Introduction to Probability , url=https://books.google.com/books?id=vaXv_yhefG8C Graph theory objects