526
个编辑
更改
跳到导航
跳到搜索
第44行：
第44行： − + 第57行：
第57行： − + 第65行：
第65行： − 有些学者并不要求路径的所有顶点都是不同的，而是使用术语“简单路径”来指代这样的路径。+
→Walk, trail, path 步道 轨迹 路径
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.
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.
以一个图为例{{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 begin}}''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}}对于{{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} 是移动的顶点序列。如果 {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}} ，则此步道封闭，反之则开放。一个无限步道是由一系列的边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)有起点但是没有终点。
以一个图为例{{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 begin}}''ϕ''(''e''<sub>''i''</sub>) = {''v''<sub>''i''</sub>, ''v''<sub>''i'' + 1</sub>}{{nowrap end}}对于{{nowrap|1=''i'' = 1, 2, …, ''n'' − 1}}. {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} 是移动的顶点序列。如果 {{nowrap begin}}''v''<sub>1</sub> = ''v''<sub>''n''</sub>{{nowrap end}} ，则此步道封闭，反之则开放。一个无限步道是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)则有起点但是没有终点。
* 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}}
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> ''to'' ''v''<sub>''n''</sub>的步行。同样，对于一条轨迹或者一条路径也是如此。如果在两个不同的顶点之间有一个有限步道，那么在它们之间也有一个有限的轨迹和一个有限的路径。
如果 {{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 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.
有些学者对路径的定义中并不要求它的所有顶点都是不同的，而是使用术语“简单路径”来指代这样的路径。