組合せ最適化 2.3 連結性 2.4 オイラーグラフと2部グラフ

Presentation on theme: "組合せ最適化 2.3 連結性 2.4 オイラーグラフと2部グラフ"— Presentation transcript:

1 組合せ最適化 2.3 連結性 2.4 オイラーグラフと2部グラフ
組合せ最適化 2.3 連結性 2.4 オイラーグラフと2部グラフ 岩間研究室M2　津山担当

2 2.3　連結性 ・連結性＝最も重要な概念 連結なグラフだけを考えれば十分な問題も多い。 (連結でない時は連結成分ごとに考えれば良い) (最大次数は？ k-彩色可能か？ 閉路はいくつ？ etc……） ・グラフの連結成分を検出するアルゴリズムを考える。

3 2.3　連結性 ・グラフ走査アルゴリズム [入力] 有向(or無向)グラフGと1点s [出力] sから到達可能な全ての点の集合Rと (R,T)がsを根とする有向木(or木)となるような 辺集合T⊆𝐸(𝐺) を具体的に考える。 以下、とりあえず 無向グラフで説明 (有向グラフも同様) s

4 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ s

5 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

6 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

7 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

8 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

9 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

10 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

11 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

12 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

13 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

14 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

15 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

16 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

17 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

18 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

19 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

20 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

21 2.3　連結性 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、②へ Q チェックすべき頂点集合 s

22 2.3　連結性 命題2.16：グラフ走査アルゴリズムは正しく動作する。 [証明(簡単に)] ・常に(R,T)はsを根とする有向木(or木)である。 (Tに追加される枝は常に新しい頂点に向けて張られる) ・アルゴリズムが出力したRに対して、sから 到達可能な点𝑤∈𝑉(𝐺)＼Rの存在を仮定すると？ 𝑥 𝑦 𝑤 ……　　　　　…… 　　　…… ∈𝑅 ∉𝑅 ∉𝑅 ・𝑥はQに一度入れられている ・Qが空になった時、アルゴリズムは停止する ・𝑦がR,Qに加えられる前に𝑥がQから 　除去されることはない！　　　　　→矛盾する s

23 2.3　連結性 ・ところで、「入力としてグラフを与える」とは？ 様々なグラフの表現方法(頂点数n、枝数mとする) Gの接続行列 ⋯ ⋮ ⋱ ⋮ ⋯ 頂点𝑖から枝𝑗が出る時 𝑖,𝑗 成分=1、他は0 辺1　辺2　辺3 … 辺(m-2)辺(m-1)辺m　 頂点1 頂点2 頂点3 … 頂点n

24 2.3　連結性 ・ところで、「入力としてグラフを与える」とは？ 様々なグラフの表現方法(頂点数n、枝数mとする) Gの接続行列(有向グラフの時) −1 1 0 ⋯ − ⋮ ⋱ ⋮ ⋯ 0 1 −1 頂点𝑖から頂点𝑖′に枝𝑗が出る時 𝑖,𝑗 成分=1、 𝑖′,𝑗 成分=−1、他は0 辺1　辺2　辺3 … 辺(m-2)辺(m-1)辺m　 頂点1 頂点2 頂点3 … 頂点n 各列で非0な要素はたったの2個で、 ほとんどの成分は0 接続行列を表現するために 𝑂 𝑚𝑛 の領域が必要(というか𝛩(𝑚𝑛)ね) →あまり効率的な表現方法ではない

25 2.3　連結性 隣接行列を表現するために 𝑂 𝑛 2 の領域で十分 →グラフがdenseな時、有効 →グラフがsparseな時、もっと良い表現方法がある！ dense……密　辺数がΘ( 𝑛 2 )とか？ sparse……疎　辺数が𝑂(𝑛)とか？ ・ところで、「入力としてグラフを与える」とは？ 様々なグラフの表現方法(頂点数n、枝数mとする) Gの隣接行列 ⋯ ⋮ ⋱ ⋮ ⋯ 頂点𝑖から頂点𝑗に枝が出る時 𝑖,𝑗 成分=1、他は0 出典：隣接行列 –Wikipedia- 点1　点2　点3 …点(n-2)点(n-1) 点n　 頂点1 頂点2 頂点3 … 頂点n

26 2.3　連結性 ・ところで、「入力としてグラフを与える」とは？ 様々なグラフの表現方法(頂点数n、枝数mとする) →たとえばそれぞれの辺の両端点のみ記憶すると？ 辺kの両端点が頂点 𝑖 𝑘 と頂点 𝑗 𝑘 の時に 𝑖 1 , 𝑗 1 , 𝑖 2 , 𝑗 2 ,… 𝑖 𝑘 , 𝑗 𝑘 ,…, 𝑖 𝑚−1 , 𝑗 𝑚−1 ,( 𝑖 𝑚 , 𝑗 𝑚 ) という形式でグラフを表現できる ・点を記憶するのに log 𝑛 ビット ・辺を記憶するのに2 log 𝑛 ビット ・グラフを表現するのには 　2𝑚 log 𝑛 =𝑂(𝑚 log 𝑛 )ビット mが小さい(グラフがsparseな)時、 少ない領域でグラフを表現できる →辺の順番を適当な順で保存されても 実用上不便過ぎる！ ある点に接続する辺が欲しい時は多い

27 2.3　連結性 ・ところで、「入力としてグラフを与える」とは？ 様々なグラフの表現方法(頂点数n、枝数mとする) Gの隣接リスト →それぞれの頂点に接続する辺のリストと、 それらリストへのポインターのリストも保存する (点 𝑣 1 ,点 𝑣 2 ,……,点 𝑣 𝑛−1 ,点 𝑣 𝑛 ) ・「これは2𝑚 log 𝑛 ビット 余分に領域を用意すれば 記憶できる」 → 2𝑚 log 𝑚 では？ 𝑚=Θ(𝑛)を仮定した？ 頂点を記憶する？ ただの勘違い？ ・隣接リストでグラフを表現するための総ビット 𝑂(𝑛 log 𝑚 +𝑚 log 𝑛 ) (辺 𝑒 11 ,辺 𝑒 12 ,辺 𝑒 13 ,……) (辺 𝑒 21 ,辺 𝑒 22 ,辺 𝑒 23 ,……) 　　　　　…… (辺 𝑒 𝑛1 ,辺 𝑒 𝑛2 ,辺 𝑒 𝑛3 ,……)

28 2.3　連結性 ・ところで、「入力としてグラフを与える」とは？ 今後、グラフが入力として与えられる時、 その隣接リストを受け取るものとして考える。 要するに？ 「指定された辺への操作」「指定された点への操作」 は定数時間で行える仮定の上で計算時間を議論する。 (指定された点の隣接リストのヘッダーにアクセスする、点から出る辺を適当に一つ選択する、指定された辺の端点を求める……)

29 2.3　連結性 以下、基本的に 𝑛,𝑚でそれぞれグラフの点数、辺数を(本書では)表す。 また、𝑛−1≤𝑚< 𝑛 2 の成立を仮定する。 （つまり、連結でかつ並列辺が存在しないと仮定する） グラフアルゴリズムの計算時間は𝑛, 𝑚をパラメーターに測定される。 𝑂(𝑚+𝑛)時間の計算時間のアルゴリズムは線形と呼ばれる。

30 2.3　連結性 命題2.17：グラフ走査アルゴリズムは𝑂(𝑚+𝑛)時間で走るよう実装できる。つまり連結成分は線形時間で求まる。 [証明(簡単に)] ・各点𝑥それぞれに対し、”現在の辺”を指すポインターを導入する。(初めはすべて最初の辺を指すor空) ・③でポインターは一つ前進し、リストの最後に達するとその点𝑥は集合Qから除去され、二度と入れられない。 ・全て除去されれば アルゴリズムは 正しく停止する →点数+辺数に比例！ ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 　If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}　　 　とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、 　②へ　　　　グラフ走査アルゴリズム(再掲)

