圈（图论）

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

此词条暂由彩云小译翻译，翻译字数共2107，未经人工整理和审校，带来阅读不便，请见谅。

A graph with edges colored to illustrate a closed walk H–A–B–A–H in green, a circuit which is a closed walk in which all edges are distinct B–D–E–F–D–C–B in blue, and a cycle which is a closed walk in which all vertices are distinct but the first and last vertices H–D–G–H in red.

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.

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

没有圈的图称为无圈图。没有有向圈的有向图称为有向无环图图。没有圈的连通图称为树。

Definitions

Circuit and cycle

  • A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).模板:Sfn
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.模板:Sfn
  • A circuit is a non-empty trail 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).模板:Sfn
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.模板:Sfn
  • 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

文件:Graph with Chordless and Chorded Cycles.svg
In this graph the green cycle A–B–C–D–E–F–A is chordless whereas the red cycle G–H–I–J–K–L–G is not. This is because the edge {K, I} is a chord.

thumb|right|In this graph the green cycle A–B–C–D–E–F–A is chordless whereas the red cycle G–H–I–J–K–L–G is not. This is because the edge {K, I} is a chord.

= = 无弦循环 = = 拇指 | 右 | 在这个图中，绿色循环 A-B-C-D-E-F-A 是无弦的，而红色循环 G-H-I-J-K-L-G 不是。这是因为边{ K，I }是和弦。

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.

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.

图中的无弦循环，也称为空洞或诱导循环，是这样一种循环，即循环的两个顶点之间没有一个边连接，而这个边本身又不属于循环。反孔是图孔的补充。无弦圈可以用来刻画完美图的特征: 根据完美图问题，一个图是完美的当且仅当它的孔或反孔中没有一个顶点的数目大于3的奇数。弦图是一种特殊类型的完全图，没有大于三的孔。

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.

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.

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.

周边循环是图中的一个循环，它的性质是每两个不在循环上的边可以通过一条路径连接，而路径的内部顶点可以避开该循环。在一个图中，如果一个图不是通过向一个循环添加一条边而形成的，那么一个周边循环必须是一个诱导循环。

Cycle space

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.[1]

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

周期空间这个术语也可以指图的周期空间的一个元素。有许多循环空间，每个系数域或环都有一个循环空间。最常见的是二进制循环空间(通常简称为循环空间) ，它由在每个顶点具有偶数度的边集合组成; 它在两个元素域上形成向量空间。根据 Veblen 定理，循环空间中的每个元素都可以形成简单循环的边不交并。图的循环基是一组简单的循环，构成循环空间的基础。

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

利用代数拓扑的思想，二进制循环空间推广到向量空间或其他环上的模，如整数、有理数或实数等。.

Cycle detection

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).[3] All the back edges which DFS skips over are part of cycles.[4] 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.

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

循环检测在有向和无向图中循环的存在可以通过深度优先搜索(dFS)是否找到一个指向当前顶点祖先的边(它包含一个后边)来确定。DFS 跳过的所有后边都是循环的一部分。在无向图中，到节点父节点的边不应该算作后边，但是找到任何其他已经访问过的顶点将表示后边。在无向图的情况下，只需要 O (n)时间就可以在 n 个顶点图中找到一个圈，因为最多 n-1个边可以是树的边。

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.[4]

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.

许多拓扑排序算法也会检测到周期，因为这些是拓扑有序存在的障碍。此外，如果有向图被划分为强连通分量，圈只存在于分量之内，而不存在于分量之间，因为圈是强连通的。

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

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.[5]

Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.

循环检测的应用包括使用等待图来检测并发系统中的死锁。

Algorithm

For every vertex v: visited(v) = false, finished(v) = false
For every vertex v:
  DFS(v)

For every vertex v: visited(v) = false, finished(v) = false
For every vertex v:
  DFS(v)

= = 算法 = = 对于每个顶点 v: 访问(v) = false，完成(v) = false 对于每个顶点 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

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

DFS (v) : 如果完成(v)返回如果访问(v)“循环发现”和返回访问(v) = 真对于每个邻居 w DFS (w)完成(v) = 真

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.

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.

对于有向图和无向图，邻域意味着所有连接到 v 的顶点，除了一个叫做 DFS (v)的顶点。这避免了算法也捕获平凡的循环，这是每个无向图至少有一个边的情况。

Programming

The following example in the Programming language C# shows one implementation of an undirected graph using Adjacency lists. The undirected graph is declared as class UndirectedGraph. Executing the program uses the Main method, which - if one exists - prints the shortest, non-trivial cycle to the console.[6]

using System;
using System.Collections.Generic;

