更改

== 定义==

== 定义==

===步道 轨迹 路径 Walk, trail, path ===

===通路 轨迹 路径 Walk, trail, path ===

[[File:Trail_but_not_path.svg|200px|thumb|right |图2：从A到E的轨迹，非路径]]

[[File:Trail_but_not_path.svg|200px|thumb|right |图2：从A到E的轨迹，非路径]]

* '''步道 Walk'''：是连接一系列[[顶点]]形成的有限或无限的边序列。

* '''通路 Walk'''：是连接一系列[[顶点]]形成的有限或无限的边序列。

:以一个图为例 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 。'''有限步道 finite walk'''是一系列的边 ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )，其顶点序列( ''v''₁, ''v''₂, …, ''v''_''n'' ) 。 ''ϕ'' ( ''e''_''i'' ) = {''v''_''i'', ''v''_{''i'' + 1}}对于''i'' = 1, 2, …, ''n'' − 1。 ( ''v''₁, ''v''₂, …, ''v''_''n'' ) 是移动的顶点序列。如果 ''v''₁ = ''v''_''n'' ，则此步道封闭，反之则开放。'''无限步道 infinite walk'''是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)则有起点但是没有终点。

:以一个图为例 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 。'''有限通路 finite walk'''是一系列的边 ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )，其顶点序列( ''v''₁, ''v''₂, …, ''v''_''n'' ) 。 ''ϕ'' ( ''e''_''i'' ) = {''v''_''i'', ''v''_{''i'' + 1}}对于''i'' = 1, 2, …, ''n'' − 1。 ( ''v''₁, ''v''₂, …, ''v''_''n'' ) 是移动的顶点序列。如果 ''v''₁ = ''v''_''n'' ，则此通路封闭，反之则开放。'''无限通路 infinite walk'''是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限通路(或光线)则有起点但是没有终点。

* '''轨迹 trail'''是所有的边缘都清晰可见的步道。

* '''轨迹 trail'''是所有的边缘都清晰可见的通路。

* '''路径 path'''是一条所有顶点（包括所有边）都是不同的轨迹。

* '''路径 path'''是一条所有顶点（包括所有边）都是不同的轨迹。

如果 ''w'' = ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )是有顶点的序列 (''v''₁, ''v''₂, …, ''v''_''n'')，那么''w '' 就是从 ''v''₁ 到 ''v''_''n''的有限步道。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限步道，那么在它们之间也有一条有限的轨迹和一条有限的路径。

如果 ''w'' = ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )是有顶点的序列 (''v''₁, ''v''₂, …, ''v''_''n'')，那么''w '' 就是从 ''v''₁ 到 ''v''_''n''的有限通路。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限通路，那么在它们之间也有一条有限的轨迹和一条有限的路径。

一个'''加权图 weighted graph'''将一个值（权重）与图中的每条边相关联。一个加权图中的步道（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。

一个'''加权图 weighted graph'''将一个值（权重）与图中的每条边相关联。一个加权图中的通路（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。

<br>

<br>

===  有向的步道，轨迹，路径 Directed walk, trail, path===

===  有向的通路，轨迹，路径 Directed walk, trail, path===

* '''有向步道 directed walk'''是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。

* '''有向通路 directed walk'''是指由连接一系列顶点的边沿相同方向定向形成的有限或无限序列。

:以一个有向图 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 为例。有限有向步道由一系列的边组成 ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )，而对于这些边，又存在一系列的顶点 ( ''v''₁, ''v''₂, …, ''v''_''n'' )。 ''ϕ'' ( ''e''_''i'' ) = ( ''v''_''i'', ''v''_{''i'' + 1} )对于 ''i'' = 1, 2, …, ''n'' − 1 。( ''v''₁, ''v''₂, …, ''v''_''n'' )是有向步道的顶点序列。无限有向步道是一个边序列，其类型与本文描述的相同，但起点或终点，而半无限有向步道（或射线）有起点，但没有终点。

:以一个有向图 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 为例。有限有向通路由一系列的边组成 ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )，而对于这些边，又存在一系列的顶点 ( ''v''₁, ''v''₂, …, ''v''_''n'' )。 ''ϕ'' ( ''e''_''i'' ) = ( ''v''_''i'', ''v''_{''i'' + 1} )对于 ''i'' = 1, 2, …, ''n'' − 1 。( ''v''₁, ''v''₂, …, ''v''_''n'' )是有向通路的顶点序列。无限有向通路是一个边序列，其类型与本文描述的相同，但起点或终点，而半无限有向通路（或射线）有起点，但没有终点。

* '''有向轨迹 directed trail'''是指所有边都可见的轨迹。

* '''有向轨迹 directed trail'''是指所有边都可见的轨迹。

假设一个步道 ''w'' = ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )是顶点序列有限的( ''v''₁, ''v''₂, …, ''v''_''n'' )有向步道，那么''w''就是从 ''v''₁ ''到 ''v''_''n''的步道。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道，那么在它们之间也存在有限有向轨迹和有限有向路径。

假设一个通路 ''w'' = ( ''e''₁, ''e''₂, …, ''e''_{''n'' − 1} )是顶点序列有限的( ''v''₁, ''v''₂, …, ''v''_''n'' )有向通路，那么''w''就是从 ''v''₁ ''到 ''v''_''n''的通路。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向通路，那么在它们之间也存在有限有向轨迹和有限有向路径。

一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向步道（或路径）的权是有向边权重的和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。

一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向通路（或路径）的权是有向边权重的和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。

<br>

<br>

* [[Bellman–Ford算法 Bellman–Ford algorithm]]

* [[Bellman–Ford算法 Bellman–Ford algorithm]]

* [[Floyd–Warshall算法 Floyd–Warshall algorithm]]

* [[Floyd–Warshall算法 Floyd–Warshall algorithm]]

* [[自我避免的步道 Self-avoiding walk]]

* [[自我避免的通路 Self-avoiding walk]]

* [[最短路径图Shortest-path graph]]

* [[最短路径图Shortest-path graph]]

==编者推荐==

==编者推荐==

====[https://campus.swarma.org/course/2013 中介分析和路径因果效应（下）]====

=== 课程推荐 ===

 

[[File:巴拉巴西网络科学.jpeg|360px|缩略图|[https://campus.swarma.org/course/1754 巴拉巴西网络科学（课程）]]]

 

 

====[https://campus.swarma.org/course/1754 巴拉巴西网络科学（课程）]====