路径 path - 版本历史

2024年6月5日 (三) 07:16 Gyt666

2024-06-05T07:16:48Z

思无涯咿呀咿呀：/* 参见 */

2021-03-07T09:46:24Z

参见

2021年3月7日 (日) 09:45 思无涯咿呀咿呀

2021-03-07T09:45:20Z

2021年1月21日 (四) 09:03 Qige96

2021-01-21T09:03:26Z

薄荷：/* 其他链接 */

2020-12-27T14:58:38Z

其他链接

薄荷：薄荷移动页面路径至路径 path

2020-12-03T15:57:55Z

薄荷移动页面路径至路径 path

2020年12月3日 (四) 15:57 薄荷

2020-12-03T15:57:45Z

2020年12月3日 (四) 15:57 薄荷

2020-12-03T15:57:06Z

薄荷：/* References 引用 */

2020-12-03T15:55:20Z

References 引用

薄荷：/* 路径寻找 Finding paths */

2020-12-03T15:52:59Z

路径寻找 Finding paths

←上一版本		2024年6月5日 (三) 07:16的版本
第5行：		第5行：
	[[File:Snake-in-the-box_and_Hamiltonian_path.svg\|thumb\|right\|图1：一个三维的超立方体图表显示一个红色的[[哈密顿图]]，和一个黑色的[[最长诱导路径]]]]		[[File:Snake-in-the-box_and_Hamiltonian_path.svg\|thumb\|right\|图1：一个三维的超立方体图表显示一个红色的[[哈密顿图]]，和一个黑色的[[最长诱导路径]]]]

−	在[[图论 Graph theory]]~~中，图中的~~'''路径 path'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。有向图中的'''有向路径 directed path'''（有时也称为dipath<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>），是一个有限或无限的边序列，它连接一系列不同的顶点，并具有附加一个条件：序列中所有的边都方向都相同。	+	在[[图论 Graph theory]]中，路径（path），图中的'''路径 path'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。有向图中的'''有向路径 directed path'''（有时也称为dipath<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>），是一个有限或无限的边序列，它连接一系列不同的顶点，并具有附加一个条件：序列中所有的边都方向都相同。

@@ 第86行： / 第86行： @@
 == 参见==
-* [[图论词汇 Glossary of graph theory]]
+*  图论词汇表 Glossary of graph theory
-* [[路径图 Path graph]]
+*  路径图 Path graph
-* [[多边形链 Polygonal chain]]
+*  多边形链 Polygonal chain
-* [[最短路径问题 Shortest path problem]]
+*  最短路径问题 Shortest path problem
-* [[最长路径问题 Longest path problem]]
+*  最长路径问题 Longest path problem
-* [[Dijkstra算法 Dijkstra's algorithm]]
+*  [[Dijkstra算法]] Dijkstra's algorithm
-* [[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
 <br>

@@ 第13行： / 第13行： @@
 == 定义==
-===步道 轨迹 路径 Walk, trail, path ===
+===通路 轨迹 路径 Walk, trail, path ===
 [[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'''是一条所有顶点（包括所有边）都是不同的轨迹。
