526
个编辑
更改
→Directed walk, trail, path 有向的步道，轨迹，路径
Let {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} be a directed graph. A finite directed walk is a sequence of edges for which there is a sequence of vertices such that for . 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 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 for which there is a sequence of vertices such that for . 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 ray) has a first vertex but no last vertex.
以一个有向图{{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}}为例。有限有向步道是一系列的边 {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}}，对于这些边，存在一系列的顶点 {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}}。{{nowrap|1=''ϕ''(''e''<sub>''i''</sub>) = (''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>)}}对于{{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}}是有向步道的顶点序列。无限有向步道是一个边序列，其类型与本文描述的相同，但没有第一个顶点或最后一个顶点，而半无限有向步道(或射线)有第一个顶点，但没有最后一个顶点。
以一个有向图{{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}}为例。有限有向步道由一系列的边组成 {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}}，而对于这些边，又存在一系列的顶点 {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}}。{{nowrap|1=''ϕ''(''e''<sub>''i''</sub>) = (''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>)}}对于{{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}}是有向步道的顶点序列。无限有向步道是一个边序列，其类型与本文描述的相同，但起点或终点，而半无限有向步道(或射线)有起点，但没有终点。
* 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>'''是指所有边缘都清晰可见的有向轨迹。
'''<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}}
If is a finite directed walk with vertex sequence then w is said to be a walk from v<sub>1</sub> to v<sub>n</sub>. Similarly for a directed trail or a path. If there is a finite directed walk between two distinct vertices then there is also a finite directed trail and a finite directed path between them.
If is a finite directed walk with vertex sequence then w is said to be a walk from v<sub>1</sub> to v<sub>n</sub>. Similarly for a directed trail or a path. If there is a finite directed walk between two distinct vertices then there is also a finite directed trail and a finite directed path between them.
假设一个步道{{nowrap|1=''w'' = (''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}}是顶点序列有限的{{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}}有向步道，那么 w 就是从 ''v''<sub>1</sub> ''到'' ''v''<sub>''n''</sub>的步行。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道，那么在它们之间也存在有限有向轨迹和有限有向路径。
Some authors do not require that all vertices of a directed path be distinct and instead use the term simple directed path to refer to such a directed path.
Some authors do not require that all vertices of a directed path be distinct and instead use the term simple directed path to refer to such a directed path.
有些学者并不要求有向路径的所有顶点都是不同的，他们用“简单有向路径”这个术语来表示这样一个有向路。
A weighted directed graph associates a value (weight) with every edge in the directed graph. The weight of a directed walk (or trail or path) in a weighted directed graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.
A weighted directed graph associates a value (weight) with every edge in the directed graph. The weight of a directed walk (or trail or path) in a weighted directed graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.
一个加权有向图将一个值(权)与有向图中的每条边相关联。加权有向图中有向步道(或路径)的权是有向边权重的和。有时，“成本”或“长度”这两个词用来代替“权重”。
一个加权有向图将一个值(权)与有向图中的每条边相关联。加权有向图中有向步道(或路径)的权是有向边权重的和。有时，“成本”或“长度”这两个词可以用来代替“权重”。
== Examples 例子==
== Examples 例子==