アルゴリスト

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

グラフとは - グラフ理論入門1

グラフ

  • 図のP,Q,R,S,Tはノードといい、それらを結ぶ線はエッジという。ノードとエッジを合わせてグラフという。エッジに方向がないグラフは無向グラフ、方向があるグラフは有向グラフという。エッジに重みを与える場合、重み付きグラフという。
  • ノードの次数とは、そのノードをつなぐエッジの本数のこと。
  • 2つのグラフがあるとき、片方のグラフで2点がエッジで結ばれるとき、他方のグラフの対応する2点がエッジで結ばれているとき、かつそのときに限り2つのグラフは同じ。
  • 2つの点を複数のエッジで結んでいるときは多重辺(multiple edges)と呼ぶ。1つの点をそれ自身とエッジで結ぶなら、ループと呼ぶ。多重辺やループを含まないグラフを単純グラフ(simple graph)という。
  • 歩道 (walk) はある点から別の点への行き方で、連結した辺の列で表せる。
  • どの点も高々1度しか現れない歩道は道 (path)という。始点と終点が一致する道は閉路(cycle)という。
  • すべての辺あるいはすべての点をちょうど1回ずつ通って始点に戻る歩道を含むグラフをそれぞれオイラーグラフ(Eulerian graph)、ハミルトングラフ(Hamiltonian graph)という。
  • 任意の2点が道で結ばれているグラフは連結グラフ(connected graph)といい、2つ以上のかたまりからなるなら非連結グラフ(disconnected graph)という。
  • 任意の2点の間に道が1本しかない連結グラフを木(tree)という。
  • 交差のない形に書き表せるなら平面的グラフ(planar graph)という。
  • 隣り合ったノードに別の色を塗るとして、何色使う必要があるかという問題を彩色問題という。平面的グラフであれば4色で塗れるが、これを4色定理(four-colour theorem)という。
  • 何人かの女性がそれぞれ何人かの男性を知っているとして、どの女性も知り合いの男性と結婚できる組み合わせを考えるための条件を探すという問題は結婚問題(marriage problem)という。
  • 結婚問題に関連して、グラフにおいて与えられた2点を結ぶ素な道を求める問題がある。
  • Pは工場、Rは市場、エッジは商品が送られるルートとする。各ルートには容量が与えられ、エッジの数字は通過可能な最大容量とする。このときの問題は、工場から市場まで最大でどれだけ送れるかである。

参考