75
个编辑
更改
跳到导航
跳到搜索
第15行：
第15行： − 在图论中，图中的路径是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(因为顶点是不同的，所以边也是不同的)。有向图中的有向路径(有时称为dipath)是一个有限或无限的边序列，它连接一系列不同的顶点，但附加的限制是所有的边都朝向同一个方向。+ 第23行：
第23行： − + 第36行：
第36行： − 步道是连接一系列顶点的有限或无限的边序列+ 第45行：
第45行： − 轨迹是所有的边缘都清晰可见的步道+ − 路径是一条所有顶点(因此也包括所有边)都是不同的轨迹。+ 第71行：
第71行： − 一个加权图将一个值(权)与图中的每条边相关联。一个加权图中的步道(或轨迹或路径)的权是所有边的权之和。有时，“成本”或“长度”这两个词用来代替“权重”。+ 第78行：
第78行： − 有向步道是沿相同方向定向的边的有限或无限序列，该边连接一系列顶点。+ 第87行：
第87行： − 有向轨迹是指所有边缘都清晰可见的有向轨迹。+ − 有向路径是指所有顶点都是不同的有向路径。+ 第126行：
第126行： − 没有图的边连接两个不连续的路径顶点的路径称为诱导路径。+ − 包含图的每个顶点的路径称为哈密顿路径。+ 第155行：
第155行： − +
无编辑摘要
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
在'''<font color="#ff8000">图论 Graph Theory</font>'''中，图中的'''<font color="#ff8000">路径 Path</font>'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(因为顶点是不同的，所以边也是不同的)。'''<font color="#ff8000">有向图 Directed Graph</font>'''中的有向路径(有时称为dipath)是一个有限或无限的边序列，它连接一系列不同的顶点，但附加的限制是所有的边都朝向同一个方向。
Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.
Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.
路径是图论的基本概念，在大多数图论文本的导论部分都有描述。邦迪和默蒂(1976) ，吉本斯(1985) ，或迪斯特尔(2005)。柯尔特(1990)等人著作中，涵盖了更多关于图中路径的高级算法话题。
路径是图论的基本概念，在大多数图论文本的导论部分都有描述。邦迪和默蒂(1976) ，吉本斯(1985) ，或迪斯特尔(2005)。柯尔特(1990)等人著作中，涵盖了更多关于图中路径的高级算法的话题。
* A '''walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}}
* A '''walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}}
'''<font color="#ff8000">步道 Walk</font>'''是连接一系列顶点的有限或无限的边序列
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a graph. A finite walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} such that {{nowrap begin}}''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}} for {{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the walk. This walk is ''closed'' if {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}}, and ''open'' else. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a graph. A finite walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} such that {{nowrap begin}}''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}} for {{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the walk. This walk is ''closed'' if {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}}, and ''open'' else. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
* A '''trail''' is a walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
* A '''trail''' is a walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
'''<font color="#ff8000">轨迹 Trail</font>'''是所有的边缘都清晰可见的步道
* A '''path''' is a trail in which all vertices (and therefore also all edges) are distinct.{{sfn|Bender|Williamson|2010|p=162}}
* A '''path''' is a trail in which all vertices (and therefore also all edges) are distinct.{{sfn|Bender|Williamson|2010|p=162}}
'''<font color="#ff8000">路径 Path</font>'''是一条所有顶点(因此也包括所有边)都是不同的轨迹。
A weighted graph associates a value (weight) with every edge in the graph. The weight of a walk (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.
A weighted graph associates a value (weight) with every edge in the graph. The weight of a walk (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.
一个'''<font color="#ff8000">加权图 Weighted Graph</font>'''将一个值(权)与图中的每条边相关联。一个加权图中的步道(或轨迹或路径)的权是所有边的权之和。有时，“成本”或“长度”这两个词用来代替“权重”。
* A '''directed walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] directed in the same direction which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}}
* A '''directed walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] directed in the same direction which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}}
'''<font color="#ff8000">有向步道 Directed Walk</font>'''是沿相同方向定向的边的有限或无限序列，该边连接一系列顶点。
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a directed graph. A finite directed walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} such that {{nowrap|1=''ϕ''(''e''<sub>''i''</sub>) = (''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>)}} for {{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the directed walk. An infinite directed walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite directed walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a directed graph. A finite directed walk is a sequence of edges {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} for which there is a sequence of vertices {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} such that {{nowrap|1=''ϕ''(''e''<sub>''i''</sub>) = (''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>)}} for {{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} is the ''vertex sequence'' of the directed walk. An infinite directed walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite directed walk (or [[End (graph theory)|ray]]) has a first vertex but no last vertex.
* A '''directed trail''' is a directed walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
* A '''directed trail''' is a directed walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
'''<font color="#ff8000">有向轨迹 Directed Trail</font>'''是指所有边缘都清晰可见的有向轨迹。
* A '''directed path''' is a directed trail in which all vertices are distinct.{{sfn|Bender|Williamson|2010|p=162}}
* A '''directed path''' is a directed trail in which all vertices are distinct.{{sfn|Bender|Williamson|2010|p=162}}
'''<font color="#ff8000">有向路径 Directed Path</font>'''是指所有顶点都是不同的有向路径。
* A path such that no graph edges connect two nonconsecutive path vertices is called an [[induced path]].
* A path such that no graph edges connect two nonconsecutive path vertices is called an [[induced path]].
没有图的边连接两个不连续的路径顶点的路径称为'''<font color="#ff8000">诱导路径 Induced Path</font>'''。
* A path that includes every vertex of the graph is known as a [[Hamiltonian path]].
* A path that includes every vertex of the graph is known as a [[Hamiltonian path]].
包含图的每个顶点的路径称为'''<font color="#ff8000">哈密顿路径 Hamiltonian Path</font>'''。
* Two paths are ''vertex-independent'' (alternatively, ''internally vertex-disjoint'') if they do not have any internal vertex in common. Similarly, two paths are ''edge-independent'' (or ''edge-disjoint'') if they do not have any internal edge in common. Two internally vertex-disjoint paths are edge-disjoint, but the converse is not necessarily true.
* Two paths are ''vertex-independent'' (alternatively, ''internally vertex-disjoint'') if they do not have any internal vertex in common. Similarly, two paths are ''edge-independent'' (or ''edge-disjoint'') if they do not have any internal edge in common. Two internally vertex-disjoint paths are edge-disjoint, but the converse is not necessarily true.
Dijkstra's algorithm produces a list of shortest paths from a source vertex to every other vertex in directed and undirected graphs with non-negative edge weights (or no edge weights), whilst the Bellman–Ford algorithm can be applied to directed graphs with negative edge weights. The Floyd–Warshall algorithm can be used to find the shortest paths between all pairs of vertices in weighted directed graphs.
Dijkstra's algorithm produces a list of shortest paths from a source vertex to every other vertex in directed and undirected graphs with non-negative edge weights (or no edge weights), whilst the Bellman–Ford algorithm can be applied to directed graphs with negative edge weights. The Floyd–Warshall algorithm can be used to find the shortest paths between all pairs of vertices in weighted directed graphs.
Dijkstra 算法产生了一个从源顶点到无向或有向图中每个顶点的最短路径列表，而 Bellman-Ford 算法可以应用于具有负边权重的有向图。利用 Floyd-Warshall 算法可以求出加权有向图中所有顶点对之间的最短路径。
'''<font color="#ff8000">Dijkstra 算法</font>'''产生了一个从源顶点到无向或有向图中每个顶点的最短路径列表，而'''<font color="#ff8000">Bellman-Ford 算法</font>''' 可以应用于具有负边权重的有向图。利用'''<font color="#ff8000"> Floyd-Warshall 算法</font>'''可以求出加权有向图中所有顶点对之间的最短路径。