The following example in the Programming language C# shows one implementation of an undirected graph using Adjacency lists. The undirected graph is declared as class UndirectedGraph. Executing the program uses the Main method, which - if one exists - prints the shortest, non-trivial cycle to the console.GeeksforGeeks: Shortest cycle in an undirected unweighted graph<syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;

下面的例子在编程语言 C # 中显示了一个使用邻接列表的无向图的实现。无向图被声明为类 UndirectedGraph。执行程序使用 Main 方法，如果存在的话，它会将最短的非平凡周期打印到控制台。GeeksforGeeks: 无向无权图中的最短循环使用 System; using System。收款。一般;

// Declares the class for the vertices of the graph
class Node
{
	public int index;
	public string value;
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices
}

// Declares the class for the vertices of the graph
class Node
{
	public int index;
	public string value;
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices
}

//声明图形类 Node { public int index; public string value; public HashSet < Node > adjacentNodes = new HashSet < Node > () ;//Set of  邻点}的顶点类

// Declares the class for the undirected graph
class UndirectedGraph
{
	public HashSet<Node> nodes = new HashSet<Node>();
	
	// This method connects node1 and node2 with each other
	public void ConnectNodes(Node node1, Node node2)
	{
		node1.adjacentNodes.Add(node2);
		node2.adjacentNodes.Add(node1);
	}
}

// Declares the class for the undirected graph
class UndirectedGraph
{
	public HashSet<Node> nodes = new HashSet<Node>();
	
	// This method connects node1 and node2 with each other
	public void ConnectNodes(Node node1, Node node2)
	{
		node1.adjacentNodes.Add(node2);
		node2.adjacentNodes.Add(node1);
	}
}

//声明无向图类 UndirectedGraph { public HashSet < Node > Node = new HashSet < Node > () ;//此方法将 node1和 node2连接到彼此的公共空白 ConnectNodes (Node node1，Node node2){ node1.adjacentNodes。添加(node2) ; node2.adjacentNodes。添加(node1) ; }

class Program
{
	// This method returns the cycle in the form A, B, C, ... as text.
	public static string ToString(List<Node> cycle)
	{
		string text = "";
		for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices
		{
			text += cycle[i].value + ", ";
		}
		text = text.Substring(0, text.Length - 2);
		return text;
	}
	
	// Main method executing the program
	public static void Main(string[] args)
	{
		// Declares and initialises 5 vertices
		Node node1 = new Node{index = 0, value = "A"};
		Node node2 = new Node{index = 1, value = "B"};
		Node node3 = new Node{index = 2, value = "C"};
		Node node4 = new Node{index = 3, value = "D"};
		// Declares and initialises an array holding the vertices
		Node[] nodes = {node1, node2, node3, node4};
		// Creates an undirected graph
		UndirectedGraph undirectedGraph = new UndirectedGraph();
		int numberOfNodes = nodes.Length;
		for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
		{
			undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
		}
		// Connects the vertices of the graph with each other
		undirectedGraph.ConnectNodes(node1, node1);
		undirectedGraph.ConnectNodes(node1, node2);
		undirectedGraph.ConnectNodes(node2, node3);
		undirectedGraph.ConnectNodes(node3, node1);
		undirectedGraph.ConnectNodes(node3, node4);
		undirectedGraph.ConnectNodes(node4, node1);
		
		HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
		HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
		for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
		{
			Node node = nodes[i];
			newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
			List<Node> path = new List<Node>();
			path.Add(node);
			paths.Add(path); // Adds a path for each node as a starting vertex
		}
		HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
		int lengthOfCycles = 0; // Length of shortest cycles
		bool cyclesAreFound = false; // Whether or not cycles were found at all
		while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate
		{
			newNodes.Clear(); // Empties the set of nodes to iterate
			HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths
			foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
			{
				Node lastNode = path[path.Count - 1];
				newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate
				foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
				{
					if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
					{
						cyclesAreFound = true;
						shortestCycles.Add(path); // Adds the path to the set of cycles
						lengthOfCycles = path.Count;
					}
					if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour
					{
						newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate
						// Creates a new path
						List<Node> newPath = new List<Node>();
						newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order
						newPath.Add(nextNode); // Adds the neighbour to the new path
						newPaths.Add(newPath); // Adds the path to the set of newly found paths
					}
				}
			}
			paths = newPaths; // Updates the set of current paths
		}
		if (shortestCycles.Count > 0) // If cycles were found
		{
			Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
			foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles
			{
				Console.WriteLine(ToString(cycle)); // Print to console
			}
		}
		else
		{
			Console.WriteLine("The graph contains no cycles."); // Print to console
		}
		
		Console.ReadLine();
	}
}