-如果 ''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>的有限通路。同样，对于一条轨迹或者一条路径也是如此。如果两个不同的顶点之间有一个有限通路，那么在它们之间也有一条有限的轨迹和一条有限的路径。
@@ 第32行： / 第32行： @@
-一个'''加权图 weighted graph'''将一个值（权重）与图中的每条边相关联。一个加权图中的步道（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
+一个'''加权图 weighted graph'''将一个值（权重）与图中的每条边相关联。一个加权图中的通路（或轨迹或路径）的权是所有边的权之和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
 <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'''是指所有边都可见的轨迹。
@@ 第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>的步道。同样，对于有向轨迹或路径也是如此。如果在两个不同的顶点之间存在有限有向步道，那么在它们之间也存在有限有向轨迹和有限有向路径。
+假设一个通路 ''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”这两个词可以用来指代“权重”这一概念。
+一个加权有向图将一个值（权重）与有向图中的每条边相关联。加权有向图中有向通路（或路径）的权是有向边权重的和。有时，“成本 cost”或“长度 length”这两个词可以用来指代“权重”这一概念。
 <br>
@@ 第94行： / 第94行： @@
 * [[Bellman–Ford算法 Bellman–Ford algorithm]]
 * [[Floyd–Warshall算法 Floyd–Warshall algorithm]]
-* [[自我避免的步道 Self-avoiding walk]]
+* [[自我避免的通路 Self-avoiding walk]]
 * [[最短路径图Shortest-path graph]]
@@ 第115行： / 第115行： @@
 ==编者推荐==
-====[https://campus.swarma.org/course/2013 中介分析和路径因果效应（下）]====
+=== 课程推荐 ===
-本课程是“因果科学与Causal AI”读书会进行第四期的线上论文分享录像，主题是“中介分析和路径因果效应”，将由ThoughtWorks高级咨询师兼东南亚市场技术总监徐培以及辅仁大学心理系在读硕士原显智来进行分享。

@@ 第5行： / 第5行： @@
 [[File:Snake-in-the-box_and_Hamiltonian_path.svg|thumb|right|图1：一个三维的超立方体图表显示一个红色的[[哈密顿图]]，和一个黑色的[[最长诱导路径]]]]
-在[[图论 Graph theory]]中，图中的'''路径 path'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。'''有向图 directed path'''（有时也称为dipath<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>）中的有向路径，在具有附加条件：所有的边都方向相同时是一个有限或无限的边序列，它连接一系列不同的顶点。
+在[[图论 Graph theory]]中，图中的'''路径 path'''是一个有限或无限的边序列，这些边连接着一系列顶点，这些顶点在大多数定义中都是不同的(又因为这些顶点是不同的，所以图中的边也是不同的)。有向图中的'''有向路径 directed path'''（有时也称为dipath<ref>Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991, [https://books.google.com/books?id=idigH5CTGWAC&pg=PA205 p.205]</ref>），是一个有限或无限的边序列，它连接一系列不同的顶点，并具有附加一个条件：序列中所有的边都方向都相同。
@@ 第76行： / 第76行： @@
 <br>
-==  路径寻找==
+== 路径寻找==
 求解图的最短和最长路径有多种算法，但是前者的计算比后者简单得多。

←上一版本		2020年12月27日 (日) 14:58的版本
第113行：		第113行：

	* {{cite book \|last1=Korte \|first1=Bernhard \|last2=Lovász \|first2=László \|last3=Prömel \|first3=Hans Jürgen \|last4=Schrijver \|first4=Alexander \|date=1990 \|title=Paths, Flows, and VLSI-Layout \|url=https://archive.org/details/pathsflowsvlsila0000unse \|location= \|publisher=Springer-Verlag \|url-access=registration }}		* {{cite book \|last1=Korte \|first1=Bernhard \|last2=Lovász \|first2=László \|last3=Prömel \|first3=Hans Jürgen \|last4=Schrijver \|first4=Alexander \|date=1990 \|title=Paths, Flows, and VLSI-Layout \|url=https://archive.org/details/pathsflowsvlsila0000unse \|location= \|publisher=Springer-Verlag \|url-access=registration }}
		+
		+	==编者推荐==
		+	====[https://campus.swarma.org/course/2008 中介分析和路径因果效应（上）]====
		+	本课程是“因果科学与Causal AI”读书会进行第五期的线上论文分享录像，主题是“中介分析和路径因果效应(论文解读)”，将由毕业于北京大学数学学院陆怡舟以及北京大学数学科学学院在读博士胡文杰来进行分享。
		+
		+
		+	====[https://campus.swarma.org/course/2013 中介分析和路径因果效应（下）]====
		+	本课程是“因果科学与Causal AI”读书会进行第四期的线上论文分享录像，主题是“中介分析和路径因果效应”，将由ThoughtWorks高级咨询师兼东南亚市场技术总监徐培以及辅仁大学心理系在读硕士原显智来进行分享。
		+
		+
		+	====[https://campus.swarma.org/course/1052 注意力模型学习求解路径问题]====
		+	本课程来自集智第 38 期图网络论文解读活动。本文提出一种基于注意力机制的网络模型并通过REINFORCE算法训练网络来解决关于路径的组合优化问题，对于100个节点以内的旅行商问题来说取得了接近最优解的结果，该模型还能扩展到VRP（车辆路径问题）等问题。
		+
		+

←上一版本	2020年12月3日 (四) 15:57的版本
（没有差异）

@@ 第3行： / 第3行： @@
 |description=是一个有限或无限的边序列。
 }}
 [[File:Snake-in-the-box_and_Hamiltonian_path.svg|thumb|right|图1：一个三维的超立方体图表显示一个红色的[[哈密顿图]]，和一个黑色的[[最长诱导路径]]]]

@@ 第1行： / 第1行： @@
-本词条由Ryan初步翻译
+{{#seo:
-由CecileLi初步审校；于2020.11.19再次审校，若有遗漏敬请谅解。
+|keywords=路径，图论，顶点
 [[File:Snake-in-the-box_and_Hamiltonian_path.svg|thumb|right|图1：一个三维的超立方体图表显示一个红色的[[哈密顿图]]，和一个黑色的[[最长诱导路径]]]]
@@ 第115行： / 第117行： @@
 ----
-本中文词条由[[用户:嘉树|嘉树]]翻译，[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。
+本中文词条由[[用户:Ryan|Ryan]]翻译，[[用户:CecileLi|CecileLi]]审校，[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。
 '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''

@@ 第98行： / 第98行： @@
 <br>
-== References 引用==
+== 参考文献 ==
 {{Reflist}}
-* {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.fr/books?id=vaXv_yhefG8C |location= |publisher= |page= |isbn= |author-link= }}
+==其他链接==
-* {{cite book |last1=Bondy |first1=J. A. |last2=Murty |first2=U. S. R. |date=1976 |title=Graph Theory with Applications |url=https://archive.org/details/graphtheorywitha0000bond/page/12 |location= |publisher=North Holland |page=[https://archive.org/details/graphtheorywitha0000bond/page/12 12-21] |isbn=0-444-19451-7 |author-link= }}
+* {{cite book |last1=Bondy |first1=J. A. |last2=Murty |first2=U. S. R. |date=1976 |title=Graph Theory with Applications |url=https://archive.org/details/graphtheorywitha0000bond/page/12 |location= |publisher=North Holland |page=[https://archive.org/details/graphtheorywitha0000bond/page/12 12-21] |isbn=0-444-19451-7}}
 * {{cite book |last=Diestel |first=Reinhard |date=2005 |title=Graph Theory |url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ |location= |publisher=Springer-Verlag |page=6-9 |isbn=3-540-26182-6 |author-link= }}
-* {{cite book |last=Gibbons |first=A. |date=1985 |title=Algorithmic Graph Theory |url= |location= |publisher=Cambridge University Press |page=5-6 |isbn=0-521-28881-9 |author-link= }}
+* {{cite book |last=Gibbons |first=A. |date=1985 |title=Algorithmic Graph Theory |url= |location= |publisher=Cambridge University Press |page=5-6 | }}
-* {{cite book |last1=Korte |first1=Bernhard |last2=Lovász |first2=László |last3=Prömel |first3=Hans Jürgen |last4=Schrijver |first4=Alexander |date=1990 |title=Paths, Flows, and VLSI-Layout |url=https://archive.org/details/pathsflowsvlsila0000unse |location= |publisher=Springer-Verlag |page= |isbn=0-387-52685-4 |author-link= |url-access=registration }}
+* {{cite book |last1=Korte |first1=Bernhard |last2=Lovász |first2=László |last3=Prömel |first3=Hans Jürgen |last4=Schrijver |first4=Alexander |date=1990 |title=Paths, Flows, and VLSI-Layout |url=https://archive.org/details/pathsflowsvlsila0000unse |location= |publisher=Springer-Verlag |url-access=registration }}
-[[Category:Graph theory objects]]
+'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
-范畴: 图论对象
+[[Category:图论对象]]
+[[Category:图形连接性]]