名称のあるグラフのギャラリー
特徴的なグラフ[編集]
Highly symmetric graphs[編集]
強正則グラフ[編集]
-
Paley graph of order 13
対称グラフ[編集]
-
The ラドグラフ
半対称グラフ[編集]
Graph families[編集]
完全グラフ[編集]
完全2部グラフ[編集]
-
-
, the utility graph
-
-
閉路グラフ[編集]
個の頂点を持つ閉路グラフはn-cycleと呼ばれで表される。
フレンドシップグラフ[編集]
フレンドシップグラフはn個の 閉路グラフC3 を一つの頂点で繋いで構成する。[2]
フラーレングラフ[編集]
グラフ理論においてフラーレンとは、3-正則平面グラフであって無限面を含めて全ての面が五角形または六角形であるもの。オイラーの多面体公式 V – E + F = 2(V, E, F はそれぞれ頂点数、辺数、面数)から、フラーレンにはちょうど12個の五角形と V/2–10 個の六角形がある。フラーレングラフは対応するフラーレン化合物のシュレーゲル図である。
-
20-fullerene (dodecahedral graph)
-
24-fullerene (Hexagonal truncated trapezohedron graph)
-
26-fullerene
-
60-fullerene (truncated icosahedral graph)
-
70-fullerene
同じ六角形の面の数で同型でないフラーレンを作るアルゴリズムがG. BrinkmannとA. Dressによって発表された。[3]
正多面体[編集]
4つの頂点の完全グラフは正四面体の骨格を形作る。このように超立方体グラフは正多面体の骨格を表している。
Truncated solids[編集]
スナーク[編集]
スナーク はブリッジを持たない立方体グラフのうち辺彩色に4色必要なものの総称である。最も小さいスナークグラフはピーターセングラフである。
-
Loupekine snark (first)
-
Loupekine snark (second)
星[編集]
星 Skは任意のkについて完全2部グラフ K1,kの総称である。S3は爪とも呼ばれる。
車輪グラフ[編集]
車輪グラフ Wnはn個の頂点を持ち、一つの頂点が(n − 1)-閉路グラフのすべての頂点と結ばれたものを言う。
出典[編集]
- ^ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
- ^ Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics, DS6, 1-58, January 3, 2007. [1].
- ^ Journal of Algorithms 23 (2): 345–358. (1997). doi:10.1006/jagm.1996.0806. MR1441972.