アルゴリスト

アルゴリズムについてのブログ

グラフの例 - グラフ理論入門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
    補グラフ

参考