佩特森圖
外观
(重定向自彼得森图)
此條目没有列出任何参考或来源。 (2010年8月16日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Petersen_graph.svg/200px-Petersen_graph.svg.png)
彼得森圖是一个由10个顶点和15条边构成的无向图。其最为人熟知的造型为一个五边形内包含一个五角星。彼得森圖由丹麦哥本哈根大学数学教授Julius Peter Christian Petersen于1898年提出。由于其有趣的性质,它常常用于证明中的例子或反例。
性質
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Petersen_graph%2C_two_crossings.svg/220px-Petersen_graph%2C_two_crossings.svg.png)
- 強正則圖。
- 半徑同直徑均為2。
- 点连通度和线连通度均为3。
- 最大独立集的大小为4。
- 點色數為3,邊色數為4。
- 非平面圖:子圖有完全圖和完全雙分圖,交叉數為2。
- 有哈密頓路徑而無哈密顿圈。
- 的線圖的補圖。
最……
[编辑]- 最小無橋而邊色數大於3的三次圖(立方图)
- 最小無橋而沒有哈密爾頓圈的三次圖
- 最大半徑為2的三次圖
- 最小的hypohamiltonian圖(原本無哈密爾頓圈,但除去任何一個頂點,便可有哈密爾頓圈)
- 最小圍長為5的三次圖(唯一的-cage graph和唯一的-Moore graph。)
腳註
[编辑]