Cycle (graph theory)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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. Cycle (graph theory)_sentence_0

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. Cycle (graph theory)_sentence_1

A graph without cycles is called an acyclic graph. Cycle (graph theory)_sentence_2

A directed graph without directed cycles is called a directed acyclic graph. Cycle (graph theory)_sentence_3

A connected graph without cycles is called a tree. Cycle (graph theory)_sentence_4

Definitions Cycle (graph theory)_section_0

Circuit, cycle Cycle (graph theory)_section_1

Cycle (graph theory)_unordered_list_0

  • A circuit is a non-empty trail in which the first vertex is equal to the last vertex (closed trail).Cycle (graph theory)_item_0_0

Cycle (graph theory)_description_list_1

  • Let G = (V, E, ϕ) be a graph. A circuit is a non-empty trail (e1, e2, …, en) with a vertex sequence (v1, v2, …, vn, v1).Cycle (graph theory)_item_1_1

Cycle (graph theory)_unordered_list_2

  • A cycle or simple circuit is a circuit in which the only repeated vertex is the first/last vertex.Cycle (graph theory)_item_2_2
  • The length of a circuit or cycle is the number of edges involved.Cycle (graph theory)_item_2_3

Directed circuit, cycle Cycle (graph theory)_section_2

Cycle (graph theory)_unordered_list_3

  • A directed circuit is a non-empty directed trail in which the first vertex is equal to the last vertex.Cycle (graph theory)_item_3_4

Cycle (graph theory)_description_list_4

  • Let G = (V, E, ϕ) be a directed graph. A directed circuit is a non-empty directed trail (e1, e2, …, en) with a vertex sequence (v1, v2, …, vn, v1).Cycle (graph theory)_item_4_5

Cycle (graph theory)_unordered_list_5

  • A directed cycle or simple directed circuit is a directed circuit in which the only repeated vertex is the first/last vertex.Cycle (graph theory)_item_5_6

Chordless cycles Cycle (graph theory)_section_3

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. Cycle (graph theory)_sentence_5

An antihole is the complement of a graph hole. Cycle (graph theory)_sentence_6

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. Cycle (graph theory)_sentence_7

A chordal graph, a special type of perfect graph, has no holes of any size greater than three. Cycle (graph theory)_sentence_8

The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cycle (graph theory)_sentence_9

Cages are defined as the smallest regular graphs with given combinations of degree and girth. Cycle (graph theory)_sentence_10

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. Cycle (graph theory)_sentence_11

In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle. Cycle (graph theory)_sentence_12

Cycle space Cycle (graph theory)_section_4

The term cycle may also refer to an element of the cycle space of a graph. Cycle (graph theory)_sentence_13

There are many cycle spaces, one for each coefficient field or ring. Cycle (graph theory)_sentence_14

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. Cycle (graph theory)_sentence_15

By Veblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. Cycle (graph theory)_sentence_16

A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space. Cycle (graph theory)_sentence_17

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. Cycle (graph theory)_sentence_18

Cycle detection Cycle (graph theory)_section_5

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).All the back edges which DFS skips over are part of cycles. Cycle (graph theory)_sentence_19

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. Cycle (graph theory)_sentence_20

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. Cycle (graph theory)_sentence_21

Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Cycle (graph theory)_sentence_22

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. Cycle (graph theory)_sentence_23

For directed graphs, distributed message based algorithms can be used. Cycle (graph theory)_sentence_24

These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Cycle (graph theory)_sentence_25

Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer). Cycle (graph theory)_sentence_26

Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems. Cycle (graph theory)_sentence_27

Covering graphs by cycles Cycle (graph theory)_section_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. Cycle (graph theory)_sentence_28

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. Cycle (graph theory)_sentence_29

In either case, the resulting walk is known as an Euler cycle or Euler tour. Cycle (graph theory)_sentence_30

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. Cycle (graph theory)_sentence_31

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. Cycle (graph theory)_sentence_32

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Cycle (graph theory)_sentence_33

Such a cycle is known as a Hamiltonian cycle, and determining whether it exists is NP-complete. Cycle (graph theory)_sentence_34

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. Cycle (graph theory)_sentence_35

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. Cycle (graph theory)_sentence_36

Proving that this is true (or finding a counterexample) remains an open problem. Cycle (graph theory)_sentence_37

Graph classes defined by cycles Cycle (graph theory)_section_7

Several important classes of graphs can be defined by or characterized by their cycles. Cycle (graph theory)_sentence_38

These include: Cycle (graph theory)_sentence_39

Cycle (graph theory)_unordered_list_6

  • Bipartite graph, a graph without odd cycles (cycles with an odd number of vertices).Cycle (graph theory)_item_6_7
  • Cactus graph, a graph in which every nontrivial biconnected component is a cycleCycle (graph theory)_item_6_8
  • Cycle graph, a graph that consists of a single cycle.Cycle (graph theory)_item_6_9
  • Chordal graph, a graph in which every induced cycle is a triangleCycle (graph theory)_item_6_10
  • Directed acyclic graph, a directed graph with no cyclesCycle (graph theory)_item_6_11
  • Line perfect graph, a graph in which every odd cycle is a triangleCycle (graph theory)_item_6_12
  • Perfect graph, a graph with no induced cycles or their complements of odd length greater than threeCycle (graph theory)_item_6_13
  • Pseudoforest, a graph in which each connected component has at most one cycleCycle (graph theory)_item_6_14
  • Strangulated graph, a graph in which every peripheral cycle is a triangleCycle (graph theory)_item_6_15
  • Strongly connected graph, a directed graph in which every edge is part of a cycleCycle (graph theory)_item_6_16
  • Triangle-free graph, a graph without three-vertex cyclesCycle (graph theory)_item_6_17

See also Cycle (graph theory)_section_8

Cycle (graph theory)_unordered_list_7

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: (graph theory).