第16行: |
第16行: |
| 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)中的有向路径,在具有附加条件:所有的边都方向相同时是一个有限或无限的边序列,它连接一系列不同的顶点。 | + | 在[[图论 Graph theory]]中,图中的'''路径 path'''是一个有限或无限的边序列,这些边连接着一系列顶点,这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的,所以图中的边也是不同的)。有向图(有时也称为dipath)中的有向路径,在具有附加条件:所有的边都方向相同时是一个有限或无限的边序列,它连接一系列不同的顶点。 |
| | | |
| | | |
第29行: |
第29行: |
| --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“邦迪和默蒂(1976) ,吉本斯(1985) ,或迪斯特尔(2005)。柯尔特(1990)等人著作中,”一句改为“如在邦迪和默蒂(1976) 、吉本斯(1985) 、迪斯特尔(2005)、柯尔特(1990)等人著作中,” | | --[[用户:CecileLi|CecileLi]]([[用户讨论:CecileLi|讨论]]) 【审校】“邦迪和默蒂(1976) ,吉本斯(1985) ,或迪斯特尔(2005)。柯尔特(1990)等人著作中,”一句改为“如在邦迪和默蒂(1976) 、吉本斯(1985) 、迪斯特尔(2005)、柯尔特(1990)等人著作中,” |
| | | |
− | == Definitions 定义== | + | == 定义== |
| | | |
− | === Walk, trail, path 步道 轨迹 路径=== | + | ===步道 轨迹 路径 Walk, trail, path === |
| | | |
− | [[File:Trail but not path.svg|200px|thumb|right | + | [[File:Trail but not path.svg|200px|thumb|right |图2:Trail from A to E,but not path 从A到E的轨迹而非路径]] |
− | 图2:Trail from A to E,but not path 从A到E的轨迹而非路径]] | |
| | | |
| | | |
− | * A '''walk''' is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]].{{sfn|Bender|Williamson|2010|p=162}} | + | * '''步道 Walk''':是连接一系列[[顶点]]形成的有限或无限的边序列。{{sfn|Bender|Williamson|2010|p=162}} |
− | '''<font color="#ff8000">步道 Walk</font>'''是连接一系列顶点形成的有限或无限的边序列
| |
| | | |
| 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 {{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. |
第44行: |
第42行: |
| 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'', ''ϕ'')}} 。'''有限步道 finite walk'''是一系列的边{{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}} ,则此步道封闭,反之则开放。'''无限步道 infinite walk'''是由一系列边组成的,它们的类型与这里描述的相同,但没有起点或终点,而一个半无限步道(或光线)则有起点但是没有终点。 |
| | | |
− | * A '''trail''' is a walk in which all edges are distinct.{{sfn|Bender|Williamson|2010|p=162}}
| |
− | '''<font color="#ff8000">轨迹 Trail</font>'''是所有的边缘都清晰可见的步道
| |
| | | |
− | * A '''path''' is a trail in which all vertices (and therefore also all edges) are distinct.{{sfn|Bender|Williamson|2010|p=162}} | + | * '''轨迹 trail'''是所有的边缘都清晰可见的步道。{{sfn|Bender|Williamson|2010|p=162}} |
− | '''<font color="#ff8000">路径 Path</font>'''是一条所有顶点(因此也包括所有边)都是不同的轨迹。 | + | |
| + | * '''路径 path'''是一条所有顶点(因此也包括所有边)都是不同的轨迹。{{sfn|Bender|Williamson|2010|p=162}} |
| | | |
| | | |
第59行: |
第56行: |
| 如果 {{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>的有限步道。同样,对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限步道,那么在它们之间也有一条有限的轨迹和一条有限的路径。 | | 如果 {{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.
| |
| | | |
| 有些学者对路径的定义中并不要求它的所有顶点都是不同的,而是使用术语“简单路径”来指代这样的路径。 | | 有些学者对路径的定义中并不要求它的所有顶点都是不同的,而是使用术语“简单路径”来指代这样的路径。 |
| | | |
| | | |
| + | 一个'''加权图 weighted graph'''将一个值(权重)与图中的每条边相关联。一个加权图中的步道(或轨迹或路径)的权是所有边的权之和。有时,“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。 |
| | | |
− | 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>'''将一个值(权)与图中的每条边相关联。一个加权图中的步道(或轨迹或路径)的权是所有边的权之和。有时,“成本”或“长度”这两个词可以用来指代“权重”这一概念。
| |
| | | |
− | === Directed walk, trail, path 有向的步道,轨迹,路径=== | + | === 有向的步道,轨迹,路径 Directed walk, trail, path=== |
| | | |
− | * 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}} | + | * '''有向步道 directed walk'''是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。{{sfn|Bender|Williamson|2010|p=162}} |
− | '''<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. |
− |
| |
− | 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. |
− | '''<font color="#ff8000">有向轨迹 Directed Trail</font>'''是指所有边都可见的轨迹。
| + | '''有向轨迹 directed trail'''是指所有边都可见的轨迹。{{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}} | + | * A '''directed path''' is a directed trail in which all vertices are distinct. |
− | '''<font color="#ff8000">有向路径 Directed Path</font>'''是指所有顶点都不同的有向路径。
| + | '''有向路径 directed path'''是指所有顶点都不同的有向路径。{{sfn|Bender|Williamson|2010|p=162}} |
| | | |
| | | |
| If {{nowrap|1=''w'' = (''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} is a finite directed walk with vertex sequence {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} 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 {{nowrap|1=''w'' = (''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n'' − 1</sub>)}} is a finite directed walk with vertex sequence {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>)}} 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>的步道。同样,对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道,那么在它们之间也存在有限有向轨迹和有限有向路径。 | | 假设一个步道{{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>的步道。同样,对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道,那么在它们之间也存在有限有向轨迹和有限有向路径。 |
| | | |
| | | |
− | | + | 有些学者并不要求有向路径的所有顶点都是不同的,因此他们用“简单有向路径 simple 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.
| |
− | | |
− | 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.
| |
− | | |
− | 有些学者并不要求有向路径的所有顶点都是不同的,因此他们用“简单有向路径”这个术语来表示它。
| |
| | | |
| | | |
第113行: |
第91行: |
| 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 例子== | + | ==例子== |
| | | |
− | * A graph is [[Connectivity (graph theory)|connected]] if there are paths containing each pair of vertices. | + | * 如果路径包含每一对顶点,那么图就是连通的。 |
− | 如果路径包含每一对顶点,那么图就是连通的。 | |
| | | |
| * A directed graph is [[Strongly-connected digraph|strongly connected]] if there are oppositely oriented directed paths containing each pair of vertices. | | * A directed graph is [[Strongly-connected digraph|strongly connected]] if there are oppositely oriented directed paths containing each pair of vertices. |
| 如果一个有向图中存在包含每对顶点的相对有向路径,那么这个有向图就是紧密连通的。 | | 如果一个有向图中存在包含每对顶点的相对有向路径,那么这个有向图就是紧密连通的。 |
| | | |
− | * A path such that no graph edges connect two nonconsecutive path vertices is called an [[induced path]]. | + | * 没有边连接两个不连续的路径顶点的路径称为'''<font color="#ff8000">诱导路径 induced path</font>'''。 |
− | 没有边连接两个不连续的路径顶点的路径称为'''<font color="#ff8000">诱导路径 Induced Path</font>'''。 | |
| | | |
− | * A path that includes every vertex of the graph is known as a [[Hamiltonian path]]. | + | * 包含图的每个顶点的路径称为'''<font color="#ff8000">哈密顿路径 Hamiltonian Path</font>'''。 |
− | 包含图的每个顶点的路径称为'''<font color="#ff8000">哈密顿路径 Hamiltonian Path</font>'''。 | |
| | | |
| * Two paths are ''vertex-independent'' (alternatively, ''internally vertex-disjoint'') if they do not have any internal vertex in common. Similarly, two paths are ''edge-independent'' (or ''edge-disjoint'') if they do not have any internal edge in common. Two internally vertex-disjoint paths are edge-disjoint, but the converse is not necessarily true. | | * Two paths are ''vertex-independent'' (alternatively, ''internally vertex-disjoint'') if they do not have any internal vertex in common. Similarly, two paths are ''edge-independent'' (or ''edge-disjoint'') if they do not have any internal edge in common. Two internally vertex-disjoint paths are edge-disjoint, but the converse is not necessarily true. |
− | 如果两条路径没有任何共同的内部顶点,那么它们与顶点无关(换言之,内部顶点不相交)。类似地,如果两条路径没有任何共同的内边,那么它们是边独立的(或边不相交)。两条内部顶点不相交的路径的边也不相交,但反之未必正确的。
| + | 如果两条路径没有任何共同的内部顶点,那么它们与顶点无关(换言之,内部顶点不相交)。类似地,如果两条路径没有任何共同的内边,那么它们是边独立的(或边不相交)。两条内部顶点不相交的路径的边也不相交,但反之未必正确的。 |
| + | |
| + | * 图中两个顶点之间,如果最短路径存在,那么它们的的距离是最短路径的长度,否则该距离是无穷大。 |
| | | |
− | * The [[Distance (graph theory)|distance]] between two vertices in a graph is the length of a shortest path between them, if one exists, and otherwise the distance is infinity. | + | * 连接图的直径是图的顶点对之间的最大距离(如上定义)。 |
− | 图中两个顶点之间,如果最短路径存在,那么它们的的距离是最短路径的长度,否则该距离是无穷大。
| |
| | | |
− | * The diameter of a connected graph is the largest distance (defined above) between pairs of vertices of the graph.
| |
− | 连接图的直径是图的顶点对之间的最大距离(如上定义)。
| |
| | | |
− | == Finding paths 路径寻找== | + | == 路径寻找 Finding paths== |
| | | |
| Several algorithms exist to find [[Shortest path problem|shortest]] and [[Longest path problem|longest]] paths in graphs, with the important distinction that the former problem is computationally much easier than the latter. | | Several algorithms exist to find [[Shortest path problem|shortest]] and [[Longest path problem|longest]] paths in graphs, with the important distinction that the former problem is computationally much easier than the latter. |
第144行: |
第118行: |
| Several algorithms exist to find shortest and longest paths in graphs, with the important distinction that the former problem is computationally much easier than the latter. | | Several algorithms exist to find shortest and longest paths in graphs, with the important distinction that the former problem is computationally much easier than the latter. |
| | | |
− | 求解图的最短路径和最长路径的均有多种算法,但是前者的计算比后者简单得多。
| + | 求解图的[[最短路径]]和[[最长路径]]的均有多种算法,但是前者的计算比后者简单得多。 |
| | | |
| | | |