更改

删除2,247字节 、 2020年12月3日 (四) 23:38
第15行: 第15行:     
[[File:Trail but not path.svg|200px|thumb|right |图2:Trail from A to E,but not path 从A到E的轨迹而非路径]]
 
[[File:Trail but not path.svg|200px|thumb|right |图2:Trail from A to E,but not path 从A到E的轨迹而非路径]]
      
* '''步道 Walk''':是连接一系列[[顶点]]形成的有限或无限的边序列。
 
* '''步道 Walk''':是连接一系列[[顶点]]形成的有限或无限的边序列。
第38行: 第37行:  
===  有向的步道,轨迹,路径 Directed walk, trail, path===
 
===  有向的步道,轨迹,路径 Directed walk, trail, path===
   −
* '''有向步道 directed walk'''是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。{{sfn|Bender|Williamson|2010|p=162}}
     −
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.
+
* '''有向步道 directed walk'''是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。
   −
以一个有向图{{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.
+
以一个有向图 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 为例。有限有向步道由一系列的边组成 ( ''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> )是有向步道的顶点序列。无限有向步道是一个边序列,其类型与本文描述的相同,但起点或终点,而半无限有向步道(或射线)有起点,但没有终点。
'''有向轨迹 directed trail'''是指所有边都可见的轨迹。{{sfn|Bender|Williamson|2010|p=162}}
     −
* A '''directed path''' is a directed trail in which all vertices are distinct.
+
* '''有向轨迹 directed trail'''是指所有边都可见的轨迹。
'''有向路径 directed path'''是指所有顶点都不同的有向路径。{{sfn|Bender|Williamson|2010|p=162}}
      +
*'''有向路径 directed path'''是指所有顶点都不同的有向路径。
   −
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.
     −
假设一个步道{{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>的步道。同样,对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道,那么在它们之间也存在有限有向轨迹和有限有向路径。
      第59行: 第54行:        +
一个加权有向图将一个值(权重)与有向图中的每条边相关联。加权有向图中有向步道(或路径)的权是有向边权重的和。有时,“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
   −
A [[Weighted graph|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.
+
<br>
 
  −
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.
  −
 
  −
一个加权有向图将一个值(权重)与有向图中的每条边相关联。加权有向图中有向步道(或路径)的权是有向边权重的和。有时,“成本”或“长度”这两个词可以用来指代“权重”这一概念。
      
==例子==
 
==例子==
7,129

个编辑