31 2.3　連結性 ・③の中で追加される頂点の選ばれる順番が気になる →そもそも、②で頂点はどのように選ばれるのか？ ・深さ優先探索(Depth-First Search, DFS) Qに最後に入れられた𝑣∈𝑄を選ぶ ・幅優先探索(Breadth-First Search, BFS) Qに最初に入れられた𝑣∈𝑄を選ぶ それぞれの選び方により作られる木をそれぞれ 深さ優先探索木(DFS-tree)、幅優先探索木(BFS-tree) と呼ぶ。 ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 　If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}　　 　とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、 　②へ　　　　グラフ走査アルゴリズム(再掲) s s

32 2.3　連結性 命題2.18：幅優先探索木はsから到達可能なすべての点への最短パスを含む。それぞれの最短パスの長さ𝑑𝑖𝑠 𝑡 𝐺 (𝑠,𝑣)は線形時間で求められる。 [証明(それなりにちゃんと)] ・アルゴリズムの①に𝑙 𝑠 ≔0、④に𝑙 𝑤 ≔𝑙 𝑣 +1を加え、(𝐺,𝑠)に対してアルゴリズムを幅優先で実行する。 ・𝑣∈𝑅に対し常に𝑙 𝑣 =𝑑𝑖𝑠 𝑡 𝑅,𝑇 (𝑠,𝑣)の成立が明らか。 ・𝑣を現在走査中の 点とすると、 𝑙 𝑤 >𝑙 𝑣 +1となる 点𝑤はその時点でRに 存在しない。(∵幅優先) ①𝑅≔ 𝑠 ,𝑄≔ 𝑠 , 𝑇≔𝜙とする。 ②If 𝑄=𝜙 then 終了する else 𝑣∈𝑄を選ぶ ③𝑒={𝑣,𝑤}∈𝐸 𝐺 となる𝑤∈𝑉 𝐺 ＼Rを選択 　If そのような𝑤は存在しない then 𝑄≔𝑄＼{𝑣}　　 　とし、②へ ④𝑅≔𝑅∪ 𝑤 , 𝑄≔𝑄∪ 𝑤 , 𝑇≔𝑇∪{𝑒}とし、 　②へ　　　　グラフ走査アルゴリズム(再掲)

