In graph theory, a **cycle** in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A **directed cycle** in a directed graph is a non-empty directed trail in which the only repeated vertices are the first and last vertices.

- Definitions
- Circuit, cycle
- Directed circuit, cycle
- Chordless cycles
- Cycle space
- Cycle detection
- Covering graphs by cycles
- Graph classes defined by cycles
- See also
- References

A graph without cycles is called an *acyclic graph*. A directed graph without directed cycles is called a * directed acyclic graph *. A connected graph without cycles is called a * tree *.

- A
**circuit**is a non-empty trail in which the first vertex is equal to the last vertex (*closed trail*).^{ [1] }

- Let
*G*= (*V*,*E*,*ϕ*) be a graph. A circuit is a non-empty trail (*e*_{1},*e*_{2}, …,*e*_{n}) with a vertex sequence (*v*_{1},*v*_{2}, …,*v*_{n},*v*_{1}).

- A
**cycle**or**simple circuit**is a circuit in which the only repeated vertex is the first/last vertex.^{ [1] } - The
**length**of a circuit or cycle is the number of edges involved.

- A
**directed circuit**is a non-empty directed trail in which the first vertex is equal to the last vertex.^{ [1] }

- Let
*G*= (*V*,*E*,*ϕ*) be a directed graph. A directed circuit is a non-empty directed trail (*e*_{1},*e*_{2}, …,*e*_{n}) with a vertex sequence (*v*_{1},*v*_{2}, …,*v*_{n},*v*_{1}).

- A
**directed cycle**or**simple directed circuit**is a directed circuit in which the only repeated vertex is the first/last vertex.^{ [1] }

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 of a graph hole. Chordless cycles may be used to characterize perfect graphs: 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, a special type of perfect graph, has no holes of any size greater than three.

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

The term *cycle* may also refer to an element of the cycle space 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 over the two-element field. By Veblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space.^{ [2] }

Using ideas from algebraic topology, the binary cycle space generalizes to vector spaces or modules over other rings such as the integers, rational or real numbers, etc.^{ [3] }

The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge).^{ [4] } All the back edges which DFS skips over are part of cycles.^{ [5] } 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 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 components, cycles only exist within the components and not between them, since cycles are strongly connected.^{ [5] }

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 (or supercomputer).

Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.^{ [6] }

In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once, 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 and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting walk is known as an Euler cycle or Euler tour. 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.^{ [7] } 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 by solving the route inspection problem.

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, and determining whether it exists is NP-complete.^{ [8] } Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem 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.^{ [9] }

The cycle double cover conjecture states that, for every bridgeless graph, there exists a multiset 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.^{ [10] }

Several important classes of graphs can be defined by or characterized by their cycles. These include:

- Bipartite graph, a graph without odd cycles (cycles with an odd number of vertices).
- Cactus graph, a graph in which every nontrivial biconnected component is a cycle
- Cycle graph, a graph that consists of a single cycle.
- Chordal graph, a graph in which every induced cycle is a triangle
- Directed acyclic graph, a directed graph with no cycles
- Line perfect graph, a graph in which every odd cycle is a triangle
- Perfect graph, a graph with no induced cycles or their complements of odd length greater than three
- Pseudoforest, a graph in which each connected component has at most one cycle
- Strangulated graph, a graph in which every peripheral cycle is a triangle
- Strongly connected graph, a directed graph in which every edge is part of a cycle
- Triangle-free graph, a graph without three-vertex cycles

- Cycle space
- Cycle basis
- Cycle detection in a sequence of iterated function values

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* which are connected by *edges*. A distinction is made between **undirected graphs**, where edges link two vertices symmetrically, and **directed graphs**, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

In graph theory, a **planar graph** is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a **plane graph** or **planar embedding of the graph**. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, a **tree** is an undirected graph in which any two vertices are connected by *exactly one* path, or equivalently a connected acyclic undirected graph. A **forest** is an undirected graph in which any two vertices are connected by *at most one* path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In graph theory, a branch of mathematics and computer science, the **Chinese postman problem**, **postman tour** or **route inspection problem** is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time.

