ノート04

Report
有限幾何学
第4回
有限幾何学 第4回
1. 中国人郵便配達人問題
1. 中国人郵便配達人問題
2. ハミルトングラフ
1. 用語の説明
2. ハミルトン閉路問題
1. 中国人郵便配達人問題
1.1. 中国人郵便配達人問題
右下図の様に3×3のブロックになっている街路がある.
郵便配達人はこの上の1点Pから出発し,
全ての道を通ってPに戻ってこなければならない.
同じ道を何回通ってもかまわないが,
郵便配達人としては,当然、最短で回りたい.
ブロックの1辺の長さを1とすると,
最短経路の長さは、いくつになるか?
「たけしのコマネチ大学数学科」より
P
1.1. 中国人郵便配達人問題
ヒント:
交差点と四つ角を頂点とみなし,
頂点間を歩くたびに辺でつなぐことによりグラフを構成する
P
1.1. 中国人郵便配達人問題
ヒント:
交差点と四つ角を頂点とみなし,
頂点間を歩くたびに辺でつなぐことによりグラフを構成する
P
1.1. 中国人郵便配達人問題
ヒント:
Pから出発し,Pに戻ってくるので,
構成されたグラフはオイラーグラフ
P
1.1. 中国人郵便配達人問題
ヒント:
オイラーの定理
G:位数2以上の連結グラフ
Gがオイラーグラフ
Gの全ての頂点の次数が偶数
P
1.1. 中国人郵便配達人問題
解答:
全ての道を通らなければならないので,
構成されるグラフは以下のグラフに幾つか辺を加えたものになる.
P
1.1. 中国人郵便配達人問題
解答:
構成されるグラフはオイラーグラフなので,
全ての頂点の次数が偶数.
次数が奇数の頂点は以下の赤い8頂点.
P
1.1. 中国人郵便配達人問題
解答:
次数が奇数の8頂点を偶数の次数にするには,
最低4辺の追加が必要で,次のように4辺追加することにより
全ての頂点の次数を偶数にすることができる.
P
1.1. 中国人郵便配達人問題
解答:
全ての頂点の次数が偶数なので,以下のグラフはオイラーグラフ.
グラフの構成の仕方より,以下のグラフのオイラー回路を
PからたどってPに戻ってくるのが最短経路となる.
P
1.1. 中国人郵便配達人問題
解答:
∴ 最短経路の長さ = 以下のグラフの辺の本数 = 28
P
1.1. 中国人郵便配達人問題
中国人郵便配達人問題
重み付きグラフの全ての辺を含む閉じた歩道で
重みが最小のものを求める問題
4 2
2
1
3
4
2
1
3
5
重み付きグラフ:
グラフの各辺eに重みと呼ばれる
実数値w(e)が割り当てられているグラフ
歩道の重み:歩道に含まれる辺の重みの総和
1.1. 中国人郵便配達人問題
中国人郵便配達人問題の解法
辺e=uvの2重化:頂点uとvを重みw(e)の新しい辺で
更に結ぶ操作
w(e)
w(e)
1.1. 中国人郵便配達人問題
中国人郵便配達人問題の解法
(1) 辺の2重化を何回か行い,
次の条件を満たすグラフG*を構成する.
(i) G*はオイラーグラフ
(ii) (i)のもとで ∑ w(e) が最小
e ∈ E(G*)-E(G)
(2) G*のオイラー回路を見つける
1.1. 中国人郵便配達人問題
中国人郵便配達人問題の解法
(1) 辺の2重化を何回か行い,
次の条件を満たすグラフG*を構成する.
(i) G*はオイラーグラフ
(ii) (i)のもとで ∑ w(e) が最小
e ∈ E(G*)-E(G)
(2) G*のオイラー回路を見つける
一般のグラフにおいて
効率よくG*を構成する方法は知られていない.
1.1. 中国人郵便配達人問題
中国人郵便配達人問題の解法
(1) 辺の2重化を何回か行い,
次の条件を満たすグラフG*を構成する.
(i) G*はオイラーグラフ
(ii) (i)のもとで ∑ w(e) が最小
e ∈ E(G*)-E(G)
(2) G*のオイラー回路を見つける
奇点を丁度2つ持つグラフに対しては
効率よくG*を構成することができる
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
入力:奇点を丁度2つ持つ連結な重み付きグラフ
出力:中国人郵便配達人問題の解
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
手順1:2個の奇点間の重み最小の道を求める
手順2:手順1で求めた道上の辺を2重化する
手順3:手順2で得られたグラフのオイラー回路を求める
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
1
3
2
4
u
3
2
v
辺の2重化を行いオイラーグラフにする.
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
1
3
2
4
u
3
2
v
無駄のない辺の2重化を行うと,
追加された辺を用いて
構成されるグラフは u-v 道になる.
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
u
u (奇点)から辺の2重化をスタートし,次々に辺の2重化を行う
無駄のない辺の2重化を行うと,
追加された辺を用いて
構成されるグラフは u-v 道になる.
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
⇐ ここが無駄,2重化する必要がない
u
一度通った頂点に戻るのは無駄のある辺の2重化となる
無駄のない辺の2重化を行うと,
追加された辺を用いて
構成されるグラフは u-v 道になる.
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
v
u
辺の2重化は次の奇点 v まで続く
無駄のない辺の2重化を行うと,
追加された辺を用いて
構成されるグラフは u-v 道になる.
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
3
1 1
3
2
4
u
3
2
v
uとvを結ぶ重みが最小の道を探す
注意:重み最小の u-v 道は効率よく求めることができる
(ダイキストラのアルゴリズム)
1.1. 中国人郵便配達人問題
奇点を丁度2つ持つグラフの
中国人郵便配達人問題の解法
アルゴリズムの説明
3
1 1
3
2
4
u
3
2
v
オイラーグラフのオイラー回路は
効率よく求めることができる(フラーリのアルゴリズム)
2. ハミルトングラフ
2.1 用語の説明
ハミルトン閉路: グラフの全ての頂点を含む閉路
ハミルトングラフ:ハミルトン閉路をもつグラフ
ハミルトン道:
グラフの全ての頂点を含む道
2.1 用語の説明
ハミルトングラフ
ハミルトングラフではないが
ハミルトン道を含むグラフ
2.1 用語の説明
注意
ハミルトン閉路:グラフの全ての頂点を含む閉路
各頂点を一度だけ通る
オイラー回路: グラフの全ての辺を含む回路
同じ頂点を何度通ってもよい
各辺を一度だけ通る
2.2 ハミルトン閉路問題
ハミルトン閉路問題
与えられたグラフが
ハミルトングラフであるかどうかを調べる問題
グラフがハミルトングラフであるための
必要十分条件は知られていない
注意:オイラーグラフであるための必要十分条件は
全ての頂点の次数が偶数であること
2.2 ハミルトン閉路問題
ハミルトン閉路問題
与えられたグラフが
ハミルトングラフであるかどうかを調べる問題
効率よく最適解を求めるアルゴリズムは知られていない
注意:オイラーグラフであるかどうかの判定は簡単
∵全ての頂点の次数が
偶数であるかどうかを調べればよい
2.2 ハミルトン閉路問題
ハミルトン閉路問題
与えられたグラフが
ハミルトングラフであるかどうかを調べる問題
グラフがハミルトングラフであるための
必要条件と十分条件に関して盛んに研究がなされている
ハミルトン閉路問題に関連した
アルゴリズムの研究が盛んになされている
2.2 ハミルトン閉路問題
ハミルトン閉路問題
与えられたグラフが
ハミルトングラフであるかどうかを調べる問題
関連する問題:
巡回セールスマン問題
重み付きグラフにおいて
重みが最小のハミルトン閉路を求める問題
2.2 ハミルトン閉路問題
次のハミルトングラフの特徴は,
グラフがハミルトングラフではないことを調べる際に役に立つ
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,k(G-S) ≦|S|
k(G-S):GからSを取り除いてできるグラフの連結成分の数
2.2 ハミルトン閉路問題
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,k(G-S) ≦|S|
証明:C:Gのハミルトン閉路
S:空ではない S⊆V(G) とする.
このとき,
k(C-S) ≦|S|.
C
2.2 ハミルトン閉路問題
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,k(G-S) ≦|S|
証明:C:Gのハミルトン閉路
S:空ではない S⊆V(G) とする.
このとき,
k(C-S) ≦|S|.
C
2.2 ハミルトン閉路問題
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,k(G-S) ≦|S|
証明:C:Gのハミルトン閉路
S:空ではない S⊆V(G) とする.
このとき,
k(C-S) ≦|S|.
C-SはG-Sの全域部分グラフなので,
k(G-S) ≦k(C-S).
∴ k(G-S) ≦|S|
C
2.2 ハミルトン閉路問題
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,k(G-S) ≦|S|
u
v
w
左のグラフはハミルトングラフではない
∵ k(G-{u,v,w})=5, |{u,v,w}|=3 より,
ある空ではないS⊆V(G)に対して,
k(G-S) >|S|となるので
2.2 ハミルトン閉路問題
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,k(G-S) ≦|S|
注意: 逆は成立しない
例えば左のグラフは,
空ではない任意のS⊆V(G)に対して,
k(G-S) ≦|S|となるが
ハミルトングラフではない
提出課題(5/9)
教科書:
P.37 問 2.6
提出課題(5/9)
knight R包
tour 問題
n×n のチェス盤上の全ての正方形をナイトが丁度1回ずつ
通って出発点に戻ることが可能かどうかを考える問題.
knightの動かし方:
左図において
赤丸の位置から移動できる位置は青丸の位置
提出課題:n = 4の場合を考えよ.可能ならば道順を書き,
不可能ならば理由を述べよ.
提出課題(5/9)
knight R包
tour 問題
n×n のチェス盤上の全ての正方形をナイトが丁度1回ずつ
通って出発点に戻ることが可能かどうかを考える問題.
ヒント:各正方形内に頂点を配置し,
ナイトが移動可能な頂点間を辺で結び
グラフG(2部グラフ)を構成すると,
Gがハミルトングラフであるかどうかという
問題に置き換えることができる.
提出課題:n = 4の場合を考えよ.可能ならば道順を書き,
不可能ならば理由を述べよ.
提出課題(5/9)
knight R包
tour 問題
n×n のチェス盤上の全ての正方形をナイトが丁度1回ずつ
通って出発点に戻ることが可能かどうかを考える問題.
ヒント:各正方形内に頂点を配置し,
ナイトが移動可能な頂点間を辺で結び
グラフG(2部グラフ)を構成すると,
Gがハミルトングラフであるかどうかという
問題に置き換えることができる.
発展課題:nが奇数の場合,不可能であることを示せ.

similar documents