名称のあるグラフのギャラリー

グラフ理論において、名前が付いたグラフの一覧を以下に示す。

特徴的なグラフ編集

Highly symmetric graphs 編集

強正則グラフ編集

対称グラフ編集

半対称グラフ編集

Graph families 編集

完全グラフ編集

$n$ 個の頂点を持つ完全グラフは $K_{n}$ と書かれる。^[1]

$K_{1}$
$K_{2}$
$K_{3}$
$K_{4}$
$K_{5}$
$K_{6}$
$K_{7}$
$K_{8}$

完全2部グラフ編集

$K_{2,3}$
$K_{3,3}$ , the utility graph
$K_{2,4}$
$K_{3,4}$

閉路グラフ編集

$n$ 個の頂点を持つ閉路グラフはn-cycleと呼ばれ $C_{n}$ で表される。

$C_{3}$
$C_{4}$
$C_{5}$
$C_{6}$

フレンドシップグラフ編集

フレンドシップグラフはn個の閉路グラフC₃ を一つの頂点で繋いで構成する。^[2]

The friendship graphs F₂, F₃ and F₄.

フラーレングラフ編集

グラフ理論においてフラーレンとは、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つの頂点の完全グラフは正四面体の骨格を形作る。このように超立方体グラフは正多面体の骨格を表している。

立方体
$n=8$ , $m=12$
正八面体
$n=6$ , $m=12$
正十二面体
$n=20$ , $m=30$
正二十面体
$n=12$ , $m=30$

Truncated solids 編集

スナーク編集

スナークはブリッジを持たない立方体グラフのうち辺彩色に4色必要なものの総称である。最も小さいスナークグラフはピーターセングラフである。

星編集

星 S_kは任意のkについて完全2部グラフ K_1,kの総称である。S₃は爪とも呼ばれる。

The star graphs S₃, S₄, S₅ and S₆.

車輪グラフ編集

車輪グラフ W_nはn個の頂点を持ち、一つの頂点が(n − 1)-閉路グラフのすべての頂点と結ばれたものを言う。

車輪グラフの例

W_{4}

–

W_{9}

.

出典編集

[脚注の使い方]

^ 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. MR 1441972.

「https://ja.wikipedia.org/w/index.php?title=名称のあるグラフのギャラリー&oldid=97746115」から取得