第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’ は
少なくとも１つの頂点を共有している．したがって
C’ に C を加えた G のオイラー回路が存在する．
入力：各点の次数が偶数で，
|V(G)|≧2 の連結グラフ G．
出力：G のオイラー回路．
方法：
（１）はじめの点 v∈ V(G) を適当に選ぶ．
（２）v からの閉路 C をダイクストラ法
で計算する．
（３）C がオイラーグラフでないなら，C に含まれる
点 v から始まる H=G-C の閉路を計算する．
（４）C がオイラー回路になるまで（３）を続ける．
CとHからGのオイラー回路
を構成できる
C
H
G
5
アルゴリズム2.5の動作例
ダイクストラ法(最短経路発見)の応用
（１）最初の点を選ぶ（どれでもよい）
グラフ中の最短経路を発見できるダイクストラ法を
グラフ中の閉路を見つけることに応用できる
ダイクストラ法で探索
6
合流を見つけると
1
6
2
5
8
10
3
閉路が見つかる
7
7
9
4
8
2
アルゴリズム2.5の動作例
アルゴリズム2.5の動作例
（２）その点から始まる閉路をダイクストラの
方法で求める．
（２）その点から始まる閉路をダイクストラの
方法で求める．
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の動作例
（２）その点から始まる閉路をダイクストラの
方法で求める．C = ①－②－③－①
（３） 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の動作例
（３） Cに含まれるある点vから始まるH=G-Cの閉路を
計算する．(太い線以外の部分がH)
1
6
2
1
7
5
8
10
3
（３） Cに含まれるある点vから始まるH=G-Cの閉路を
計算する．(太い線以外の部分がH)
新しい閉路：C = ①－②－③－①－④－⑤－①
6
2
5
9
8
10
4
7
3
9
4
13
アルゴリズム2.5の動作例
アルゴリズム2.5の動作例
（４） Cがオイラー閉路になるまで（すべての辺を含むまで）
この動作を続ける．
次の閉路：C = ①②③①④②⑤③④⑤①
1
6
2
（４） 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で
あることである．
すべての辺を１度ずつ通ることができるが，起点に
帰ることが出来ないグラフ
半オイラーグラフの例
証明の前半(半オイラーグラフ⇒奇点が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

Download Report