グラフの例 - グラフ理論入門2

空グラフ(null graph): 辺集合が空であるグラフ。
空グラフ
完全グラフ(complete graph) $K_n$ 辺の数は $\frac{1}{2}n(n-1)$
完全グラフ
閉路グラフ(cycle graph) $C_n$
閉路グラフ
道グラフ(path graph) $P_n$ 閉路から1つの辺を除去したもの
道グラフ
車輪(wheel) $W_n$ 閉路に点を1つ加えて他のすべての点と結んだもの
車輪
正則グラフ(regular graph): どの点の次数も同じグラフ。3次正則グラフで有名な例はPetersen graphがある https://en.wikipedia.org/wiki/Petersen_graph
ピータスングラフ
プラトングラフ(Platonic graph): 正多面体の頂点と辺から作られたグラフhttps://link.springer.com/article/10.1007/s40995-018-0646-1
プラトングラフ
二部グラフ: グラフの点集合をAとBに分割し、Gのすべての辺がAの点とBの点を結ぶようにしたグラフ $K_{r,s}$ 。Aの各点がBの各点とちょうど1本の辺で結ばれているなら完全2部グラフ(complete bipartite graph)という。r+sの点とrsの辺がある。
完全2部グラフ
単純グラフの補グラフ(complement) $\bar{G}$ 点集合 V(G)を持ち、2点が隣接するのはGにおけるそれらが隣接していないときかつそのときに限るような単純グラフのこと。https://commons.wikimedia.org/wiki/File:Complement_graph.svg
補グラフ