グラフ探索＋分割統治法

グラフ探索
＋
分割統治法
グラフの諸概念
•
•
•
•
•
•
•
•
•
グラフとは(有限個の）点＝頂点と(有限個の）線=辺，エッジを結んだもの
頂点(vertex)，辺（edge)
隣接(adjacent）:1本のエッジの両端にある頂点は隣接している
近傍(neighbors)：隣接している頂点集合
路(path)：ある頂点から他の頂点に至る一連のエッジ
単純路(simple path)：同じ節点を2回以上使わない路
サイクル(cycle)：最初と最後が同じ節点である単純路．
ツリー(tree)：サイクルのないグラフ．
連結グラフ：拡張点から他の全ての頂点へのパスが必ず1つ以上あるグラフ
←→不連結グラフ
• 有向グラフ：エッジに方向性あがる←→無向グラフ
• 重み付きグラフ：エッジに重きがある場合
• ネットワーク：重み付き有向グラフ
オイラーの一筆書き定理
ロシアのケーニヒスベルグという町を流れる
プレーゲル川には、中央に島があって、その
島と川の両岸との間には７つの橋がかかって
いたという。
昔から、その町に住む人々が議論していた問
題は、「７つの橋すべてを、１つの橋を複数回
渡ることなくすべて渡り終えるような橋の渡り
方を見つけられるのか？」であった。
ケーニヒスベルグの橋
陸地を頂点，橋をエッジとすればどのようなグラフ表現になるか？
ケーニヒスベルグの橋のグラフ表現
（世界最初のグラフ応用例？）
• グラフの全ての辺をちょうど１回ずつ通って、
開始点に戻るような道をオイラー閉路という．
オイラー閉路が存在すれば、そのグラフを一
筆書きすることができる．
• Ｇがオイラー閉路を持つ
⇔
Ｇの全ての頂点に対して、繋がっている辺の
数は偶数本である
ケーニヒスベルグの橋のグラフ表現
（世界最初のグラフ応用例？）
別の橋のグラフ表現
別の橋のグラフ表現
グラフの適用事例
• 具象事物とそれらの接続関係を抽象的に表
現したものとしてグラフを利用する
• 物理的なつながり
町と道，都市と空路，Ｗｅｂ，．．．
• ビジネスプロセス，作業工程計画，．．．
グラフの表現
• グラフ→隣接行列で表現
A B
B
A
A
D
B
C
D
C
1
1
1
0
1
1
1
1
C
1
1
1
1
D
0
1
1
1
節点の分類と隣接節点の取り扱い
• 既に訪問した節点集合：Ｔ
• Ｔの隣接節点集合：Ｆ
• それ以外の節点集合：Ｕ
Ｆの選択方法によりグラフ探索が変わる
（１）深さ優先探索(DFS, Depth First Search)
（２）幅優先探索(BFS, Breadth First Search)
深さ優先探索,縦型探索ＤＦＳ
• 節点を辿れる限り深く探索し続ける
①出発点の隣接節点集合をリストＦに記録する
②リストＦの第一要素の節点aを選びaを訪れる
③aとaの隣接節点集合を置換する
（二重登録があればリストの後ろを削除する）
④Fの要素が空になるまで②と③を繰り返す
DFSの実行例
11
隣接節点集合F
7
1
12
4
2
3
4
8
13
1
2
5
5
6
3
9
7
14
6
8
9
10
10
15
DFSの実行例
11
訪問先隣接節点集合F
7
1
12
4
2
4
8
13
1
5
3
2
9
14
6
10
15
253
453
7853
幅優先探索，横型探索 BＦＳ
• 隣接節点を順次訪問し，横方向に節点を辿る
①出発点の隣接節点集合をリストＦに記録する
②リストＦの第一要素の節点aを選びaを訪れる
③リストFよりaを削除し，aの隣接節点集合をリ
ストFの最後に追加する
（二重登録があればリストの後ろを削除する）
④Fの要素が空になるまで②と③を繰り返す
BFSの実行例
11
隣接節点集合F
7
1
12
4
2
3
4
8
13
1
2
5
5
6
3
9
7
14
6
8
9
10
10
15
BFSの実行例
11
隣接節点集合F
7
1
12
4
2
5
3
8
13
1
5
3
2
9
14
6
10
15
253
534
34896
Divide&Conquer（分割統治法）
• 全体を部分に分割し，各部分を解き，その結
果を統合して解を得る方法
• 全体の問題構造と部分の問題構造が同型で
あり，再帰的（recursive)という．
• 再帰法：処理手順を自分自身を使って定義す
る方法．
階乗関数 f(n)=n! の再帰的定義
f(3)
3
f(2)
2
n=0 -> f(n)=1
n not =0 -> f(n)=n x f(n-1)
f(1)
1
f(0)
f(0)=1
最大値を再帰的に求める
アルゴリズム？
（通常はコストが大きいので使わない）
データ集合をS，データ数をｎ
n=1 → それが最大値
n=2 → ２数を比較して大きいほうが最大値
n>2 → Sを二分して（S1，S2)，S1とS2の最
大値を求める
再帰的図形：コッホ曲線
1.線分を３等分する
2.真中の部分を正三角形を埋め込んだ形に曲げる
３．できた4辺について，１と２の同じ操作を適用する
上記操作を繰り返し適用した結果得られる曲線
→コッホ曲線と呼ぶ
→ｎ回操作後の長さは？
→ｎ回操作後の面積は？
→どの部分を拡大しても同じ図形が現れる再帰的な図形
→自己相似性を持つ図形
→フラクタル
シルピンスキーのギャスケット？

Download Report