class Program { // This method returns the cycle in the form A, B, C, ... as text. public static string ToString(List<Node> cycle) { string text = ""; for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices { text += cycle[i].value + ", "; } text = text.Substring(0, text.Length - 2); return text; }

// Main method executing the program public static void Main(string[] args) { // Declares and initialises 5 vertices Node node1 = new Node{index = 0, value = "A"}; Node node2 = new Node{index = 1, value = "B"}; Node node3 = new Node{index = 2, value = "C"}; Node node4 = new Node{index = 3, value = "D"}; // Declares and initialises an array holding the vertices Node[] nodes = {node1, node2, node3, node4}; // Creates an undirected graph UndirectedGraph undirectedGraph = new UndirectedGraph(); int numberOfNodes = nodes.Length; for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices { undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph } // Connects the vertices of the graph with each other undirectedGraph.ConnectNodes(node1, node1); undirectedGraph.ConnectNodes(node1, node2); undirectedGraph.ConnectNodes(node2, node3); undirectedGraph.ConnectNodes(node3, node1); undirectedGraph.ConnectNodes(node3, node4); undirectedGraph.ConnectNodes(node4, node1);

HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph { Node node = nodes[i]; newNodes.Add(node); // Add the vertex to the set of new vertices to iterate List<Node> path = new List<Node>(); path.Add(node); paths.Add(path); // Adds a path for each node as a starting vertex } HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles int lengthOfCycles = 0; // Length of shortest cycles bool cyclesAreFound = false; // Whether or not cycles were found at all while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate { newNodes.Clear(); // Empties the set of nodes to iterate HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths foreach (List<Node> path in paths) // foreach-loop, iterating all current paths { Node lastNode = path[path.Count - 1]; newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node { if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found { cyclesAreFound = true; shortestCycles.Add(path); // Adds the path to the set of cycles lengthOfCycles = path.Count; } if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour { newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate // Creates a new path List<Node> newPath = new List<Node>(); newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order newPath.Add(nextNode); // Adds the neighbour to the new path newPaths.Add(newPath); // Adds the path to the set of newly found paths } } } paths = newPaths; // Updates the set of current paths } if (shortestCycles.Count > 0) // If cycles were found { Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles { Console.WriteLine(ToString(cycle)); // Print to console } } else { Console.WriteLine("The graph contains no cycles."); // Print to console }

Console.ReadLine(); } } </syntaxhighlight>

Class Program {//此方法以文本形式返回形式为 A、 B、 C、 ... 的循环。Public static string ToString (List < Node > Cycle){ string text = “”; for (int i = 0; i < cle。计数; i + +)//for-loop，迭代顶点{ text + = cle [ i ]。Value + “ ,”; } text = text。子串(0，文本。{//声明并初始化5个顶点 Node node1 = new Node { index = 0，value = “ A”} ; Node node2 = new Node { index = 1，value = “ B”}{ index = 1，value = “ B”} ;Node node3 = new Node { index = 2，value = “ C”} ; Node node4 = new Node { index = 3，value = “ D”} ;//声明并初始化一个包含顶点的数组 Node [] Node = { node1，node2，node3，node4} ;//创建一个无向图 UndirectedGraph undirectedGraph = new UndirectedGraph () ; int numberOfNodes = 节点。长度; for (int i = 0; i < numberOfNodes; i + +)//for-loop，迭代所有顶点{ undirectedGraph.node。Add (node [ i ]) ;//将顶点添加到图}//将图的顶点彼此连接起来 undirectedGraph。ConnectNodes (node1，node1) ; undirectedGraph.ConnectNodes (node1，node2) ; undirectedGraph.ConnectNodes (node2，node3) ; undirectedGraph.ConnectNodes (node3，node1) ; undirectedGraph.ConnectNodes (node3，node4) ; undirectedGraph.ConnectNodes (node4，node1) ; HashSet < Node > newNodes = new HashSet < Node > (Node) ;//Set of new vertices to iterate HashSet < List < Node > > path = new HashSet < List < Node > > () ;//Set of current path for (int i = 0; i < numberOfNodes; i + +)//for-loop，迭代图的所有顶点{ Node Node = Node [ i ] ; newNodes。Add (node) ;//将顶点添加到新顶点集合中，以迭代 List < Node > path = new List < Node > () ; path。添加(节点) ; 路径。添加(路径) ;//为每个节点添加一个路径作为起始顶点} HashSet < List < Node > > short estCycles = new HashSet < List < Node > > () ;//Set of short Cycle int Length thOfCycles = 0;//Llength of short Cycle bool cyesArefound = false;//是否在任何时候都找到了循环(！发现及更新节点。Count > 0)//只要我们还有可以迭代的顶点{ newNodes。//清空节点集以迭代 HashSet < List < Node > > newPath = new HashSet < List < Node > > () ;//设置新发现的 foreach 路径(List < Node > path in path)//foreach-loop，迭代所有当前路径{ Node lastNode = path [ path ]。新节点。Add (lastNode) ;//将路径的最后一个顶点添加到顶点列表中，以迭代 foreach (lastNode.adjacentNodes 中的 Node nextNode)//foreach-loop，迭代前一个节点的所有邻居{ if (path)。Count > = 3 & & & path [0] = = nextNode)//如果找到一个长度大于或等于3的循环{ cycloesArefound = true; short estCycles。Add (path) ;//将路径添加到一组循环中。如果(！路径。包含(nextNode))//如果路径不包含邻居{ newNodes。Add (nextNode) ;//将邻居添加到顶点集以迭代//创建新路径 List < Node > newPath = new List < Node > () ; newPath。将当前路径的顶点按照正确的新路径顺序添加到新路径。Add (nextNode) ;//将邻居添加到新路径 newPath。Add (newPath) ;//将路径添加到新找到的路径集}}路径 = newPath;//更新当前路径集} if (short estCycles。计数 > 0)//如果找到循环{控制台。WriteLine (“图表包含”+ short estCycles。计数 + “循环的长度”+ “循环的长度”+ 。打印到控制台 foreach (List < Node > Cycle in short estCycles)//foreach-loop，迭代所有找到的循环{ Console。WriteLine (ToString (Cycle)) ;//打印到控制台}} else { Console。WriteLine (“该图不包含循环。"); // Print to console }

Console.ReadLine(); } } </syntaxhighlight>

