图距离 - 版本历史

Gyt666：Gyt666移动页面图距离 Distance (graph theory)至图距离覆盖重定向

2024-06-06T02:19:26Z

Gyt666移动页面图距离 Distance (graph theory)至图距离覆盖重定向

2024年6月6日 (四) 02:18 Gyt666

2024-06-06T02:18:36Z

Qige96：/* 相关概念 */

2021-01-21T09:17:15Z

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

2021-01-21T09:16:32Z

薄荷：薄荷移动页面图距离至图距离 Distance (graph theory)

2020-10-30T13:49:37Z

薄荷移动页面图距离至图距离 Distance (graph theory)

2020年10月30日 (五) 13:14 薄荷

2020-10-30T13:14:08Z

薄荷：/* 编者推荐 */

2020-10-30T09:47:53Z

编者推荐

薄荷：/* 参见= */

2020-10-30T09:15:17Z

参见=

2020年10月30日 (五) 09:13 薄荷

2020-10-30T09:13:37Z

薄荷：/* 寻找伪边缘点的算法 Algorithm for finding pseudo-peripheral vertices */

2020-10-30T09:13:07Z

寻找伪边缘点的算法 Algorithm for finding pseudo-peripheral vertices

@@ 第3行： / 第3行： @@
 |description=最短路径,图度量,中心顶点，边缘顶点。
 }}
-在'''[[图论 graph theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 shortest path'''（也称为'''<font color="#ff8000">图测地线 graph geodesic</font>'''）中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。<ref>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>但，两个顶点之间可能有不止一条最短路径。<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23|last=Weisstein |first=Eric W. |work=MathWorld--A Wolfram Web Resource |publisher= Wolfram Research|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}</ref>一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 connected components</font>'''，那么这两点间的距离就被定义为无穷大。
+图距离 （Distance (graph theory)） 在'''[[图论 graph theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 shortest path'''（也称为'''<font color="#ff8000">图测地线 graph geodesic</font>'''）中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。<ref>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>但，两个顶点之间可能有不止一条最短路径。<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23|last=Weisstein |first=Eric W. |work=MathWorld--A Wolfram Web Resource |publisher= Wolfram Research|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}</ref>一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 connected components</font>'''，那么这两点间的距离就被定义为无穷大。

@@ 第14行： / 第14行： @@
 一个由点集根据图中点集的距离定义的'''<font color="#ff8000">[[度量空间 metric space]]</font>'''被称为'''<font color="#ff8000">图度量 Graph Metric</font>'''。
-  --[[Ricky|用户:Qige96]] 是我公里太渣吗，我读不懂这句话啊......
+  --[[用户:Qige96|Ricky]] 是我功力太渣吗，我读不懂这句话啊......
 当且仅当图是连接的时，（无向图的）顶点集和距离函数构成度量空间。

@@ 第6行： / 第6行： @@
-在[[有向图 directed graph]]中，顶点 <math>u</math>和<math>v</math>之间的距离<math>d(u,v)</math>被定义为从<math>u</math> 到 <math>v</math>之间由弧组成的最短有向路径的长度，但前提是至少存在一条这样的路径。<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> 与无向图不同， <math>d(u,v)</math> 不一定与<math>d(v,u)</math>一致，而且可能一个是符合定义的，而另一个不符合。
+在'''<font color="#ff8000">有向图 directed graph</font>'''中，顶点 <math>u</math>和<math>v</math>之间的距离<math>d(u,v)</math>被定义为从<math>u</math> 到 <math>v</math>之间由弧组成的最短有向路径的长度，当然前提是这样的路径是存在的。<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> 与无向图不同， <math>d(u,v)</math> 不一定与<math>d(v,u)</math>一致，而且可能一个是符合定义的，而另一个不符合。
@@ 第14行： / 第14行： @@
 一个由点集根据图中点集的距离定义的'''<font color="#ff8000">[[度量空间 metric space]]</font>'''被称为'''<font color="#ff8000">图度量 Graph Metric</font>'''。
 当且仅当图是连接的时，（无向图的）顶点集和距离函数构成度量空间。
@@ 第40行： / 第41行： @@
-对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为'''<font color="#ff8000">测地图 geodetic graph</font>'''。例如，所有的树状图都是测地图。<ref>Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104</ref>
+若对于某个图，图中对于每对顶点，都有一条连接它们的唯一最短路径，则将该图称为'''<font color="#ff8000">测地图 geodetic graph</font>'''。例如，所有的树状图都是测地图。<ref>Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104</ref>
 <br>

@@ 第3行： / 第3行： @@
 |description=最短路径,图度量,中心顶点，边缘顶点。
 }}
