2,443
个编辑
更改
跳到导航
跳到搜索
第13行：
第13行： − + − + − + − + − + 第32行：
第32行： − + − + − + − + 第48行：
第48行： − 假设一个步道 ''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>的步道。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道，那么在它们之间也存在有限有向轨迹和有限有向路径。+ 第54行：
第54行： − 一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向步道（或路径）的权是有向边权重的和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。+ 第94行：
第94行： − + 第115行：
第115行： − ====[https://campus.swarma.org/course/2008 中介分析和路径因果效应（上）]==== − 本课程是“因果科学与Causal AI”读书会进行第五期的线上论文分享录像，主题是“中介分析和路径因果效应(论文解读)”，将由毕业于北京大学数学学院陆怡舟以及北京大学数学科学学院在读博士胡文杰来进行分享。 − + − 本课程是“因果科学与Causal AI”读书会进行第四期的线上论文分享录像，主题是“中介分析和路径因果效应”，将由ThoughtWorks高级咨询师兼东南亚市场技术总监徐培以及辅仁大学心理系在读硕士原显智来进行分享。+ + + + + + + + + +
无编辑摘要
== 定义==
== 定义==
===步道 轨迹 路径 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''<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> ) 是移动的顶点序列。如果 ''v''<sub>1</sub> = ''v''<sub>''n''</sub> ，则此步道封闭，反之则开放。'''无限步道 infinite walk'''是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限步道(或光线)则有起点但是没有终点。
:以一个图为例 ''G'' = ( ''V'', ''E'', ''ϕ'' ) 。'''有限通路 finite walk'''是一系列的边 ( ''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> ) 是移动的顶点序列。如果 ''v''<sub>1</sub> = ''v''<sub>''n''</sub> ，则此通路封闭，反之则开放。'''无限通路 infinite walk'''是由一系列边组成的，它们的类型与这里描述的相同，但没有起点或终点，而一个半无限通路(或光线)则有起点但是没有终点。
* '''轨迹 trail'''是所有的边缘都清晰可见的步道。
* '''轨迹 trail'''是所有的边缘都清晰可见的通路。
* '''路径 path'''是一条所有顶点（包括所有边）都是不同的轨迹。
* '''路径 path'''是一条所有顶点（包括所有边）都是不同的轨迹。
如果 ''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>的有限步道。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限步道，那么在它们之间也有一条有限的轨迹和一条有限的路径。
如果 ''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>的有限通路。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限通路，那么在它们之间也有一条有限的轨迹和一条有限的路径。
一个'''加权图 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''<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> )是有向步道的顶点序列。无限有向步道是一个边序列，其类型与本文描述的相同，但起点或终点，而半无限有向步道（或射线）有起点，但没有终点。
:以一个有向图 ''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'''是指所有边都可见的轨迹。
* '''有向轨迹 directed trail'''是指所有边都可见的轨迹。
假设一个通路 ''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>
<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 巴拉巴西网络科学（课程）]====
本课程中，有幸邀请了汪小帆、赵海兴、许小可、史定华、陈清华、张江、狄增如、陈关荣、樊瑛、刘宗华这十个来自六大不同高校、在网络科学领域耕耘许久的教授作为导师，依据教材框架，各有侧重地为我们共同勾勒出整个学科的美丽图景，展示这个学科的迷人魅力，指引这个学科的灿烂未来。
====[https://campus.swarma.org/course/2328 网络科学导论 | 网络科学集智课堂第二期）]====
本课程中，有幸邀请了陈关荣、史定华、樊瑛等这十个来自不同高校、在网络科学领域耕耘许久的教授作为导师，围绕网络动力学这一前沿的方向，帮助大家构建网络科学学习体系。