有限幾何学　 　　　　　 第8回.

Presentation on theme: "　　　　有限幾何学　 　　　　　 第8回."— Presentation transcript:

1 　　　　有限幾何学　 　　　　　 第8回

2 有限幾何学　第8回 有向グラフと探索に関する木 用語の説明 応用例 強連結可能な向き付け 深さ優先探索（DFS）

3 1.1　用語の説明 グラフの向き付け：グラフの各辺に向きをつけること 有向グラフ：各辺に向きがつけられたグラフ グラフ G 　　　 有向グラフG

4 1.1 用語の説明 a f b g e h c a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの d
1.1　用語の説明 a f b g e h a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの 有向閉路：閉じた有向道 強連結な向き付け：相異なる任意の2頂点u,vに対して， 　　　　　　　　　　　　 u-v 有向道が存在するグラフの向き付け c d

5 1.1 用語の説明 a f b g e h c a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの d
1.1　用語の説明 a f b g e h a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの 有向閉路：閉じた有向道 強連結な向き付け：相異なる任意の2頂点u,vに対して， 　　　　　　　　　　　　 u-v 有向道が存在するグラフの向き付け c d

6 1.1 用語の説明 a f b g e h c a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの d
1.1　用語の説明 a f b g e h a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの 有向閉路：閉じた有向道 強連結な向き付け：相異なる任意の2頂点u,vに対して， 　　　　　　　　　　　　 u-v 有向道が存在するグラフの向き付け c d

7 1.1 用語の説明 a f b g e h c a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの d
1.1　用語の説明 a f b g e h a-b 有向道：a-b 道で各辺の向きが全てaからbへ向いているもの 有向閉路：閉じた有向道 強連結な向き付け：相異なる任意の2頂点u,vに対して， 　　　　　　　　　　　　 u-v 有向道が存在するグラフの向き付け c d

8 1.2 応用例 有向グラフの応用例①： PERT (Program Evaluation and Review Technique)：
1.2　応用例 有向グラフの応用例①： PERT (Program Evaluation and Review Technique)： 　スケジューリングの手法 　大規模なプロジェクトの日程管理などで用いられる 　PERTの手順　　 　1：1つのプロジェクトをいくつかの作業に分解 　2：作業の順序関係を 　　 重み付き有向グラフで表す（アローダイアグラム） 　3：作業にかかる時間等を見積もる

9 1.2 応用例 有向グラフの応用例①： PERT (Program Evaluation and Review Technique)：
1.2　応用例 有向グラフの応用例①： PERT (Program Evaluation and Review Technique)： 　スケジューリングの手法 　大規模なプロジェクトの日程管理などで用いられる 作業 先行作業 作業時間 A --- 9 B 3 C 8 D 4 E B,C 7 A B C D E 9 3 8 4 7

10 1.2 応用例 有向グラフの応用例②： トーナメント：向き付けされた完全グラフ 引き分けのないグループトーナメント（総当たり戦）表は
1.2　応用例 有向グラフの応用例②： トーナメント：向き付けされた完全グラフ 　　　　　　　　引き分けのないグループトーナメント（総当たり戦）表は 　　　　　　　　 トーナメントを用いて表すことができる v z w y x ＼ x y z v w ○ ×

11 1.2 応用例 有向グラフの応用例③： 全ての道路が一方通行になっている町の地図： 「町の任意の個所から他の任意の個所へ車で行けるように，
1.2　応用例 有向グラフの応用例③： 全ての道路が一方通行になっている町の地図： 「町の任意の個所から他の任意の個所へ車で行けるように， 道路地図に一方通行の制限を課せるのはどんなときか」 「グラフが強連結な向き付け可能であるのはどんなときか」

12 1.3 強連結な向き付け 問題 強連結な向き付け可能であるグラフを特徴づけよ 以下，
1.3　強連結な向き付け 強連結な向き付け可能であるグラフを特徴づけよ 以下， グラフが強連結な向き付け可能であるための必要十分条件を考える． 問題

13 1.3 強連結な向き付け 問題 強連結な向き付け可能であるグラフを特徴づけよ 「オイラーグラフ ⇒ 強連結な向き付け可能」は明らかだが，
1.3　強連結な向き付け 強連結な向き付け可能であるグラフを特徴づけよ 「オイラーグラフ ⇒ 強連結な向き付け可能」は明らかだが， 「オイラーグラフ ⇐ 強連結な向き付け可能」は成立しない 　　強連結な向き付け可能だがオイラーグラフではないグラフの例 問題

