![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/4/48/Petersen_graph_blue.svg/langja-640px-Petersen_graph_blue.svg.png&w=640&q=50)
ピーターセングラフ
ウィキペディア フリーな encyclopedia
ピーターセングラフ(英: Petersen graph)またはペテルセングラフとは、10個の頂点と15個の辺からなる無向グラフである。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、ジュリウス・ピーターセンが3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した[1]。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた[2]。
概要 ピーターセングラフ, 命名者 ...
ピーターセングラフ | |
---|---|
![]() 典型的なピーターセングラフ。五角形の中に五芒星形を描き、対応する各頂点を結ぶ。 | |
命名者 | ジュリウス・ピーターセン |
頂点 | 10 |
辺 | 15 |
半径 | 2 |
直径 | 2 |
内周 | 5 |
自己同型 | 120 (S5) |
彩色数 | 3 |
彩色指数 | 4 |
分数彩色指数 | 3 |
特性 |
正則グラフ 強正則グラフ スナークグラフ |
テンプレートを表示 |
閉じる
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Petersen_graph%2C_two_crossings.svg/320px-Petersen_graph%2C_two_crossings.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Petersen_graph%2C_unit_distance.svg/640px-Petersen_graph%2C_unit_distance.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Petersen_graph_2.svg/640px-Petersen_graph_2.svg.png)