ピーターセングラフ
(ペテルセングラフ から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/03/26 02:10 UTC 版)
ピーターセングラフ(英: Petersen graph)またはペテルセングラフとは、10個の頂点と15個の辺からなる無向グラフである。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、ジュリウス・ピーターセンが3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した[1]。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた[2]。
- ^ Brouwer, Andries E., The Petersen graph
- ^ Kempe, A. B. (1886), “A memoir on the theory of mathematical form”, Philosophical Transactions of the Royal Society of London 177: 1–70, doi:10.1098/rstl.1886.0002
- ^ Cubic symmetric graphs (The Foster Census)
- ^ Holton, D. A.; Sheehan, J. (1993年), The Petersen Graph, Cambridge University Press, ISBN 0-521-43594-3, page 32.
- ^ Pegg, Ed, Jr. (2002年), “Book Review: The Colossal Book of Mathematics”, Notices of the American Mathematical Society 49 (9): 1084-1086.
- ^ Jakobson, Dmitry; Rivin, Igor (1999年), On some extremal problems in graph theory, arXiv:math.CO/9907050
- ^ Valdes, L. (1991年), “Extremal properties of spanning trees in cubic graphs”, Congressus Numerantium 85: 143-160
- 1 ピーターセングラフとは
- 2 ピーターセングラフの概要
- 3 ハミルトン路とハミルトニアン閉路
- 4 参考文献
- ピーターセングラフのページへのリンク