-在'''[[图论 Graph Theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 Shortest Path'''（也称为'''<font color="#ff8000">图测地线 Graph Geodesic</font>'''）中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。<ref>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>但，两个顶点之间可能有不止一条最短路径。<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23|last=Weisstein |first=Eric W. |work=MathWorld--A Wolfram Web Resource |publisher= Wolfram Research|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}</ref>一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 Connected Components</font>'''，那么这两点间的距离就被定义为无穷大。
+在'''[[图论 graph theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 shortest path'''（也称为'''<font color="#ff8000">图测地线 graph geodesic</font>'''）中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。<ref>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>但，两个顶点之间可能有不止一条最短路径。<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23|last=Weisstein |first=Eric W. |work=MathWorld--A Wolfram Web Resource |publisher= Wolfram Research|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}</ref>一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 connected components</font>'''，那么这两点间的距离就被定义为无穷大。
@@ 第12行： / 第12行： @@
 ==相关概念==
-一个由点集根据图中点集的距离定义的度'''<font color="#ff8000">[[度量空间 metric space]]</font>'''被称为'''<font color="#ff8000">图度量 Graph Metric</font>'''。
+一个由点集根据图中点集的距离定义的'''<font color="#ff8000">[[度量空间 metric space]]</font>'''被称为'''<font color="#ff8000">图度量 Graph Metric</font>'''。
@@ 第18行： / 第18行： @@
-[[顶点]]<math>v</math>的'''<font color="#ff8000">离心率 Eccentricity</font>''' <math>\epsilon(v)</math>是它与其他顶点之间最大的距离，用<math>\epsilon(v) = \max_{u \in V}d(v,u)</math>表示。
+[[顶点]]<math>v</math>的'''<font color="#ff8000">离心率 eccentricity</font>''' <math>\epsilon(v)</math>是它与其他顶点之间最大的距离，用<math>\epsilon(v) = \max_{u \in V}d(v,u)</math>表示。
 这可以用来判断一个节点距离图中最远节点的距离。
@@ 第68行： / 第68行： @@
 ==编者推荐==
-===相关文章===
+===集智相关文章===
-====[https://swarma.org/?p=3128 自指机器的奥秘]====
+====[https://swarma.org/?p=20654 搭建图与网络之间的桥梁：网络科学的下一个突破在哪里？]====
-该文是冯·诺依曼自动机器理论”系列文章的第六篇（下半部分），由集智俱乐部资深粉丝“东方和尚”将全书第一部分翻译成中文，张江做了详细点评。
+网络是认识世界的强力手段，图论则是网络科学的数学基础，但两个领域近年来的结合并不密切。来自中欧大学的网络科学研究者，在Nature子刊Communications Physics上发表文章 Bridging the gap between graphs and networks，讨论如何将网络科学解决现实问题的经验引入图论运营，同时将图论中的前沿数学成果带入网络科学。在数据驱动下，架起图与网络之间的桥梁，网络科学将有机会迎来更大的突破。
-===集智相关课程===
 ====[https://campus.swarma.org/course/1169 图网络解决优化问题——图网络读书会]====
 图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。本系列课程为图网络论文解读活动“图网络解决优化问题”篇。

@@ 第76行： / 第76行： @@
 ===集智相关课程===
-====[https://campus.swarma.org/course/1128 层级与自指]====
+====[https://campus.swarma.org/course/1169 图网络解决优化问题——图网络读书会]====
-自复制只是自指的一种特例。而自指则是所有斑图想凭借自身演化翻身成为超越底层规则的唯一途径。阴阳二气并不会永无休止地争得个你死我活，而是会在一定阶段跃升进入无级之野。这也正是生命得以跃升进入更高层级的方式，它也将会指引人类如何超越奇点的唯一途径。该课程中，张江老师将介绍如何理解层级结构、虚拟层、哥德尔定理、自复制、自指。
+图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。本系列课程为图网络论文解读活动“图网络解决优化问题”篇。

←上一版本	2024年6月6日 (四) 02:19的版本
（没有差异）

←上一版本	2020年10月30日 (五) 13:49的版本
（没有差异）

@@ 第52行： / 第52行： @@
 # 如果<math>\epsilon(v) > \epsilon(u)</math>，那么令 <math>u=v</math> 并重复步骤2，否则 <math>u</math>是一个伪边缘点。
-=参见==
+==参见==
 * [[距离矩阵 Distance matrix]]
@@ 第67行： / 第67行： @@
-本词条由Ryan初步翻译
+====[https://swarma.org/?p=3034 自指——连接图形与衬底的金带]====
-由CecileLi初步审校
+该文是为“自指机器奥秘”的补充材料，详细地介绍了从语言到计算机程序再到数理逻辑等领域中各种形式的自指现象。除此之外，该文也详细指出了对角线删除法则与自指等概念之间的联系。
 [[Category:图论]]

@@ 第46行： / 第46行： @@
 ==寻找伪边缘点的算法  Algorithm for finding pseudo-peripheral vertices ==
-通常,外围[[稀疏矩阵 sparse matrix]]算法需要具有高离心率的起始点。外围顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，能轻松找到伪周边顶点:
+通常,外围[[稀疏矩阵 sparse matrix]]算法需要具有高离心率的起始点。边缘点会是首选，但往往难以计算。在大多数情况下，可以使用伪边缘点。通过以下算法，能轻松找到伪边缘点:
 # 选择顶点 <math>u</math>。
 # 在所有尽可能远离<math>u</math>的顶点中，让<math>v</math>是一个最小度的顶点。
-# 如果<math>\epsilon(v) > \epsilon(u)</math>，那么令 <math>u=v</math> 并重复步骤2，否则 <math>u</math>是一个伪周边顶点。
+# 如果<math>\epsilon(v) > \epsilon(u)</math>，那么令 <math>u=v</math> 并重复步骤2，否则 <math>u</math>是一个伪边缘点。
 =参见==