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

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

特徴的なグラフ

  • バラバン10-ケージ（英語版）
    バラバン10-ケージ（英語版）
  • バラバン11-ケージ（英語版）
    バラバン11-ケージ（英語版）
  • ビディアキキューブ（英語版）
    ビディアキキューブ（英語版）
  • ブリンクマングラフ（英語版）
    ブリンクマングラフ（英語版）
  • ブルグラフ（英語版）
    ブルグラフ（英語版）
  • バタフライグラフ（英語版）
    バタフライグラフ（英語版）
  • フバータルグラフ（英語版）
    フバータルグラフ（英語版）
  • ダイアモンドグラフ（英語版）
    ダイアモンドグラフ（英語版）
  • デューラーグラフ（英語版）
    デューラーグラフ（英語版）
  • Ellingham–Horton 54-graph
    Ellingham–Horton 54-graph
  • Ellingham–Horton 78-graph
    Ellingham–Horton 78-graph
  • Errera graph
    Errera graph
  • フランクリングラフ（英語版）
    フランクリングラフ（英語版）
  • フルフトグラフ（英語版）
    フルフトグラフ（英語版）
  • Goldner–Harary graph
    Goldner–Harary graph
  • Grötzsch graph
    Grötzsch graph
  • Harries graph
    Harries graph
  • Harries–Wong graph
    Harries–Wong graph
  • Herschel graph
    Herschel graph
  • ホフマングラフ（英語版）
    ホフマングラフ（英語版）
  • Holt graph
    Holt graph
  • Horton graph
    Horton graph
  • Kittell graph
    Kittell graph
  • Markström graph
    Markström graph
  • McGee graph
    McGee graph
  • Meredith graph
    Meredith graph
  • Moser spindle
    Moser spindle
  • Sousselier graph
    Sousselier graph
  • Poussin graph
    Poussin graph
  • Robertson graph
    Robertson graph
  • タットの小片
  • タットグラフ
  • Young–Fibonacci graph
    Young–Fibonacci graph
  • Wagner graph
    Wagner graph
  • Wiener–Araya graph
    Wiener–Araya graph

Highly symmetric graphs

強正則グラフ

  • Clebsch graph
    Clebsch graph
  • ピーターセングラフ
  • Hall–Janko graph
    Hall–Janko graph
  • Hoffman–Singleton graph
    Hoffman–Singleton graph
  • Higman–Sims graph
    Higman–Sims graph
  • Paley graph of order 13
    Paley graph of order 13
  • Shrikhande graph
    Shrikhande graph
  • Schläfli graph
    Schläfli graph
  • Brouwer–Haemers graph
    Brouwer–Haemers graph
  • Local McLaughlin graph
    Local McLaughlin graph
  • Perkel graph
    Perkel graph
  • Gewirtz graph
    Gewirtz graph

対称グラフ

  • ヒーウッドグラフ
  • メビウス-カントールグラフ（英語版）
    メビウス-カントールグラフ（英語版）
  • パップスグラフ（英語版）
    パップスグラフ（英語版）
  • デザルググラフ（英語版）
    デザルググラフ（英語版）
  • ナウルグラフ（英語版）
    ナウルグラフ（英語版）
  • コクセターグラフ（英語版）
    コクセターグラフ（英語版）
  • トゥッテ-コクセターグラフ（英語版）
    トゥッテ-コクセターグラフ（英語版）
  • ディックグラフ（英語版）
    ディックグラフ（英語版）
  • Klein graph
    Klein graph
  • フォスターグラフ（英語版）
    フォスターグラフ（英語版）
  • ビッグス-スミスグラフ（英語版）
    ビッグス-スミスグラフ（英語版）
  • The ラドグラフ（英語版）
    The ラドグラフ（英語版）

半対称グラフ

  • フォークマングラフ
  • グレイグラフ（英語版）
    グレイグラフ（英語版）
  • リュブリャナグラフ（英語版）
    リュブリャナグラフ（英語版）
  • トゥッテ12-ケージ（英語版）
    トゥッテ12-ケージ（英語版）

Graph families

完全グラフ

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

  • '"`UNIQ--postMath-00000003-QINU`"'
    K 1 {\displaystyle K_{1}}
  • '"`UNIQ--postMath-00000004-QINU`"'
    K 2 {\displaystyle K_{2}}
  • '"`UNIQ--postMath-00000005-QINU`"'
    K 3 {\displaystyle K_{3}}
  • '"`UNIQ--postMath-00000006-QINU`"'
    K 4 {\displaystyle K_{4}}
  • '"`UNIQ--postMath-00000007-QINU`"'
    K 5 {\displaystyle K_{5}}
  • '"`UNIQ--postMath-00000008-QINU`"'
    K 6 {\displaystyle K_{6}}
  • '"`UNIQ--postMath-00000009-QINU`"'
    K 7 {\displaystyle K_{7}}
  • '"`UNIQ--postMath-0000000A-QINU`"'
    K 8 {\displaystyle K_{8}}

