7,129
个编辑
更改
跳到导航
跳到搜索
第67行：
第67行： + − + − 相较之下，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为'''哈密顿环Hamiltonian cycle'''，确定其存在性的过程属于NP-完全问题。<ref>{{citation+ − | author = [[Richard M. Karp]] − | chapter = Reducibility Among Combinatorial Problems − | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf − | title = Complexity of Computer Computations − | editor = R. E. Miller and J. W. Thatcher − | publisher = New York: Plenum − | pages = 85–103 − | year = 1972}}.</ref> − 目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''奥尔定理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> + − + − − '''<font color="#ff8000"> 双圈覆盖猜想Cycle double cover conjecture</font>'''指出，对于每个无桥图，都存在一组简单环可以将图的每个边缘恰好覆盖两次。然而目前其是否成立（或找到反例）仍然是一个悬而未决的问题。<ref>{{citation − | last = Jaeger | first = F. − | contribution = A survey of the cycle double cover conjecture − | doi = 10.1016/S0304-0208(08)72993-1 − | pages = 1–12 − | series = North-Holland Mathematics Studies − | title = Annals of Discrete Mathematics 27 – Cycles in Graphs − | volume = 27 − | year = 1985}}.</ref>
→环覆盖图
== 环覆盖图 ==
== 环覆盖图 ==
'''莱昂哈德·欧拉 Leonhard Euler'''在1736年发表的关于'''柯尼斯堡七桥 Seven Bridges of Königsberg'''的论文后来被广泛认为是图论的起源。论文中，欧拉做出了以下证明：对于一个具有封闭行走路线的有限无向图，要求访问者恰好经过每条边一次。其充要条件是除了孤立的顶点（即，所有边都被两两顶点相连）之外，其他每个顶点都是偶数度。一旦该有向图满足能一次性访问所有边不重复的特征，那么它就具有强连接性，并且每个顶点的进入次数和离开次数必定相等。无论哪种情况，其访问轨迹均被称为欧拉环或欧拉环游。如果一个有限的无向图在其每个顶点上都具有偶数度，那么不管其是否相连，均有可能找到一组简单的环，使满足恰好覆盖该图的每个边一次：这即是'''<font color="#ff8000"> 维勃伦定理 Veblen's theorem</font>'''。<ref>{{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | 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 | author1-link=Oswald Veblen | 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>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。
相较之下，寻找覆盖每个顶点仅一次而不是覆盖连边的简单环问题要困难得多。这种环被称为'''哈密顿环 Hamiltonian cycle'''，确定其存在性的过程属于'''NP-完全问题'''。<ref>{{citation | author = Richard M. Karp | chapter = Reducibility Among Combinatorial Problems | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf | title = Complexity of Computer Computations | editor = R. E. Miller and J. W. Thatcher | publisher = New York: Plenum | pages = 85–103 | year = 1972}}.</ref>
目前诸多包含哈密顿环的相关图类研究被发表。其中一个例子是'''奥尔定理 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>
'''<font color="#ff8000"> 双圈覆盖猜想 Cycle double cover conjecture</font>'''指出，对于每个无桥图，都存在一组简单环可以将图的每个边缘恰好覆盖两次。然而目前其是否成立（或找到反例）仍然是一个悬而未决的问题。<ref>{{citation | last = Jaeger | first = F. | contribution = A survey of the cycle double cover conjecture | doi = 10.1016/S0304-0208(08)72993-1 | pages = 1–12 | series = North-Holland Mathematics Studies | title = Annals of Discrete Mathematics 27 – Cycles in Graphs | volume = 27 | year = 1985}}.</ref>
<br>
==根据环定义的图类 ==
==根据环定义的图类 ==