33 2.3　連結性 命題2.18：幅優先探索木はsから到達可能なすべての点への最短パスを含む。それぞれの最短パスの長さ𝑑𝑖𝑠 𝑡 𝐺 (𝑠,𝑣)は線形時間で求められる。 [証明(それなりにちゃんと)] ・アルゴリズム終了時点で𝑑𝑖𝑠 𝑡 𝐺 𝑠,𝑤 <𝑑𝑖𝑠 𝑡 𝑅,𝑇 (𝑠,𝑣) と なる点𝑤∈𝑅が存在すると仮定し、その中でも最もsから近い点𝑤について考える。 ・PをGの最短s-wパスとし、最後の枝𝑒={𝑣,𝑤}を考えると𝑑𝑖𝑠 𝑡 𝐺 𝑠,𝑣 =𝑑𝑖𝑠 𝑡 𝑅,𝑇 (𝑠,𝑣)かつ𝑒∉𝑇が成立。(∵ 𝑤の選び方) ・𝑙 𝑤 = 𝑑𝑖𝑠𝑡 𝑅,𝑇 𝑠,𝑤 > 𝑑𝑖𝑠𝑡 𝐺 𝑠,𝑤 = 𝑑𝑖𝑠𝑡 𝐺 𝑠,𝑣 +1= 𝑑𝑖𝑠𝑡 𝑅,𝑇 𝑠,𝑣 +1=𝑙 𝑣 +1が成立することになる。 𝑣除去の時点で𝑤はRに存在しないことが𝑒∉𝑇と矛盾。

34 2.3　連結性 ・この結果は最短パス問題に対するDijkstraのアルゴリズムからも導出できる。 →Dijkstraのアルゴリズムは辺に(非負の)重みを与えたグラフに対する幅優先探索の一般化(7.1節でやります) ・連結成分に続いて、有向グラフの強連結成分を求めるアルゴリズムを考える。 強連結成分……任意の二点間のパスが存在する。 →n回DFS/BFSすればいける！(愚直) →実は各辺を2回辿れば十分(線形)

35 2.3　連結性 ・強連結成分アルゴリズム [入力] 有向グラフG [出力] 各点の強連結成分を表す関数𝑐𝑜𝑚𝑝:𝑉 𝐺 →𝑁 𝑐𝑜𝑚𝑝 𝑎 =2 𝑐𝑜𝑚𝑝 𝑏 =2 𝑐𝑜𝑚𝑝 𝑐 =1 𝑐𝑜𝑚𝑝 𝑑 =3 𝑐𝑜𝑚𝑝 𝑒 =3 𝑐𝑜𝑚𝑝 𝑓 =2 𝑐𝑜𝑚𝑝 𝑔 =2 b a c g f d e