完全2部グラフ

  • '"`UNIQ--postMath-0000000B-QINU`"'
    K 2 , 3 {\displaystyle K_{2,3}}
  • '"`UNIQ--postMath-0000000C-QINU`"', the utility graph
    K 3 , 3 {\displaystyle K_{3,3}} , the utility graph
  • '"`UNIQ--postMath-0000000D-QINU`"'
    K 2 , 4 {\displaystyle K_{2,4}}
  • '"`UNIQ--postMath-0000000E-QINU`"'
    K 3 , 4 {\displaystyle K_{3,4}}

閉路グラフ

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

  • '"`UNIQ--postMath-00000011-QINU`"'
    C 3 {\displaystyle C_{3}}
  • '"`UNIQ--postMath-00000012-QINU`"'
    C 4 {\displaystyle C_{4}}
  • '"`UNIQ--postMath-00000013-QINU`"'
    C 5 {\displaystyle C_{5}}
  • '"`UNIQ--postMath-00000014-QINU`"'
    C 6 {\displaystyle C_{6}}

フレンドシップグラフ

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

The friendship graphs F2, F3 and F4.

フラーレングラフ

グラフ理論においてフラーレンとは、3-正則平面グラフであって無限面を含めて全ての面が五角形または六角形であるもの。オイラーの多面体公式 V – E + F = 2（V, E, F はそれぞれ頂点数、辺数、面数）から、フラーレンにはちょうど12個の五角形と V/2–10 個の六角形がある。フラーレングラフは対応するフラーレン化合物のシュレーゲル図（英語版）である。

  • 20-fullerene (dodecahedral graph)
    20-fullerene (dodecahedral graph)
  • 24-fullerene (Hexagonal truncated trapezohedron graph)
    24-fullerene (Hexagonal truncated trapezohedron graph)
  • 26-fullerene
    26-fullerene
  • 60-fullerene (truncated icosahedral graph)
    60-fullerene (truncated icosahedral graph)
  • 70-fullerene
    70-fullerene

同じ六角形の面の数で同型でないフラーレンを作るアルゴリズムがG. BrinkmannとA. Dressによって発表された。[3]

正多面体

4つの頂点の完全グラフは正四面体の骨格を形作る。このように超立方体グラフは正多面体の骨格を表している。

  • 立方体 '"`UNIQ--postMath-00000015-QINU`"', '"`UNIQ--postMath-00000016-QINU`"'
    立方体
    n = 8 {\displaystyle n=8} , m = 12 {\displaystyle m=12}
  • 正八面体 '"`UNIQ--postMath-00000017-QINU`"', '"`UNIQ--postMath-00000018-QINU`"'
    正八面体
    n = 6 {\displaystyle n=6} , m = 12 {\displaystyle m=12}
  • 正十二面体 '"`UNIQ--postMath-00000019-QINU`"', '"`UNIQ--postMath-0000001A-QINU`"'
    正十二面体
    n = 20 {\displaystyle n=20} , m = 30 {\displaystyle m=30}
  • 正二十面体 '"`UNIQ--postMath-0000001B-QINU`"', '"`UNIQ--postMath-0000001C-QINU`"'
    正二十面体
    n = 12 {\displaystyle n=12} , m = 30 {\displaystyle m=30}

Truncated solids

  • Truncated tetrahedron
    Truncated tetrahedron
  • Truncated cube
    Truncated cube
  • Truncated octahedron
    Truncated octahedron
  • Truncated dodecahedron
    Truncated dodecahedron
  • Truncated icosahedron
    Truncated icosahedron

スナーク

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

  • Blanuša snark (first)
    Blanuša snark (first)
  • Blanuša snark (second)
    Blanuša snark (second)
  • Double-star snark
    Double-star snark
  • Flower snark
    Flower snark
  • Loupekine snark (first)
    Loupekine snark (first)
  • Loupekine snark (second)
    Loupekine snark (second)
  • Szekeres snark
    Szekeres snark
  • Tietze graph
    Tietze graph
  • Watkins snark
    Watkins snark

星

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

The star graphs S3, S4, S5 and S6.

車輪グラフ

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

車輪グラフの例 W 4 {\displaystyle W_{4}} – W 9 {\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.