更改

==  环覆盖图 ==

==  环覆盖图 ==

'''莱昂哈德·欧拉 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>'''，可以在多项式时间中找到覆盖每个边的最短闭合路径。