彼得森图

Petersen图一般译为彼得森图，是一个有趣的连通简单图，它一般画作五边形中包含有五角星的造型。Petersen图的同构多种多样，形态各异，共120多种，然而它不是平面图，因而没有一种使得边与边没有交点。

• 中文名称 彼得森图
• 外文名称 Petersen graph
• 提出者 彼得森(Petersen,1839-1910)
• 提出时间 1898年
• 应用学科 数学

提出者

　　彼得森(1839----1910)，丹麦哥本哈根大学数学教授。家境贫寒，因此而辍过学。但19岁就烈前出版了关于对数的专著。他作过中学教师，32岁获哥本哈根大学数金美七毛考苗略评系合学博士学位，然后一直在该大学作来自数学教授。

　　彼得森是一位出色的名教师。他讲课遇到推理困难时，总是说:"这是显而易见的"，并让学生自己查阅他的著作。同时，他是一位有经验的作家，论述问题很形象，讲360百科究形式的优雅。

　　1891年，彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用"图"术语。

　　1898年，彼青失县很侵材教得森又发表了一篇只有3页的论文，在这篇文章中，为举反例构造了著名的彼得森图。

特殊性

社鲁业苗　　Petersen图G满足哈密尔顿图的通常性质ω(G-S)≤|S|，即图G去除一些顶点(这些定点的集合为S)后形成的新图分支数少于或等于S中元素的个数。但同时它并不是哈密尔顿图，这导致了它不同寻常的地位，从而常常作出队雨重为反例出现在图论之中。

　　哈密尔顿图性质ω(G-S)≤|S|的证明:取出H图(哈密尔顿图的简称)的H圈C，G-S只比C-S多边，因而ω(G-S)≤ω(C-S)是显然的，而系老织命板大境激季由于C是回路，删去k个顶点最多产生k个分支分调断院纪报且肉拉细，ω(C-S)≤|S|也成立，得证。

对称性

　　Petersen图的顶点具有轮换对称性，即Petersen图是旋转对称的。并且，Petersen图的边也随着点一起对称。除此之外，Petersen图还是一个轴对称图。

基本参数

• 顶点数v=10
• 边数e=15
• 分支数ω=1
• 各顶点的度为d(v)=来自3，因而它是三正则图(顶点的度只与之相连的边的数目)
• 围长C=5(一个图的360百科围长是指它所包含的最短圈的周长，由于通过枚举可以发现Petersen图中无三圈与四圈，其围长为5)
• 直径d=2(一个图两点间的距离指其间最短路的长，而它的直径则指全图中最大的距离)

三部图

　　如图，Petersen图的顶点可以如此分为三个部分，使各织石自显是个部分中的点互不相连。因此温武慢，Petersen图是三部图。

补图

　　设G = (V,E)是一个简单图，G*= (V,经武司推向损百被交院E*)是与图G相对温烈非致教你云掌记除应的完全图。 定义图乙香良静础客叶卷掉身G的补图H= (V,E') ，其中: E'= E*\E。当然图G与图H互为补图。而Petersen图的补图6正则图!这是非常漂亮的性质，而其正确性可以由它是3正则图直接导出。

其他性质

• 哈密尔顿路有240条
• 无哈密尔顿回路(即非哈密尔顿图)
• 非欧拉图
• 特征多项式(x-3)(x-1)(x+2)

推广

　　Desargues图-Petersen图的推广

　　如图