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

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

特徴的なグラフ

•  

  (バラバン10-ケージ)（英語版）

•  

  (バラバン11-ケージ)（英語版）

•  

  (ビディアキキューブ)（英語版）

•  

  (ブリンクマングラフ)（英語版）

•  

  (ブルグラフ)（英語版）

•  

  (バタフライグラフ)（英語版）

•  

  (フバータルグラフ)（英語版）

•  

  (ダイアモンドグラフ)（英語版）

•  

  (デューラーグラフ)（英語版）

•  

  (Ellingham–Horton 54-graph)

•  

  (Ellingham–Horton 78-graph)

•  

  (Errera graph)

•  

  (フランクリングラフ)（英語版）

•  

  (フルフトグラフ)（英語版）

•  

  (Goldner–Harary graph)

•  

  (Grötzsch graph)

•  

  (Harries graph)

•  

  (Harries–Wong graph)

•  

  (Herschel graph)

•  

  (ホフマングラフ)（英語版）

•  

  (Holt graph)

•  

  (Horton graph)

•  

  (Kittell graph)

•  

  (Markström graph)

•  

  (McGee graph)

•  

  (Meredith graph)

•  

  (Moser spindle)

•  

  (Sousselier graph)

•  

  (Poussin graph)

•  

  (Robertson graph)

•  

  タットの小片

•  

  タットグラフ

•  

  (Young–Fibonacci graph)

•  

  (Wagner graph)

•  

  (Wiener–Araya graph)

Highly symmetric graphs

強正則グラフ

•  

  (Clebsch graph)

•  

  ピーターセングラフ

•  

  (Hall–Janko graph)

•  

  (Hoffman–Singleton graph)

•  

  (Higman–Sims graph)

•  

  (Paley graph) of order 13

•  

  (Shrikhande graph)

•  

  (Schläfli graph)

•  

  (Brouwer–Haemers graph)

•  

  (Local McLaughlin graph)

•  

  (Perkel graph)

•  

  (Gewirtz graph)

対称グラフ

•  

  ヒーウッドグラフ

•  

  (メビウス-カントールグラフ)（英語版）

•  

  (パップスグラフ)（英語版）

•  

  (デザルググラフ)（英語版）

•  

  (ナウルグラフ)（英語版）

•  

  (コクセターグラフ)（英語版）

•  

  (トゥッテ-コクセターグラフ)（英語版）

•  

  (ディックグラフ)（英語版）

•  

  (Klein graph)

•  

  (フォスターグラフ)（英語版）

•  

  (ビッグス-スミスグラフ)（英語版）

•  

  The (ラドグラフ)（英語版）

半対称グラフ

•  

  フォークマングラフ

•  

  (グレイグラフ)（英語版）

•  

  (リュブリャナグラフ)（英語版）

•  

  (トゥッテ12-ケージ)（英語版）

Graph families

完全グラフ

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

•  

  ${\displaystyle K_{1}}$ 

•  

  ${\displaystyle K_{2}}$ 

•  

  ${\displaystyle K_{3}}$ 

•  

  ${\displaystyle K_{4}}$ 

•  

  ${\displaystyle K_{5}}$ 

•  

  ${\displaystyle K_{6}}$ 

•  

  ${\displaystyle K_{7}}$ 

•  

  ${\displaystyle K_{8}}$ 

完全2部グラフ

•  

  ${\displaystyle K_{2,3}}$ 

•  

  ${\displaystyle K_{3,3}}$ , the (utility graph)

•  

  ${\displaystyle K_{2,4}}$ 

•  

  ${\displaystyle K_{3,4}}$ 

閉路グラフ

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

•  

  ${\displaystyle C_{3}}$ 

•  

  ${\displaystyle C_{4}}$ 

•  

  ${\displaystyle C_{5}}$ 

•  

  ${\displaystyle 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つの頂点の完全グラフは正四面体の骨格を形作る。このように(超立方体グラフ)は正多面体の骨格を表している。

•  

  立方体
  ${\displaystyle n=8}$ , ${\displaystyle m=12}$ 

•  

  正八面体
  ${\displaystyle n=6}$ , ${\displaystyle m=12}$ 

•  

  正十二面体
  ${\displaystyle n=20}$ , ${\displaystyle m=30}$ 

•  

  正二十面体
  ${\displaystyle n=12}$ , ${\displaystyle m=30}$ 

Truncated solids

•  

  (Truncated tetrahedron)

•  

  (Truncated cube)

•  

  (Truncated octahedron)

•  

  (Truncated dodecahedron)

•  

  (Truncated icosahedron)

スナーク

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

•  

  (Blanuša snark (first))

•  

  (Blanuša snark (second))

•  

  (Double-star snark)

•  

  (Flower snark)

•  

  Loupekine snark (first)

•  

  Loupekine snark (second)

•  

  (Szekeres snark)

•  

  (Tietze graph)

•  

  (Watkins snark)

星

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

 

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

車輪グラフ

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

 

車輪グラフの例 ${\displaystyle W_{4}}$  – ${\displaystyle W_{9}}$ .

出典

[脚注の使い方]

1. ^ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
2. ^ Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." (Electronic Journal of Combinatorics), DS6, 1-58, January 3, 2007. [1].
3. ^ Journal of Algorithms 23 (2): 345–358. (1997). doi:10.1006/jagm.1996.0806. MR1441972.