14 1.3 強連結な向き付け 問題 強連結な向き付け可能であるグラフを特徴づけよ 次に，条件「Gがオイラーグラフ」を弱めることで
1.3　強連結な向き付け 強連結な向き付け可能であるグラフを特徴づけよ 次に，条件「Gがオイラーグラフ」を弱めることで 必要十分条件が得られるかどうかを考えていく． どのようにして弱めるか？： Gがオイラーグラフ　 Gは連結グラフで，E(G)を互いに素な閉路に分割することができる を利用する． 問題

15 1.3 強連結な向き付け 問題 強連結な向き付け可能であるグラフを特徴づけよ
1.3　強連結な向き付け 強連結な向き付け可能であるグラフを特徴づけよ 「Gは連結グラフで，E(G)が互いに素な閉路に分割することができる」 を弱めた条件 「Gは連結グラフで，任意の辺がある閉路に含まれる」 はグラフが強連結な向き付け可能であるための必要十分条件か？ 問題

16 1.3 強連結な向き付け 問題 強連結な向き付け可能であるグラフを特徴づけよ 注意（提出課題）：
1.3　強連結な向き付け 強連結な向き付け可能であるグラフを特徴づけよ 注意（提出課題）： 「Gは連結グラフで，任意の辺がある閉路に含まれる」 「Gは連結グラフで，橋を含まない」 問題

17 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 注意： 「Gは連結グラフで，任意の辺がある閉路に含まれる」 「Gは連結グラフで，橋を含まない」

18 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか（提出課題） ．⇐を示す． 注意より， Gはある閉路G1を含む． 注意： 「Gは連結グラフで，任意の辺がある閉路に含まれる」 「Gは連結グラフで，橋を含まない」 G1

19 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 注意より， Gはある閉路G1を含む． G1≠Gならば右図のような辺eが存在する． e G1

20 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 注意より， Gはeを含むある閉路を含む． e G1

21 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 右図のようにグラフG2を選ぶ G2 G1

22 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 右図のグラフ≠Gならば 右図のような辺fが存在する． G2 f G1

23 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 注意より， Gはfを含むある閉路を含む． G2 f G1

24 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 右図のようにG3を選ぶ． G2 G1 G3

25 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下同様にしてG4,G5,・・・,Grを構成， 頂点集合が V(G1) ∪ V(G2) ∪‥∪ V(Gr)， 　 辺集合が E(G1) ∪ E(G2) ∪ ‥∪ E(Gr) のグラフがGとなるまで繰り返す． Gr G2 G1 G3

26 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下rに関する帰納法を用いる． r = 1 のときは明らか G1

27 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． r ≧ 2 のとき， Grを除いたグラフ（端点を除く）は 連結グラフで，任意の辺がある閉路に含まれる ∴ Grを除いたグラフは連結で橋を含まない． よって帰納法の仮定より， Grを除いたグラフは強連結な向き付けを持つ． Gr G2 G1 G3

28 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． E(Gr) には右図のように （Grに沿った）向き付けを与える （向きはどちらでもよい）． Gr G2 G1 G3

29 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下，次のことを示せばよい． ∀u ∈ V(G)-V(Gr), ∀v1,∀v2 ∈ V(Gr) に対して， (1) v1-v2 有向道が存在する， (2) v2-v1 有向道が存在する， (3) u-v1 有向道が存在する， (4) v1-u 有向道が存在する． v1 Gr v2 G2 u G1 G3

30 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下，次のことを示せばよい． ∀u ∈ V(G)-V(Gr), ∀v1,∀v2 ∈ V(Gr) に対して， (1) v1-v2 有向道が存在する， (1)は明らか． v1 Gr v2 G2 u G1 G3

31 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下，次のことを示せばよい． ∀u ∈ V(G)-V(Gr), ∀v1,∀v2 ∈ V(Gr) に対して， (2) v2-v1 有向道が存在する， GからGrを除いたグラフには w1-w2 有向道が存在する． これを用いて v2-v1 有向道を構成することができる． v1 Gr w2 v2 w1 G2 u G1 G3

32 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下，次のことを示せばよい． ∀u ∈ V(G)-V(Gr), ∀v1,∀v2 ∈ V(Gr) に対して， (3) u-v1 有向道が存在する， GからGrを除いたグラフには u-w1 有向道が存在する． これを用いて u-v1 有向道を構成することができる． v1 Gr w1 v2 G2 u G1 G3

