环 - 版本历史

Gyt666：Gyt666移动页面环 Cycle至环覆盖重定向

2024-06-03T07:44:09Z

Gyt666移动页面环 Cycle至环覆盖重定向

2024年6月3日 (一) 07:43 Gyt666

2024-06-03T07:43:52Z

薄荷：/* 编者推荐 */

2020-12-27T15:03:19Z

编者推荐

薄荷：/* 环覆盖图 */

2020-10-31T16:41:08Z

环覆盖图

薄荷：/* 无弦环 */

2020-10-31T16:39:52Z

无弦环

薄荷：/* 环覆盖图 */

2020-10-31T16:38:18Z

环覆盖图

薄荷：/* 环覆盖图 */

2020-10-31T16:37:45Z

环覆盖图

薄荷：/* 无弦环 */

2020-10-31T16:36:16Z

无弦环

2020年10月31日 (六) 16:33 薄荷

2020-10-31T16:33:26Z

2020年10月31日 (六) 16:32 薄荷

2020-10-31T16:32:28Z

@@ 第4行： / 第4行： @@
 }}
 [[文件:Graph cycle.svg|200px|thumb|right|这是一个经过着色的图，用于说明路径H-A-B（绿色），闭合路径或具有重复顶点的路径B-D-E-F-D-C-B（蓝色）和无重复边或顶点的环H-D-G-H（红色）。]]
-在[[图论 graph theory]]中，一个图中的'''环 Cycle'''是一个非空轨迹，其中唯一重复的点是起点和终点。一个[[有向图]]中的'''有向环 Directed cycle'''同样是非空有向迹线，其中唯一重复的点也是起点和终点。
+在[[图论 graph theory]]中，一个图中的'''环（ Cycle）'''是一个非空轨迹，其中唯一重复的点是起点和终点。一个[[有向图]]中的'''有向环 Directed cycle'''同样是非空有向迹线，其中唯一重复的点也是起点和终点。

