第4回 - Donald Home Page

2.1: オイラーグラフと中国人郵便配達問題
(すべての辺をたどる経路)
定義(オイラー回路):あるグラフに、全ての辺を
含む回路が存在するとき,その回路をオイラー
回路といい,オイラー回路を含むグラフ G を
オイラーグラフという.
H27 グラフ理論
―第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 の情報について
何も漏らしていない.
G
ゼロ知識証明による
安全な認証
V
ユーザ
25
寄り道:因数分解の困難性を用いたゼロ
知識証明の例(暗号化された通信)
実際の認証は因数分解などの
困難性が用いられる
問題:整数Z,mが与えられている。証明者Pはこの式を満た
す整数Tを知っており、それを検証者Vに証明したい
②
③
④
Pは乱数Rを生成し
をVへ送る
Vは1-bit b = 0 or 1 をランダムに選んでPに送る
Pは
をVへ送る
Vは
を確かめる
Pが本当にTを知っていれば (b=0のとき)

26
PとVの通信の例
①

遠隔サーバ
Pが本当にTを知っていれば (b=1のとき)
前提条件(因数分解の困難性)

mはできるだけ大きな素数の積で因数分解できない
例えばm=2107-1×2107-1=162259276829213363391578010288127×162259276829213363391578010288127

mとZだけからではTを求めることは困難である
Tを少しずつ増やしながら式を満たすTを求めることはできない(TとT2のmod mに関する類似性はない)

このような前提の元、Tの情報を漏らすことなくTを知っている
ことを証明する手続きを考える
27
よって④は成立する。
Pが偽物の場合、RとR2を送っている
だけなので、b=0と事前にわかっていれば
この質問には答えられる
よって④は成立する。
Pが偽物の場合、b=1が事前にわかっていれば
Xを適当な数に調整すれば④を成立させる
ことは可能
しかし、b=0 or 1は事前にわからないため、Tを知らないものが
n回の試行を成功させる確率は1/n以下
28
7
閑話休題:
証明(背理法):
定理の条件を満たすが,ハミルトングラフでないグラフが
存在すると仮定し,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 はハミルトングラフである.
この定理は, 辺の数(サイズ)が十分に大きければ
そのグラフはハミルトン閉路を持つことを表している.
ただし, これは十分条件に過ぎないことに注意.
29
証明(つづき):
なぜならば (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
30
v
p-2+1以下の辺しか
描くことができない
31
定理2.11: (J.A.ボンディ,V.シュバタル):
G を位数 p≧3 以上のグラフとすると,
deg u+deg v ≧ p を満たす G の非隣接点 u,v に
対して,G がハミルトングラフであることと G+(u,v)が
ハミルトングラフであることは等価である.
32
8
deg u+deg v ≧ p を満たす非隣接点がなくなるまで
これらを辺で結ぶ操作を繰り返すことによって
得られるグラフを G の閉包とよび C(G) と表す.
証明:辺 e1,…,en および f1,…,fm を加えること
によって得られる閉包を G1,G2 とする.
任意の ei が G2 に含まれ,任意の fi が G1 に
含まれることを示せば G1=G2 となる.
このことが成立しないと仮定する.
定理2.12:任意のグラフに対して,得られる
閉包はただ一つに定まる.
33
証明(つづき):
すなわち 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 で非連接である仮定に反する.
34
以上により次の結果を得る.
定理2.13 :グラフ G がハミルトングラフである
ことと G の閉包がハミルトングラフであることは
同値である.
定理2.14:G の閉包が完全グラフならば
G はハミルトングラフである.
eの系列
G3
G
+e1 +e2
+ek
eとfが被っている部分
G1
+ek+1
fの系列
次回は,巡回セールスマン問題を高速にかつ近似的に解く
アルゴリズムを解説する
G2
35
36
9