In mathematics, particularly graph theory, and computer science, a **directed acyclic graph** is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to sociology to computation (scheduling).

In the mathematical field of graph theory, a **bipartite graph** is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the *parts* of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In the mathematical field of graph theory, a **Hamiltonian path** is a path in an undirected or directed graph that visits each vertex exactly once. A **Hamiltonian cycle** is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

In graph theory, a branch of mathematics, the (binary) **cycle space** of an undirected graph is the set of its even-degree subgraphs.

This is a **glossary of graph theory**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In mathematics, and more specifically in graph theory, a **graph** is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called *vertices* and each of the related pairs of vertices is called an *edge*. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In graph theory, an **Eulerian trail** is a trail in a finite graph that visits every edge exactly once. Similarly, an **Eulerian circuit** or **Eulerian cycle** is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In graph theory, an **edge coloring** of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The **edge-coloring problem** asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the **chromatic index** of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0.

In mathematics and computer science, **connectivity** is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In the mathematical discipline of graph theory, the **dual graph** of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a branch of mathematics, the **handshaking lemma** is the statement that every finite undirected graph has an even number of vertices with odd degree. In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands. The vertices of odd degree in a graph are sometimes called **odd nodes** or **odd vertices**; in this terminology, the handshaking lemma can be restated as the statement that every graph has an even number of odd nodes.

In graph theory, a **pseudoforest** is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A **pseudotree** is a connected pseudoforest.

In mathematics, **Veblen's theorem**, introduced by Oswald Veblen (1912), 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 Euler (1736) that a finite graph has an Euler tour if and only if it is connected and every vertex has even degree. Indeed, a representation of a graph as a union of simple cycles may be obtained from an Euler tour by repeatedly splitting the tour into smaller cycles whenever there is a repeated vertex. However, Veblen's theorem applies also to disconnected graphs, and can be generalized to infinite graphs in which every vertex has finite degree.

In graph theory, an **orientation** of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

In graph theory, the **Gallai–Hasse–Roy–Vitaver theorem** is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph *G* equals one plus the length of a longest path in an orientation of *G* chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

- 1 2 3 4 Bender & Williamson 2010, p. 164.
- ↑ Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces",
*Graph Theory and Its Applications*(2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054 . - ↑ Diestel, Reinhard (2012), "1.9 Some linear algebra",
*Graph Theory*, Graduate Texts in Mathematics,**173**, Springer, pp. 23–28. - ↑ Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings".
*Applied Combinatorics*(5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6. - 1 2 Sedgewick, Robert (1983), "Graph algorithms",
*Algorithms*, Addison–Wesley, ISBN 0-201-06672-6 - ↑ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003).
*Operating System Concepts*. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0. - ↑ Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs",
*Annals of Mathematics*, Second Series,**14**(1): 86–94, doi:10.2307/1967604, JSTOR 1967604 . - ↑ Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller and J. W. Thatcher (ed.),
*Complexity of Computer Computations*, New York: Plenum, pp. 85–103. - ↑ Ore, Ø. (1960), "Note on Hamilton circuits",
*American Mathematical Monthly*,**67**(1): 55, doi:10.2307/2308928, JSTOR 2308928 . - ↑ Jaeger, F. (1985), "A survey of the cycle double cover conjecture",
*Annals of Discrete Mathematics 27 – Cycles in Graphs*, North-Holland Mathematics Studies,**27**, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1 ..

- Balakrishnan, V. K. (2005).
*Schaum's outline of theory and problems of graph theory*([Nachdr.] ed.). McGraw–Hill. ISBN 978-0070054899. - Bender, Edward A.; Williamson, S. Gill (2010).
*Lists, Decisions and Graphs. With an Introduction to Probability*.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.