526
个编辑
更改
跳到导航
跳到搜索
第64行：
第64行： − 有些作者并不要求路径的所有顶点都是不同的，而是使用术语“简单路径”来指代这样的路径。+ 第72行：
第72行： − + 第79行：
第79行： − +
无编辑摘要
Some authors do not require that all vertices of a path be distinct and instead use the term simple path to refer to such a path.
Some authors do not require that all vertices of a path be distinct and instead use the term simple path to refer to such a path.
有些学者并不要求路径的所有顶点都是不同的，而是使用术语“简单路径”来指代这样的路径。
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>'''将一个值(权)与图中的每条边相关联。一个加权图中的步道(或轨迹或路径)的权是所有边的权之和。有时，“成本”或“长度”这两个词用来代替“权重”。
一个'''<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>'''是沿相同方向定向的边的有限或无限序列，该边连接一系列顶点。
'''<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.