36 2.3　連結性 ①𝑅≔𝜙,𝑁≔0とする。 ②For すべての𝑣∈𝑉(𝐺) do: If 𝑣∉𝑅 then Visit1(𝑣) ③𝑅≔𝜙,𝐾≔0 とする。 ④ For 𝑖≔|𝑉 𝐺 | down to 1 do: If 𝜓 −1 𝑖 ∉𝑅 then 𝐾≔𝐾+1とし、Visit2( 𝜓 −1 𝑖 ) Visit1(𝑣) ①𝑅≔𝑅∪{𝑣}とする。 ② For 𝑣,𝑤 ∈𝐸(𝐺)となるすべての𝑤∈𝑉(𝐺)＼R do: Visit1(𝑤) ③𝑁≔𝑁+1, 𝜓( 𝑣 ≔𝑁, 𝜓 −1 𝑁 ≔𝑣とする。 Visit2(𝑣) ①𝑅≔𝑅∪{𝑣}とする。 ② For 𝑤,𝑣 ∈𝐸(𝐺)となるすべての𝑤∈𝑉(𝐺)＼R do: Visit2(𝑤) ③𝑐𝑜𝑚𝑝 𝑣 ≔𝐾とする。 ３ ６ ７ １ ４ ５ ２ ① ② ③ 番号の大きい頂点を根に、逆矢印で見てDFSを行う。 できた反有向木 ごとに𝑐𝑜𝑚𝑝値を 与える。 １ ２ ３ ４ ５ ６ ７ DFSを行い、 葉から順に番号を振る

37 2.3　連結性 定理2.19：強連結成分アルゴリズムはすべての 強連結成分を線形時間で正しく求める。 [証明(それなりにちゃんと)] ・計算時間が𝑂(𝑛+𝑚)なのは明らか。 ・同じ強連結成分中の頂点は、2回目の深さ優先探索森 において同じ反有向木に属するので同じ𝑐𝑜𝑚𝑝値になる。 ・𝑐𝑜𝑚𝑝 𝑢 =𝑐𝑜𝑚𝑝(𝑣)となる二点𝑢,𝑣が実際に同じ強連結成分に含まれることさえ言えばOK！ ３ ６ ７ １ ４ ５ ２ ① ② ③ １ ２ ３ ４ ５ ６ ７

38 2.3 連結性 定理2.19：強連結成分アルゴリズムはすべての 強連結成分を線形時間で正しく求める。 [証明(それなりにちゃんと)]
2.3　連結性 定理2.19：強連結成分アルゴリズムはすべての 強連結成分を線形時間で正しく求める。 [証明(それなりにちゃんと)] ・ 𝑢,𝑣それぞれから反有向木において到達できる頂点で 𝜓値最大の点をそれぞれ𝑟 𝑢 ,𝑟(𝑣)とする。 ・𝑐𝑜𝑚𝑝 𝑢 =𝑐𝑜𝑚𝑝(𝑣)なので、2回目の深さ優先探索森で同じ反有向木に属するため、その木の根𝑟=𝑟 𝑢 =𝑟(𝑣) ・𝜓 𝑟 ≥𝜓(𝑢)より、 𝑟=𝑢または1回目の深さ優先探索森はr-uパスを(同様にr-vパスも)含む。 ・rは反有向木の根なのでu-rパス、v-rパスも存在する。 ゆえにuからv、vからuが到達可能であり、二つは同じ強連結成分に属することが分かる。 ３ ６ ７ １ ４ ５ ２ ① ② ③ １ ２ ３ ４ ５ ６ ７

39 2.3　連結性 ・このアルゴリズムで、有向無閉路グラフ(Directed Acyclic Graph, DAG)のトポロジカル順序も求められる。 定義2.8[再掲] Gを有向グラフとする。任意の辺 𝑣 𝑖 , 𝑣 𝑗 ∈𝐸(𝐺)に対して𝑖<𝑗が成立するような点集合𝑉 𝐺 ={ 𝑣 1 , 𝑣 2 ,… 𝑣 𝑛 }の順序をGのトポロジカル順序(topological order)という。 命題2.9[再掲] 有向グラフがトポロジカル順序をもつ必要十分条件は、無閉路であることである。 ・各強連結成分を1点に縮約することで有向無閉路グラフが得られるが、各点の元の成分の𝑐𝑜𝑚𝑝値が実はその順序となっている。 ３ ６ ７ １ ４ ５ ２ ① ② ③ ① ② ③

40 2.3　連結性 定理2.20：強連結成分アルゴリズムは有向グラフGの 各強連結成分を1点に縮約して得られる有向グラフの トポロジカル順序を正しく求める。 [証明(さくっと)] ・ XとYを有向グラフGの二つの強連結成分とする。𝑥∈𝑋,𝑦∈𝑌に対して𝑐𝑜𝑚𝑝 𝑥 <𝑐𝑜𝑚𝑝 𝑦 かつ辺(𝑦,𝑥)が存在すると仮定して矛盾を導く。 ・2番目のDFSではYの最初の点が加えられる前にXの点はすべてRに加えられている。特に辺(𝑦,𝑥)が走査されている時𝑥∈𝑅かつ𝑦∉𝑅である。 ・するとKが増加する前に𝑦がRに加えられることになり、 𝑐𝑜𝑚𝑝 𝑥 <𝑐𝑜𝑚𝑝(𝑦)に反する。

41 2.3　連結性 ・k+1以上の頂点を持つ無向グラフにおいて 任意にk-1個の点を除いても連結である時 k-連結(k-connected)であると言い、k-1個の辺を除いても連結である時 k-辺連結(k-edge-connected)であると言う。 (3点以上のグラフが 2-連結(2-辺連結)な 必要十分条件は、関節点(橋)を持たないことである) グラフGが k-連結 であるような最大のkをGの点連結度(vertex-connectivity)と呼び、 k-辺連結であるような最大のkを辺連結度(edge-connectivity)と呼ぶ。 →連結なグラフは、1-連結(1-点連結)である →非連結なグラフは、点連結度(辺連結度)は0とする。

42 2.3　連結性 ・関節点を持たない極大な連結部分グラフ=ブロック ブロックは……極大な2-連結グラフor1本の橋or孤立点 2つのブロックは……高々1点のみを共有 2個以上のブロックに属する点は……関節点 (証明はしない)

43 2.3　連結性 ・関節点を持たない極大な連結部分グラフ=ブロック ブロックは……極大な2-連結グラフor1本の橋or孤立点 2つのブロックは……高々1点のみを共有 2個以上のブロックに属する点は……関節点 (証明はしない)

44 2.3　連結性 定義2.21 Gを(有向あるいは無向)グラフとする。 各 𝑃 𝑖 𝑖∈ 1,…,𝑘 に対して、 𝑃 𝑖 はパスであり 𝑃 𝑖 の両端点のちょうど2点のみが 𝑟 ∪𝑉 𝑃 1 ∪…∪𝑉( 𝑃 𝑖−1 )に属するか、 あるいは 𝑃 𝑖 は閉路でありかつちょうど1点のみが 𝑟 ∪𝑉 𝑃 1 ∪…∪𝑉( 𝑃 𝑖−1 )に属するような 系列𝑟, 𝑝 1 ,… 𝑃 𝑘 を用いてG= 𝑟 ,𝜙 + 𝑃 1 +…+ 𝑃 𝑘 と書け るとき、これをGの耳分解(ear-decomposition)という。 𝑘≥1かつ 𝑃 1 が3点以上からなる 閉路かつ 𝑃 2 ,…, 𝑃 𝑘 がすべてパス である時、耳分解はプロパー(proper)であると呼ぶ。

45 2.3　連結性 以下の2-連結グラフの華麗な構造定理を証明する。 定理2.22(Whitney[1932]) 無向グラフが2-連結である 必要十分条件は、プロパーな耳分解を持つことである。 [証明(割とちゃんと)] ・明らかに長さ3以上の閉路は2-連結である。 ・2-連結なGの𝑥≠𝑦なる二点を結ぶx-yパスを加えても 2-連結である。 ・よってプロパーな耳分解を持つグラフは2-連結である ので、十分性が示された。

46 2.3　連結性 以下の2-連結グラフの華麗な構造定理を証明する。 定理2.22(Whitney[1932]) 無向グラフが2-連結である 必要十分条件は、プロパーな耳分解を持つことである。 [証明(割とちゃんと)] ・ 2-連結グラフGの極大な単純部分グラフをG’とする。 ・明らかにG’も2-連結であり、すなわち閉路を含む。 単純であることから閉路の長さは3以上である。 ・Hをプロパーな耳分解を持つGの極大部分グラフとする。このようなHは存在する。 まずHは全点でないと仮定して ムジュンを導く。

47 2.3　連結性 以下の2-連結グラフの華麗な構造定理を証明する。 定理2.22(Whitney[1932]) 無向グラフが2-連結である 必要十分条件は、プロパーな耳分解を持つことである。 [証明(割とちゃんと)] ・Hが全点でない時、𝑥∈𝑉(𝐻)かつ𝑦∉𝑉(𝐻)となる辺𝑒= 𝑥,𝑦 ∈𝐸 𝐺 が存在する。(∵Gは連結) ・𝑧∈𝑉(𝐻){𝑥}を考える。𝐺−𝑥は連結であるため、y-zパスPを持つ。Pを𝑦から辿った時、𝑉(𝐻)に属する最初の点を𝑧′とする。 ・この時、 𝑃 𝑦, 𝑧 ′ +𝑒は耳として 加えられるため、極大性に反する。 𝑧 𝑦 𝑥 𝑧′

48 2.3　連結性 以下の2-連結グラフの華麗な構造定理を証明する。 定理2.22(Whitney[1932]) 無向グラフが2-連結である 必要十分条件は、プロパーな耳分解を持つことである。 [証明(割とちゃんと)] ・ Hは全点である。 ・𝐸(𝐺)＼E 𝐻 の各辺が仮に存在しても、それらは 耳として加えることができる。 ・したがってH=Gが得られるため、必要性が示された。

49 2.3　連結性 2-辺連結グラフと強連結グラフに対する同様の特徴付けについては演習問題17を参照されたい。 だそうな。 2.3 連結性 の内容はひとまずここまで。 やったこと ・隣接行列や隣接リストでグラフを表すと都合良さげ ・与えられた頂点を含む連結成分全点木を出すアルゴリズムは、線形で動く ・強連結成分を求めるアルゴリズムは、線形で動く →そして同時にトポロジカル順序も与える。 ・無向グラフが2-連結である必要十分条件は、プロパーな耳分解があること という華麗な結果

50 2.4　オイラーグラフと2部グラフ レオンハルト・オイラー (Leonard Euler ) 「オイラーは人類史上最も多くの 論文を書いた数学者であったと言 われ、彼の論文は5万ページを超え る全集にまとめられて1911年から 刊行され続けているが、その全集 は100年以上たった今日でも未だに 完結していない」 (出典：レオンハルト・オイラー –Wikipedia) そんなオイラーさんの29歳頃(若い！)の業績のお話。

51 このプレーゲル川に架かっている7つの橋を全て1度ずつ渡って、元の所に
2.4　オイラーグラフと2部グラフ ・みんな大好きケーニヒスベルクの橋の問題 　　　　　　　　　 [画像元：一筆書き - Wikipedia] 町の誰か ～これがグラフ理論のはじまりである～ このプレーゲル川に架かっている7つの橋を全て1度ずつ渡って、元の所に 戻ってくることはできるか？？？ できない

52 2.4　オイラーグラフと2部グラフ 定義2.23 グラフGの全ての辺を含む閉じたウォークをオイラーウォーク(Eulerian walk)という。 無向グラフGは全ての点の次数が偶数である時、オイラー(Eulerian)であると呼ばれる。 有向グラフGは全ての点𝑣∈𝑉(𝐺)で 𝛿 − 𝑣 =| 𝛿 + 𝑣 | である時、オイラーであると呼ばれる。

53 2.4　オイラーグラフと2部グラフ 定理2.24(Euler [1736], Hierholzer [1873]) 連結グラフGがオイラーウォークを持つための 必要十分条件は、Gがオイラーであることである。 [証明(適当)] ・必要性は明らかである。 ・十分性は具体的なアルゴリズムを与えることで示す。

54 2.4　オイラーグラフと2部グラフ ・Eulerのアルゴリズム [入力] 無向連結オイラーグラフ ∵連結であるか、オイラーであるかは線形時間で判定できるため、そうでない入力は拒否できる。有向グラフの場合のアルゴリズムは簡単な改変で得られる。 [出力]GのオイラーウォークW

55 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とする。𝐸 𝐺 ≔𝐸(𝐺){𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。 𝑣 1

56 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。 𝑣 1

57 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

58 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

59 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

60 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

61 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

62 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

63 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。

64 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。 𝑣 3 𝑣 1 𝑣 2 =𝑊

65 2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。 𝑣 2 𝑣 1 𝑣 3 𝑣 4 =𝑊 𝑣 5 =𝑊

66 ② If 𝛿 + 𝑥 =𝜙 then ④へ else 𝑒∈ 𝛿 + (𝑥)を選び𝑒=(𝑥,𝑦)とする
2.4　オイラーグラフと2部グラフ ① 𝑣 1 ∈𝑉(𝐺)を任意に選ぶ。𝑊≔𝐸𝑈𝐿𝐸𝑅 𝐺, 𝑣 1 を返す。 𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 1 ) ① 𝑊≔ 𝑣 1 , 𝑥≔ 𝑣 1 とする。 ② If 𝛿 𝑥 =𝜙 then ④へ else 𝑒∈𝛿(𝑥)を選び𝑒={𝑥,𝑦}とする ③𝑊≔𝑊,𝑒,𝑦かつ𝑥≔𝑦とし、𝐸 𝐺 ≔𝐸(𝐺)＼{𝑒}として②へ ④𝑊を系列 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 ,……, 𝑣 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 とする。 For 𝑖≔1 to 𝑘 do: 𝑊 𝑖 ≔𝐸𝑈𝐿𝐸𝑅(𝐺, 𝑣 𝑖 )とする ⑤𝑊≔ 𝑊 1 , 𝑒 1 , 𝑊 2 , 𝑒 2 ,……, 𝑊 𝑘 , 𝑒 𝑘 , 𝑣 𝑘+1 として、𝑊を返す。 𝑣 3 𝑣 2 𝑣 4 𝑣 1 =𝑊 =𝑊 有向グラフの場合は②を ② If 𝛿 + 𝑥 =𝜙 then ④へ else 𝑒∈ 𝛿 + (𝑥)を選び𝑒=(𝑥,𝑦)とする

67 2.4　オイラーグラフと2部グラフ 定理2.25：Eulerのアルゴリズムは正しく動作し、 計算時間は𝑂(𝑚+𝑛)である。 [証明(|𝐸 𝐺 |についての帰納法)] ・𝐸 𝐺 =𝜙の時は自明。 ・次数条件(全て偶数)の仮定より、④が実行される時は 𝑣 𝑘+1 =𝑥= 𝑣 1 が成立する。この時点で𝑊は閉ウォークであり、 𝑊を除いたグラフ𝐺′も次数条件を満たす。 ・各辺𝑒∈𝐸( 𝐺 ′ )に対して、𝑒と同じ連結成分に属する𝐺′の点 𝑣 𝑖 でその添え字𝑖が最小のものが存在する。 ・帰納法の仮定より、𝑒は 𝑊 𝑖 に属するため、⑤で構成される閉ウォーク𝑊は実際にオイラーウォークである。

68 2.4　オイラーグラフと2部グラフ オイラーでないグラフに対して辺を加えたり縮約したりしてオイラーグラフにすることも興味深い問題。 (cf. 中国人郵便配達問題,chinese postman problem) Gを無向グラフとして、FをV(G)の非順序対の族とする。 (𝑉 𝐺 , 𝐸 𝐺 ∪𝐹)がオイラーならば、Fは奇数ジョイン(odd join)と呼ばれる。 Gから各辺𝑒∈𝐹を順次縮約していって得られるグラフがオイラーならば、Fは奇数カバー(odd cover)と呼ばれる。

69 2.4　オイラーグラフと2部グラフ 定理2.26(Aoshima and Iri[1977])：Gを無向グラフとする。 (a)奇数ジョインは奇数カバーである (b)極小な奇数カバーは奇数ジョインである。 [(a)の証明] ・Fを奇数ジョインとし、Gから(𝑉 𝐺 ,𝐹)の連結成分を縮約 して得られるグラフをG’とする。 ・ (𝑉 𝐺 ,𝐹)の各連結成分は 奇数次数の点を偶数個持つ。 ⇒それらの成分を1つに縮約すると偶数次数の点になる。 ・一方、Fに含まれない点は元々偶数次数である。 ・したがって、グラフG’は偶数次数の点しか持たないため、Fは奇数カバーである。

70 2.4　オイラーグラフと2部グラフ 定理2.26(Aoshima and Iri[1977])：Gを無向グラフとする。 (a)奇数ジョインは奇数カバーである (b)極小な奇数カバーは奇数ジョインである。 [(b)の証明] ・Fを極小な奇数カバーとする。Fの極小性より、 (𝑉 𝐺 ,𝐹)は森である。各𝑣∈𝑉(𝐺)で 𝛿 𝐹 𝑣 ≡ 𝛿 𝐺 𝑣 (𝑚𝑜𝑑 2)であることを示せば十分である。 ・𝑣∈𝑉(𝐺)で 𝑣,𝑤 ∈𝐹となる点𝑤を含む 𝑉 𝐺 ,𝐹 −𝑣の連結成分を 𝐶 1 , 𝐶 2 ,……, 𝐶 𝑘 とする。 ・Fは森なので、𝑘=| 𝛿 𝐹 𝑣 |である。 𝑣

71 2.4　オイラーグラフと2部グラフ 定理2.26(Aoshima and Iri[1977])：Gを無向グラフとする。 (a)奇数ジョインは奇数カバーである (b)極小な奇数カバーは奇数ジョインである。 [(b)の証明] ・Fは奇数カバーなので、Gで𝑋≔𝑉 𝐶 1 ∪…∪𝑉 𝐶 𝑘 ∪{𝑣} を縮約すると偶数次数の点になるため、| 𝛿 𝐺 𝑋 |は偶数。 ・一方、Fの極小性より、( 𝑣,𝑤 ∈𝐹となる任意の𝑤に対して) 𝐹＼{{𝑣,𝑤}}は奇数カバーではないので、各𝑖に対して| 𝛿 𝐺 𝑉 𝐶 𝑖 |は奇数である。 X 𝑣

72 2.4　オイラーグラフと2部グラフ 定理2.26(Aoshima and Iri[1977])：Gを無向グラフとする。 (a)奇数ジョインは奇数カバーである (b)極小な奇数カバーは奇数ジョインである。 [(b)の証明] ・以上をまとめると、 𝛿 𝐹 𝑣 ≡ 𝛿 𝐺 𝑣 (𝑚𝑜𝑑 2)を示せば十分 𝑘=| 𝛿 𝐹 𝑣 | | 𝛿 𝐺 𝑋 |は偶数。 各𝑖に対して| 𝛿 𝐺 𝑉 𝐶 𝑖 |は奇数である。 ・ここで、 𝑖=1 𝑘 | 𝛿 𝐺 𝑉 𝐶 𝑖 | = 𝛿 𝐺 𝑋 + 𝛿 𝐺 𝑣 −2 𝐸 𝐺 𝑣 ,𝑉 𝐺 ＼X +2 1≤𝑖<𝑗≤𝑘 | 𝐸 𝐺 𝐶 𝑖 , 𝐶 𝑗 | より、 𝛿 𝐹 𝑣 ≡ 𝛿 𝐺 𝑣 (𝑚𝑜𝑑 2)が示される。 X 𝑣

73 2.4　オイラーグラフと2部グラフ ・オイラーグラフについてはまた12.2節でやります ・続いて2部グラフについて ・無向グラフの2分割(bipartition)とは、AとBがともに安定集合となるような点集合の分割𝑉 𝐺 =𝐴∪𝐵

74 2.4　オイラーグラフと2部グラフ ・オイラーグラフについてはまた12.2節でやります ・続いて2部グラフについて ・無向グラフの2分割(bipartition)とは、AとBがともに安定集合となるような点集合の分割𝑉 𝐺 =𝐴∪𝐵

75 2.4　オイラーグラフと2部グラフ ・2分割を持つ時、グラフは2部(bipartite)であると呼ぶ。 ・𝑉 𝐺 =𝐴∪𝐵, 𝐴 =𝑛, 𝐵 =𝑚かつ 𝐸 𝐺 = 𝑎,𝑏 :𝑎∈𝐴,𝑏∈𝐵 となるような単純な2部グラフを 𝐾 𝑛,𝑚 と書き、完全2部グラフと呼ぶ。 ・以後𝐺= 𝐴∪𝐵,𝐸 𝐺 と書いた時、2部グラフを表す … 𝑛 𝑚

76 2.4　オイラーグラフと2部グラフ 命題2.27(König[1916])：無向グラフGが2部グラフであるための必要十分条件は、Gが奇数長の閉路を持たない ことである。与えられた無向グラフGに対して、2分割か 奇数長閉路を求める線形時間アルゴリズムが存在する。 [証明] ・まず必要性を簡単に示す。(直観的には明らか) ・閉路 𝑣 1 , ……, 𝑣 𝑘 が存在し、 𝑣 1 ∈𝐴であると仮定する。 ・明らかに 𝑣 𝑖 ∈𝐴であることと𝑖が奇数であることは等価 であり、𝑘が奇数の時 𝑣 1 , 𝑣 𝑘 が共に𝐴に属することになるが、これは2分割になっていない。

77 2.4　オイラーグラフと2部グラフ 命題2.27(König[1916])：無向グラフGが2部グラフであるための必要十分条件は、Gが奇数長の閉路を持たない ことである。与えられた無向グラフGに対して、2分割か 奇数長閉路を求める線形時間アルゴリズムが存在する。 [証明] ・グラフは連結であると仮定する。 ・任意に点𝑠∈𝑉 𝐺 を選び(𝐺,𝑠)に幅優先探索を適用し、幅優先木T全ての点𝑣∈𝑉(𝐺)への距離を求める。 ・𝐴≔ 𝑣∈𝑉 𝐺 :𝑑𝑖𝑠 𝑡 𝐺 𝑠,𝑡 は偶数 , 𝐵=𝑉(𝐺)＼𝐴と 定義する。もし𝐺[𝐴]か𝐺[𝐵]に辺𝑒={𝑥,𝑦}が存在すれば、 T上でのx-yパスに𝑒をつなげた奇数長閉路が得られる。それが無ければこれは2分割を与えている。

78 2.4　オイラーグラフと2部グラフ 2.4 オイラーグラフと2部グラフ の内容はここまで。 やったこと ・オイラーウォークを持つ必要十分条件はオイラーであることであり、そのウォークは線形時間で求まる。 ・オイラーでないグラフをオイラーに変形するための奇数ジョイン、奇数カバーの概念があり、それらはある意味等価である。 ・2部グラフである必要十分条件は、奇数長閉路を持たないこと。その閉路または2分割は線形時間で求まる。

79 おわり