Covering graphs by cycle

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

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

在他1736年发表的关于柯尼斯堡七桥问题的论文中，莱昂哈德 · 欧拉证明了，对于一个有限的无向图来说，如果一个闭游走恰好访问每条边一次(使它成为一条闭路) ，那么除了孤立的顶点(也就是说，所有的边都包含在一个分量中)之外，它都是连通的，并且在每个顶点都有偶数度。有向图中每条边只有一次访问的闭角色塑造存在的相应条件是图是强连通的，并且在每个顶点有相等数量的传入和传出边。在这两种情况下，由此产生的闭合路径被称为欧拉路径。如果一个有限的无向图在它的每个顶点都有偶度，不管它是否连通，那么就有可能找到一组简单的循环，它们一起覆盖每个边只有一次: 这就是 Veblen 定理。.当一个连通图不满足欧拉定理的条件时，通过求解路径检测问题，可以在多项式时间内找到覆盖每条边至少一次的最小长度闭游动。

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

要找到一个只覆盖每个顶点一次的简单循环，而不是覆盖边缘，这个问题要困难得多。这样的循环称为哈密顿循环，判断它是否存在是 NP- 完全的。.关于可以保证包含哈密顿圈的图类，已经发表了许多研究成果，其中一个例子是奥尔定理，即哈密顿圈总是可以在一个图中找到，对于这个图，每一对不相邻的顶点都有至少相等于图中顶点总数的度。.

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]

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

圈双覆盖猜想指出，对于每个无桥图，存在一个多重简单圈，它恰好覆盖图的每个边两次。证明这是真的(或者找到一个反例)仍然是一个悬而未决的问题。

Graph classes defined by cycle

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

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

= = 圈定义的图类 = = 几个重要的图类可以用圈定义或拥有属性定义。这些图包括:

  • 二部图，一个没有奇数圈的图(顶点数为奇数的圈)
  • 仙人掌图，一个每个非平凡的双连通部分都是圈的图
  • 循环图，一个由单个循环组成的图
  • 弦图，一个每个诱导循环都是三角形的图
  • 有向无环图,
  • 完美图，没有诱导圈或其长度大于3的奇数补图
  • 伪森林，每个连接元件(图论)最多只有一个圈的图
  • 绞合图，每个外围圈都是三角形的图
  • 强连通图，每条边都是圈的一部分的有向图
  • 无三角形图，没有三个顶点圈的图

See also

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

= 参见同样 =

  • 循环空间
  • 循环基础
  • 循环检测在一系列迭代函数值中

References

  1. ↑ 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.
  2. ↑ Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
  3. ↑ 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. 
  4. ↑ 4.0 4.1 Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison–Wesley, ISBN 0-201-06672-6
  5. ↑ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC.. pp. 260. ISBN 0-471-25060-0. https://archive.org/details/operatingsystemc0006silb. 
  6. ↑ GeeksforGeeks: Shortest cycle in an undirected unweighted graph
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
  10. ↑ Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.


References

Category:Graph theory objects

范畴: 图论对象


This page was moved from wikipedia:en:Cycle (graph theory). Its edit history can be viewed at 圈（图论）/edithistory

取自“https://wiki.swarma.org/index.php?title=圈（图论）&oldid=32664”