コンテンツにスキップ

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

特徴的なグラフ[編集]

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」から取得