@@ 第111行： / 第111行： @@
 == 编者推荐 ==
 [[File:巴拉巴西网络科学.jpeg|360px|缩略图|[https://campus.swarma.org/course/1754 巴拉巴西网络科学（课程）]]]
 ====[https://campus.swarma.org/course/1754 巴拉巴西网络科学（课程）]====
@@ 第118行： / 第116行： @@
+====[https://campus.swarma.org/course/855 知识图谱概述]====
+知识图谱是人工智能的一大技术驱动力，它能够广泛地应用于不同的任务。相比深度学习，知识图谱中的知识可以沉淀，可解释性非常强，类似于人类的思考。近年来，不管是学术界还是工业界都纷纷构建自家的知识图谱，有面向全领域的知识图谱，也有面向垂直领域的知识图谱。其实早在文艺复兴时期，培根就提出了“知识就是力量”，在当今人工智能时代，各大科技公司更是纷纷提出：知识图谱就是人工智能的基础。

←上一版本		2020年10月31日 (六) 16:41的版本
第67行：		第67行：
	== 环覆盖图 ==		== 环覆盖图 ==

−	'''莱昂哈德·欧拉 Leonhard Euler'''在1736年发表的关于'''柯尼斯堡七桥 Seven Bridges of Königsberg'''的论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为'''欧拉环'''或'''欧拉环游'''。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理 Veblen's theorem</font>'''。<ref>{{Citation \| last1=Veblen \| first1=Oswald \| title=An Application of Modular Equations in Analysis Situs \| jstor=1967604 \| series=Second Series \| year=1912 \| journal=Annals of Mathematics\| volume=14 \| issue=1 \| pages=86–94 \| doi = 10.2307/1967604 }}.</ref> 当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000">邮路问题 Route inspection problem</font>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。	+	'''莱昂哈德·欧拉 Leonhard Euler'''在1736年发表的关于'''柯尼斯堡七桥 Seven Bridges of Königsberg'''的论文后来被广泛认为是图论的起源。论文中，Euler做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为'''欧拉环'''或'''欧拉环游'''。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理 Veblen's theorem</font>'''。<ref>{{Citation \| last1=Veblen \| first1=Oswald \| title=An Application of Modular Equations in Analysis Situs \| jstor=1967604 \| series=Second Series \| year=1912 \| journal=Annals of Mathematics\| volume=14 \| issue=1 \| pages=86–94 \| doi = 10.2307/1967604 }}.</ref> 当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000">邮路问题 Route inspection problem</font>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。

←上一版本		2020年10月31日 (六) 16:39的版本
第33行：		第33行：


−	一个图中的'''<font color="#ff8000"> 边环 Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接；该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的，那么其边环肯定是导出环。	+	一个图中的'''<font color="#ff8000"> 边环 Peripheral cycle</font>'''具有以下性质：不在此边环上的两条连边可以通过一条特殊路径连接；该路径内部顶点均不在此边环上。如果一个图中的某条环不是通过添加一条边形成的，那么其边环肯定是诱导环。

	<br>		<br>

←上一版本		2020年10月31日 (六) 16:38的版本
第73行：		第73行：


−	目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''奥尔定理 Ore's theorem'''，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。<ref>{{citation\|first=Ø.\|last=~~Ore\|authorlink=Øystein~~ Ore\|title=Note on Hamilton circuits\|journal=American Mathematical Monthly\|volume=67\|year=1960\|page=55\|issue=1\|jstor=2308928\|doi=10.2307/2308928}}.</ref>	+	目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''奥尔定理 Ore's theorem'''，如果一个图中每个不相邻的顶点对的度数之和最少等于该图中顶点总数，那么该图中必然有哈密顿环。<ref>{{citation\|first=Ø.\|last=Ore\|title=Note on Hamilton circuits\|journal=American Mathematical Monthly\|volume=67\|year=1960\|page=55\|issue=1\|jstor=2308928\|doi=10.2307/2308928}}.</ref>

←上一版本	2024年6月3日 (一) 07:44的版本
（没有差异）

←上一版本		2020年10月31日 (六) 16:37的版本
第67行：		第67行：
	== 环覆盖图 ==		== 环覆盖图 ==

−	'''莱昂哈德·欧拉 Leonhard Euler'''在1736年发表的关于'''柯尼斯堡七桥 Seven Bridges of Königsberg'''的论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理 Veblen's theorem</font>'''。<ref>{{Citation \| last1=Veblen \| first1=Oswald \| title=An Application of Modular Equations in Analysis Situs \| jstor=1967604 \| series=Second Series \| year=1912 \| journal=Annals of Mathematics\| volume=14 \| issue=1 \| pages=86–94 \| doi = 10.2307/1967604 }}.</ref> 当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000">邮路问题 Route inspection problem</font>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。	+	'''莱昂哈德·欧拉 Leonhard Euler'''在1736年发表的关于'''柯尼斯堡七桥 Seven Bridges of Königsberg'''的论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为'''欧拉环'''或'''欧拉环游'''。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理 Veblen's theorem</font>'''。<ref>{{Citation \| last1=Veblen \| first1=Oswald \| title=An Application of Modular Equations in Analysis Situs \| jstor=1967604 \| series=Second Series \| year=1912 \| journal=Annals of Mathematics\| volume=14 \| issue=1 \| pages=86–94 \| doi = 10.2307/1967604 }}.</ref> 当一个连通图不满足欧拉定理的条件时，通过解决'''<font color="#ff8000">邮路问题 Route inspection problem</font>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。

←上一版本		2020年10月31日 (六) 16:36的版本
第27行：		第27行：

	[[文件:Graph with Chordless and Chorded Cycles.svg.png\|200px\|thumb\|right\|此图中的绿色环（A-B-C-D-E-F-A）是无弦的，而红色环（G-H-I-J-K-L-G）则是有弦的。因为连边K-I是弦。]]		[[文件:Graph with Chordless and Chorded Cycles.svg.png\|200px\|thumb\|right\|此图中的绿色环（A-B-C-D-E-F-A）是无弦的，而红色环（G-H-I-J-K-L-G）则是有弦的。因为连边K-I是弦。]]
−	一个图中的'''<font color="#ff8000"> 无弦环 Chordless cycles</font>'''（也可以称为'''<font color="#ff8000"> 孔 Hole</font>'''或'''<font color="#ff8000"> ~~导出环~~ Induced cycle</font>'''），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环i可用于表征'''<font color="#ff8000"> 完美图 perfect graphs</font>'''：通过'''强完美图定理 strong perfect graph theorem'''，当且仅当它的孔或反孔部分中无奇数（且大于3）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。	+	一个图中的'''<font color="#ff8000"> 无弦环 Chordless cycles</font>'''（也可以称为'''<font color="#ff8000"> 孔 Hole</font>'''或'''<font color="#ff8000"> 诱导环 Induced cycle</font>'''），指的是该环中没有两个顶点通过不属于该环的边相连。其反孔部分为此图孔的补图。无弦环i可用于表征'''<font color="#ff8000"> 完美图 perfect graphs</font>'''：通过'''强完美图定理 strong perfect graph theorem'''，当且仅当它的孔或反孔部分中无奇数（且大于3）个顶点时，图才是完美的。弦图是完美图的特殊形式，即没有任何长度大于三的孔。