7,129
个编辑
更改
跳到导航
跳到搜索
第15行：
第15行： − 第38行：
第37行： − * '''有向步道 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.+ − 以一个有向图{{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.+ − − + − '''有向路径 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. − + 第59行：
第54行： + − 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.+ − − 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. − − 一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向步道（或路径）的权是有向边权重的和。有时，“成本”或“长度”这两个词可以用来指代“权重”这一概念。
→定义
[[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'''：是连接一系列[[顶点]]形成的有限或无限的边序列。
=== 有向的步道，轨迹，路径 Directed walk, trail, path===
=== 有向的步道，轨迹，路径 Directed walk, trail, path===
* '''有向步道 directed walk'''是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。
以一个有向图 ''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'''是指所有顶点都不同的有向路径。
假设一个步道{{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>的步道。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道，那么在它们之间也存在有限有向轨迹和有限有向路径。
一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向步道（或路径）的权是有向边权重的和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
<br>
==例子==
==例子==