7,129
个编辑
更改
跳到导航
跳到搜索
第19行：
第19行： − 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 be a graph. A finite walk is a sequence of edges for which there is a sequence of vertices such that ϕ(e<sub>i</sub>) = {v<sub>i</sub>, v<sub>i + 1</sub>} for . is the vertex sequence of the walk. This walk is closed if v<sub>1</sub> = v<sub>n</sub>, 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 ray) has a first vertex but no last vertex. − + 第35行：
第33行： − + 第43行：
第41行： +
→步道 轨迹 路径 Walk, trail, path
* '''步道 Walk'''：是连接一系列[[顶点]]形成的有限或无限的边序列。
* '''步道 Walk'''：是连接一系列[[顶点]]形成的有限或无限的边序列。
:以一个图为例 ''G'' = (''V'', ''E'', ''ϕ'') 。'''有限步道 finite walk'''是一系列的边 (''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)，其顶点序列(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>) 。 ''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}对于''i'' = 1, 2, …, ''n'' − 1 . (''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>) 是移动的顶点序列。如果 ''v''<sub>1</sub> = ''v''<sub>''n''</sub> ，则此步道封闭，反之则开放。'''无限步道 infinite walk'''是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)则有起点但是没有终点。
:以一个图为例 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 。'''有限步道 finite walk'''是一系列的边 ( ''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub> )，其顶点序列( ''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub> ) 。 ''ϕ'' ( ''e''<sub>''i''</sub> ) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}对于''i'' = 1, 2, …, ''n'' − 1。 ( ''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub> ) 是移动的顶点序列。如果 ''v''<sub>1</sub> = ''v''<sub>''n''</sub> ，则此步道封闭，反之则开放。'''无限步道 infinite walk'''是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)则有起点但是没有终点。
If is a finite 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 trail or a path. If there is a finite walk between two distinct vertices then there is also a finite trail and a finite path between them.
If is a finite 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 trail or a path. If there is a finite walk between two distinct vertices then there is also a finite trail and a finite 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>的有限步道。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限步道，那么在它们之间也有一条有限的轨迹和一条有限的路径。
如果 ''w'' = ( ''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub> )是有顶点的序列 (''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)，那么''w '' 就是从 ''v''<sub>1</sub> 到 ''v''<sub>''n''</sub>的有限步道。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限步道，那么在它们之间也有一条有限的轨迹和一条有限的路径。
一个'''加权图 weighted graph'''将一个值（权重）与图中的每条边相关联。一个加权图中的步道（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
一个'''加权图 weighted graph'''将一个值（权重）与图中的每条边相关联。一个加权图中的步道（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
<br>
=== 有向的步道，轨迹，路径 Directed walk, trail, path===
=== 有向的步道，轨迹，路径 Directed walk, trail, path===