Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Cycle (graph theory)
Summary
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph 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. A connected graph without cycles is called a tree.
A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).
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).
A cycle or simple circuit is a circuit in which only the first and last vertices are equal.
A directed circuit is a non-empty directed trail in which the first and last vertices are equal (closed directed trail).
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).
A directed cycle or simple directed circuit is a directed circuit in which only the first and last vertices are equal.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.