グラフ問題

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph LR
  1((1)) --- 2((2))
  2((2)) --- 3((3))
  2((2)) --- 4((4))
  3((3)) --- 1((1))
  3((3)) --- 4((4))
  4((4)) --- 1((1))

グラフは，ノード(頂点)と，それらを繋ぐエッジ(辺)からなる．このドキュメントでは，特に断りのない限りグラフのノード集合を\(V\)，辺集合を\(E\)とする．ノード数は\(|V|\)，辺数は\(|E|\)で表される．

グラフでよく出る単語

パス(道)

あるノードから始めて，いくつかの辺をたどって，あるノードにたどり着くまでのノードの列をパス(道)という．有向グラフの場合，向きに従ってたどる必要がある．

また，同じノードを2回通らないパスを単純パスといい，同じ辺を2回通らないパスを路(トレイル)という

閉路

あるノードから始めて，同じノードに戻ってくるパス(始点と終点が同じ路)を閉路という．

次数

あるノードについて，直接繋がっている辺の数を次数という．また，有向グラフでは，入ってくる辺の辺の数を入次数，出ていく辺の数を出次数という．

グラフの種類

無向/有向グラフ

上の図のグラフは辺に向きがなく，無向グラフと呼ばれる．一方で下の図ように辺に向きがあるグラフは有向グラフという．

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph LR
  1((1)) --> 2((2))
  2((2)) --> 3((3))
  2((2)) --> 4((4))
  3((3)) --> 1((1))
  3((3)) --> 4((4))
  4((4)) --> 1((1))

重み付きグラフ

下の図のように辺に重みがあるグラフを重み付きグラフという．一般的にノード間の距離や移動コストを表すことが多い．

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph LR
  1((1)) -- 10 --- 2((2))
  2((2)) -- 30 --- 3((3))
  2((2)) -- 50 --- 4((4))
  3((3)) -- 40 --- 1((1))
  3((3)) -- 70 --- 4((4))
  4((4)) -- 10 --- 1((1))

連結/非連結グラフ

グラフ上の任意の2ノード間がいくつかの辺をたどって到達可能である(任意の2ノード間にパスが存在する)ものを連結グラフ，そうでない下のようなグラフを非連結グラフという．

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph LR
  1((1)) --- 2((2))
  3((3)) --- 4((4))

単純/多重グラフ

今まで上で出てきたグラフは全て単純グラフである．下のグラフのように，自己ループや多重辺を含むグラフは多重グラフという．

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph LR
  1((1)) -- 多重辺 --- 2((2))
  1((1)) --- 2((2))
  2((2)) --- 3((3))
  2((2)) --- 4((4))
  3((3)) --- 1((1))
  3((3)) -- 自己ループ --- 3((3))
  3((3)) --- 4((4))
  4((4)) --- 1((1))

DAG

閉路を持たない有向グラフを**DAG(有向非巡回グラフ)**という．

プログラムでのグラフの持ち方

プログラム上でのグラフの持ち方は主に2つある．例えば，このような単純連結重み付きグラフの情報を持つ場合，下の2つのような持ち方がある．

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph LR
  1((1)) -- 10 --> 2((2))
  2((2)) -- 30 --> 3((3))
  2((2)) -- 50 --> 4((4))
  3((3)) -- 40 --> 1((1))
  3((3)) -- 70 --> 4((4))
  4((4)) -- 10 --> 1((1))

• 隣接行列: 任意の2頂点の辺の取得が\(O(1)\)でできるが，空間計算量が\(O(|V|^2)\)．

• 隣接リスト: 空間計算量が\(O(|V|+|E|)\)．