526
个编辑
更改
无编辑摘要
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)是一个有限或无限的边序列，它连接一系列不同的顶点，但附加的条件是所有的边都方向相同。
在'''<font color="#ff8000">图论 Graph Theory</font>'''中，图中的'''<font color="#ff8000">路径 Path</font>'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。'''<font color="#ff8000">有向图 Directed Graph</font>'''(有时也称为dipath)中的有向路径，在具有附加条件：所有的边都方向相同时是一个有限或无限的边序列，它连接一系列不同的顶点。
--[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“涵盖了更多关于图中路径的高级算法的话题。”一句中的“涵盖”改为“涉及”
--[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“涵盖了更多关于图中路径的高级算法的话题。”一句中的“涵盖”改为“涉及”
--[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“邦迪和默蒂(1976) ，吉本斯(1985) ，或迪斯特尔(2005)。柯尔特(1990)等人著作中，”一句改为“如邦迪和默蒂(1976) 、吉本斯(1985) 、迪斯特尔(2005)、柯尔特(1990)等人著作中，”
--[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“邦迪和默蒂(1976) ，吉本斯(1985) ，或迪斯特尔(2005)。柯尔特(1990)等人著作中，”一句改为“如在邦迪和默蒂(1976) 、吉本斯(1985) 、迪斯特尔(2005)、柯尔特(1990)等人著作中，”
== Definitions 定义==
== Definitions 定义==
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}} ，则此步道封闭，反之则开放。一个无限步道是由一系列的边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)有起点但是没有终点。
* 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}}