2.1: オイラーグラフと中国人郵便配達問題 (すべての辺をたどる経路) 定義(オイラー回路):あるグラフに、全ての辺を 含む回路が存在するとき,その回路をオイラー 回路といい,オイラー回路を含むグラフ G を オイラーグラフという. H26 グラフ理論 ―第4回― 周遊性(すべての道をたどる方法, すべての都市をたどる方法) 1 定理2.1:グラフ G は連結で,|V(G)| ≥ 2とする. G がオイラーグラフであるための必要十分条件 は,G のすべての頂点が偶点であることである. オイラーグラフの例: 辺をアルファベット順にたどることで すべての辺を一度ずつ通ってもとの 頂点に戻ることが出来る 2 証明:(すべての頂点が偶点であればGは オイラーグラフであることの証明:十分条件). |V(G)|=n の帰納法.|V(G)|=1 のときはあきらか. |V(G)|=n のとき正しいと仮定. 定理1.9より G にはある閉路 C が存在する. グラフ H=G-C を考える. 証明:(G がオイラーグラフであるならば,すべて の点は偶点であることの証明:必要条件). v1,v2,…,vk ,v1をオイラー回路とすると,任意の vi (1≦ i ≦ k) に対して2本づつの辺 (vi-1,vi),(vi,vi+1) が存在する.したがって,vi が回路に現れる回数に 関係なく vi の次数は偶数である. C H=G-C G 3 4 1 アルゴリズム2.5 (オイラー回路発見法) 証明:(つづき) グラフ H=G-C も定理1.9の条件を満たすので, H にも回路 C’ が存在し,仮定より,それは オイラー回路である.G は連結なので,C と C’ は 少なくとも1つの頂点を共有している.したがって C’ に C を加えた G のオイラー回路が存在する. 入力:各点の次数が偶数で, |V(G)|≧2 の連結グラフ G. 出力:G のオイラー回路. 方法: (1)はじめの点 v∈ V(G) を適当に選ぶ. (2)v からの閉路 C をダイクストラ法 で計算する. (3)C がオイラーグラフでないなら,C に含まれる 点 v から始まる H=G-C の閉路を計算する. (4)C がオイラー回路になるまで(3)を続ける. CとHからGのオイラー回路 を構成できる C H G 5 アルゴリズム2.5の動作例 ダイクストラ法(最短経路発見)の応用 (1)最初の点を選ぶ(どれでもよい) グラフ中の最短経路を発見できるダイクストラ法を グラフ中の閉路を見つけることに応用できる ダイクストラ法で探索 6 合流を見つけると 1 6 2 5 8 10 3 閉路が見つかる 7 7 9 4 8 2 アルゴリズム2.5の動作例 アルゴリズム2.5の動作例 (2)その点から始まる閉路をダイクストラの 方法で求める. (2)その点から始まる閉路をダイクストラの 方法で求める. 1 1 6 2 7 5 8 10 3 6 2 5 9 8 10 4 7 3 9 4 9 アルゴリズム2.5の動作例 10 アルゴリズム2.5の動作例 (2)その点から始まる閉路をダイクストラの 方法で求める.C = ①-②-③-① (3) Cに含まれるある点vから始まるH=G-Cの閉路を 計算する.(太い線以外の部分がH) 1 1 6 2 5 3 2 8 10 6 7 5 9 8 10 3 4 11 7 9 4 12 3 アルゴリズム2.5の動作例 アルゴリズム2.5の動作例 (3) Cに含まれるある点vから始まるH=G-Cの閉路を 計算する.(太い線以外の部分がH) 1 6 2 1 7 5 8 10 3 (3) Cに含まれるある点vから始まるH=G-Cの閉路を 計算する.(太い線以外の部分がH) 新しい閉路:C = ①-②-③-①-④-⑤-① 6 2 5 9 8 10 4 7 3 9 4 13 アルゴリズム2.5の動作例 アルゴリズム2.5の動作例 (4) Cがオイラー閉路になるまで(すべての辺を含むまで) この動作を続ける. 次の閉路:C = ①②③①④②⑤③④⑤① 1 6 2 (4) Cがオイラー閉路になるまで(すべての辺を含むまで) この動作を続ける. オイラー閉路:C = ①②③①④②⑤③④⑤⑩⑨⑧⑦⑥⑩⑧⑥⑤① 1 7 5 8 10 3 14 6 2 5 9 8 10 4 3 15 7 9 4 16 4 半オイラーグラフ 半オイラーグラフの性質 系2.3:連結グラフ G が半オイラーグラフである ための必要十分条件は,Gの奇点の個数が2で あることである. すべての辺を1度ずつ通ることができるが,起点に 帰ることが出来ないグラフ 半オイラーグラフの例 証明の前半(半オイラーグラフ⇒奇点が2個) Gが半オイラーグラフならばオイラー小道がある. ここで,始点と終点以外は,そこに入って出ていく 辺が必ずペアになってあるので,始点と終点のみ が奇点となる. 17 18 2.2: ハミルトングラフと巡回セールスマン問題 (すべての頂点をたどる最短経路) 証明の後半(奇点の個数が2個⇒半オイラーグラフ) u, v を奇点とし,辺 e=(u,v) を G に加えた G+e を考える. G+e の頂点はすべて偶点なので, G+e はオイラーグラフである.u,v,w,…,u をその 回路とする.このとき v,w,…,u の部分は G の すべての辺をたどっているのでオイラー小道 である.すなわち,G は半オイラーグラフである. 19 各都市間に距離を定義 すべての都市を通る閉路で 最短のものを求める問題 (巡回セールスマン問題) グラフの頂点をすべてたど る閉路を求める問題 (ハミルトン閉路問題) 巡回セールスマン問題の例 http://www.infonet.co.jp/ueyama/ip/index.html 20 5 寄り道:ハミルトングラフの応用 ゼロ知識証明 自分が重要な情報を知っていることを, なんの情報も漏らすことなく相手に伝える仕組み ハミルトン閉路が存在するか否かを簡単に チェックする方法は知られていない. (NP-完全問題:しらみつぶしによる探索しか有効な 解法がないと信じられている問題の仲間) OK 0 or 1 この問題が難しいことを利用した暗号理論上の 重要な応用がある → ゼロ知識証明 (公開鍵暗号,デジタル署名,ユーザ認証など) 21 22 http://ja.wikipedia.org/wiki/ ゼロ知識証明の概略 ハミルトン閉路を用いたゼロ知識証明 V 洞窟の問題: ・Pは魔法の扉を開く言葉を知っている. ・Vはその言葉が本物ならば購入したい. ・Pは言葉そのものを教えることなく,自分の 情報が本物であることを伝える必要がある. P ゼロ知識証明のプロトコル (右図) ・Pは一人で扉の前まで行く ・VはランダムにA,Bの通路を指定する ・Pは指定された通路から出てくる 自分だけが答えを知っている 複雑なハミルトングラフを 作ることは易しい (同じグラフのコピー G,H を作る) Pが嘘つきの場合,n 回の試行すべてに偶然 成功する確率は (ほぼゼロと見なせる) 23 24 6 ハミルトン閉路を用いたゼロ知識証明 1 ゼロ知識証明によるユーザ認証 G d H 2 5 H あらかじめ複雑なグラフを作成し, 自分の認証用に登録する b c 4 P プロトコル 3 V は H のハミルトン閉路か G と H が同型であることの 証明をランダムに求める. e a P が正しく答えることができるのは G のハミルトン閉路を知っている 場合のみであり,G の情報について 何も漏らしていない. ゼロ知識証明による 安全な認証 V ユーザ 25 ハミルトン閉路問題の解析 遠隔サーバ 実際の認証は因数分解などの 困難性が用いられる 26 証明(背理法): 定理の条件を満たすが,ハミルトングラフでないグラフが 存在すると仮定し,G をそのようなグラフのうち極大なもの (それ以上辺を追加するとハミルトングラフになる)とする. 定義:すべての点を含む閉路をハミルトン閉路 といい,ハミルトン閉路を含むグラフをハミルトン グラフという. u,v を G の非連接点とし,e=(u,v) とする.グラフ G+e は, 仮定よりハミルトングラフであり,G はそうでないので, G+e のハミルトン閉路は必ず e を含む. C:u,w1,…,wp-2,v,u をその閉路とすると, u,w1,…,wp-2,v の部分は,G のすべての点を含む. ここで辺 (u,wi) が存在すれば辺 (wi-1,v) は存在しない ことが, 次のようにわかる. 定理2.10 G を位数 p≧3 のグラフとするとき,G の任意の非隣 接点 u,v に対して,deg u + deg v ≧p が成立するなら G はハミルトングラフである. この定理は, 辺の数(サイズ)が十分に大きければ そのグラフはハミルトン閉路を持つことを表している. ただし, これは十分条件に過ぎないことに注意. G 27 28 7 証明(つづき): なぜならば (u,wi) と (wi-1,v) がともに存在したならば G にハミルトン閉路 u,wi,…,wp-2,v,wi-1,…,w1,u が 存在し(図の矢印で示す道),仮定に反する. u w1 ハミルトングラフであることを簡単に確かめる (厳密ではない)手法 定理2.10と同じ証明によって以下の定理が導かれる (なぜならば,G がハミルトンなら G+(u,v) もハミルトン であることは自明で,逆は定理2.8の証明と同じ) v wi-1 wi wp-2 したがって,deg u +deg v ≦ p-2+1 =p-1 となり(右図)仮定に矛盾する. したがって最初の仮定が誤りとわかる。 u v p-2+1以下の辺しか 描くことができない 定理2.11: (J.A.ボンディ,V.シュバタル): G を位数 p≧3 以上のグラフとすると, deg u+deg v ≧ p を満たす G の非隣接点 u,v に 対して,G がハミルトングラフであることと G+(u,v)が ハミルトングラフであることは等価である. 29 deg u+deg v ≧ p を満たす非隣接点がなくなるまで これらを辺で結ぶ操作を繰り返すことによって 得られるグラフを G の閉包とよび C(G) と表す. 30 証明:辺 e1,…,en および f1,…,fm を加えること によって得られる閉包を G1,G2 とする. 任意の ei が G2 に含まれ,任意の fi が G1 に 含まれることを示せば G1=G2 となる. このことが成立しないと仮定する. 定理2.12:任意のグラフに対して,得られる 閉包はただ一つに定まる. 31 32 8 証明(つづき): すなわち ek が G2 の辺で ek+1=(u,v) がそうでない ような k が存在する.e1,…,ek までを加えたグラフを G3 とすると,G3 は G1 の部分グラフなので degG3 u+degG3 v ≧ p である.一方 G3 は G2 の 部分グラフでもあるので degG2 u+degG2 v ≧ degG3 u+degG3 v ≧ p. これは u,v が G2 で非連接である仮定に反する. 以上により次の結果を得る. 定理2.13 :グラフ G がハミルトングラフである ことと G の閉包がハミルトングラフであることは 同値である. 定理2.14:G の閉包が完全グラフならば G はハミルトングラフである. eの系列 G3 G +e1 +e2 +ek eとfが被っている部分 G1 +ek+1 fの系列 次回は,巡回セールスマン問題を高速にかつ近似的に解く アルゴリズムを解説する G2 33 34 9
© Copyright 2024 ExpyDoc