33 強連結な向き付け可能なグラフの特徴づけ（ロビンス）
1.3　強連結な向き付け 強連結な向き付け可能なグラフの特徴づけ（ロビンス） グラフGに対して， 　Gが強連結な向き付け可能 　　　　　　Gが連結で橋を含まない 証明：⇒は明らか．⇐を示す． 以下，次のことを示せばよい． ∀u ∈ V(G)-V(Gr), ∀v1,∀v2 ∈ V(Gr) に対して， (4) v1-u 有向道が存在する． GからGrを除いたグラフには w2-u 有向道が存在する． これを用いて v1-u 有向道を構成することができる． v1 Gr v2 w2 G2 u G1 G3

34 1.4 深さ優先探索（DFS） ロビンスの定理より， 橋を持たない連結なグラフには 強連結な向き付けを与えられることが分かった．
次に，与えられた橋を持たない連結なグラフに 強連結な向き付けを与えるアルゴリズムを紹介する． 深さ優先探索(DFS)と呼ばれる頂点のラベル付けを 用いた強連結な向き付けの方法を紹介する．

35 1.4 深さ優先探索（DFS） DFSアルゴリズム ・全ての頂点を探索するアルゴリズム ・DFSはdepth-first-searchの略
・可能な限り深い所を先に探索する ・グラフの構造，性質を調べるときに有効な方法 ・グラフの連結性，連結成分，強連結成分，・・・等 ・入力：橋を持たない連結なグラフ G と始点 s ・出力：グラフGの全域木T（DFS木）と頂点のラベルn(u)

36 1.4　深さ優先探索（DFS） DFSアルゴリズム S 入力

37 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 出力 6 2 4 5 8 3 7

38 1.4 深さ優先探索（DFS） DFSアルゴリズム 手順1：n(u)=0 for∀u ∈ V(G)，i=0，T=s とする
手順2：DFS(s)を実行 手順3：終了 ---DFS(v) ---- 手順1： i=i+1，n(v)=i とする 手順2：Do while M={w ∈ NG(v)：n(w)=0} ≠ ∅ 　　　　　　w ∈ M を選び，T=T+vw とし DFS(w) を実行 　　　　　Loop 手順3：DFS(v)の終了

39 1.4　深さ優先探索（DFS） DFSアルゴリズム S

40 1.4　深さ優先探索（DFS） DFSアルゴリズム

41 1.4　深さ優先探索（DFS） DFSアルゴリズム 1

42 1.4　深さ優先探索（DFS） DFSアルゴリズム 1

43 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2

44 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2

45 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2 3

46 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2 3

47 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2 4 3

48 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2 4 3

49 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2 4 5 3

50 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 2 4 5 3

51 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 6 2 4 5 3

52 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 6 2 4 5 3

53 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 6 2 4 5 3 7

54 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 6 2 4 5 3 7

55 1.4　深さ優先探索（DFS） DFSアルゴリズム 1 6 2 4 5 8 3 7

56 DFSを用いた強連結な向き付けを与えるアルゴリズム
　強連結な向き付けを与えることができる ・入力：橋を持たない連結グラフ G ・出力：G の強連結な向き付け

57 DFSを用いた強連結な向き付けを与えるアルゴリズム
手順1：Gに対してDFSを実行する 手順2：∀e=uv ∈ E(G)，n(u) < n(v) に対し， 　　　　　次の向き付けを与える 　　　　　・e=uv ∈E(T) ならば e に u から v へと向き付けを与える 　　　　　・e=uv ∉ E(T) ならば e に v から u へと向き付けを与える

58 DFSを用いた強連結な向き付けを与えるアルゴリズム
1 6 2 4 5 8 3 7

59 提出課題8 問1： グラフGに対して， 「Gは連結グラフで，任意の辺がある閉路に含まれる」 ⇔ 「Gは連結グラフで，橋を含まない」 を示せ．
　　　⇔ 　　 「Gは連結グラフで，橋を含まない」 を示せ． 問2：グラフGに対して， 　 Gが強連結な向き付け可能　⇒　Gが連結で橋を含まない 　 を示せ．

60 提出課題8 問3：P.60 問3.13 問4：P.60 問3.15

61 提出課題8 問5 (提出しなくてもよいです)： 有向グラフGに対して， 全ての頂点を含む有向道が存在するとき，
　　　全ての頂点を含む有向道が存在するとき， 　　　Gは半ハミルトンであるという． 　　　全てのトーナメントは半ハミルトンであることを示せ． ヒント：頂点数に関する帰納法