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

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

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

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

特徴的なグラフ[編集]

Highly symmetric graphs[編集]

強正則グラフ[編集]

対称グラフ[編集]

半対称グラフ[編集]

Graph families[編集]

完全グラフ[編集]

個の頂点を持つ完全グラフと書かれる。[1]

完全2部グラフ[編集]

閉路グラフ[編集]

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

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

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

The friendship graphs F2, F3 and F4.

フラーレングラフ[編集]

In graph theory, the term フラーレン refers to any 3-regular, planar graph with all faces of size 5 or 6 (including the external face). It follows from Euler's polyhedron formula, V – E + F = 2 (where V, E, F indicate the number of vertices, edges, and faces), that there are exactly 12 pentagons in a fullerene and V/2–10 hexagons. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.

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

正多面体[編集]

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

Truncated solids[編集]

スナーク[編集]

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

[編集]

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

The star graphs S3, S4, S5 and S6.

車輪グラフ[編集]

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

車輪グラフの例 .

出典[編集]

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