ノート05

Report
有限幾何学
第5回
有限幾何学 第5回
1. ハミルトングラフ
1. 必要条件と十分条件
1.1 必要条件と十分条件
ハミルトン閉路 :グラフの全ての頂点を含む閉路
ハミルトングラフ :ハミルトン閉路をもつグラフ
ハミルトン道
:グラフの全ての頂点を含む道
ハミルトングラフ
ハミルトングラフではないが
ハミルトン道を含むグラフ
1.1 必要条件と十分条件
ハミルトン閉路 :グラフの全ての頂点を含む閉路
ハミルトングラフ :ハミルトン閉路をもつグラフ
ハミルトン道
:グラフの全ての頂点を含む道
グラフがハミルトングラフであるための
必要十分条件は知られていない
1.1 必要条件と十分条件
ハミルトングラフであるための必要条件の例
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,K(G-S) ≦|S|
k(G-S):GからSを取り除いてできるグラフの連結成分の数
1.1 必要条件と十分条件
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,K(G-S) ≦|S|
証明:C:Gのハミルトン閉路
S:空ではない S⊆V(G) とする.
このとき,
k(C-S) ≦|S|.
C
1.1 必要条件と十分条件
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,K(G-S) ≦|S|
証明:C:Gのハミルトン閉路
S:空ではない S⊆V(G) とする.
このとき,
k(C-S) ≦|S|.
C
1.1 必要条件と十分条件
ハミルトングラフであるための必要条件の例
グラフ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
1.1 必要条件と十分条件
ハミルトングラフであるための必要条件の例
グラフ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|となるので
1.1 必要条件と十分条件
ハミルトングラフであるための必要条件の例
グラフGがハミルトングラフ
空ではない任意のS⊆V(G)に対して,K(G-S) ≦|S|
注意: 逆は成立しない
例えば左のグラフは,
空ではない任意のS⊆V(G)に対して,
K(G-S) ≦|S|となるが
ハミルトングラフではない
1.1 必要条件と十分条件
次に十分条件について考える
完全グラフはハミルトングラフ
完全グラフから多少辺を除いてもハミルトングラフ
辺の本数に関する問題
辺の本数がどのくらい多ければハミルトングラフであるか?
1.1 必要条件と十分条件
ハミルトングラフであるための十分条件の例
辺の本数に関する条件
G:位数n≧3の単純グラフに対し,
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
1.1 必要条件と十分条件
完全グラフはハミルトングラフ
完全グラフは各頂点の次数が|V(G)|-1のグラフ
各頂点の次数が|V(G)|-1より多少小さくてもハミルトングラフ
次数に関する問題
各頂点の次数がどれぐらい大きければハミルトングラフであるか?
1.1 必要条件と十分条件
ハミルトングラフであるための十分条件の例
次数に関する条件(Dirac)
G:位数n≧3の単純グラフに対し,
dG(v) ≧ n/2 for ∀v ∈ V(G)
Gはハミルトングラフ
1.1 必要条件と十分条件
ハミルトングラフであるための十分条件の例
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
「dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」は
「dG(v) ≧ n/2 for ∀v ∈ V(G)」よりも弱い条件
∴ Diracの定理はOreの定理から導くことができる
1.1 必要条件と十分条件
補足1:条件の強弱に関して
2つの条件AとBに対して,A ⇒ B が成り立つとき,
AはBより強い条件,BはAより弱い条件であるという.
補足2:条件に強弱関係がある2つの定理に関して
「定理1:A ⇒C」 と 「定理2:B ⇒ C」 に対して,
BがAより弱い条件であるとき(A ⇒B が成り立つ),
定理1は定理2より導くことができる.
∵ 定理2が成り立つとすると,A ⇒ B ⇒ C となるので
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:上の定理が正しくないと仮定し,矛盾を導く.
上の定理が正しくないと仮定すると,
「定理の仮定を満たすが,ハミルトングラフではないグラフ」
が存在する.
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:上の定理が正しくないと仮定すると,
「定理の仮定を満たすが,
ハミルトングラフではないグラフ」・・・① が存在する.
①のグラフで,
辺を追加してしまうと①のグラフではなくなるものをGとする.
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:「定理の仮定を満たすが,
ハミルトングラフではないグラフ」・・・①
①のグラフ
①のグラフ
辺を追加していく
注:少なくとも一つは
①のグラフが存在する
G
1辺追加すると
注:辺を追加しても
定理の仮定を満たす
①ではない
グラフ
注:辺を追加し続けると
ハミルトングラフになる
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:Gの非隣接な2頂点u,vに
辺uvを加えたグラフはハミルトングラフ.
u
v
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:Gの非隣接な2頂点u,vに
辺uvを加えたグラフはハミルトングラフ.
Gにuとvを結ぶハミルトン道Pが存在する.
u
v
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:Gにuとvを結ぶハミルトン道Pが存在する.
P
u
v
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:Gはハミルトングラフではないので
以下のような状況は起こり得ない.
v
u
NG(u) と NG(v) が P上隣同士で交差している状況
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:Gはハミルトングラフではないので
以下のような状況は起こり得ない.
u
∵ Gがこのようなハミルトンサイクルを持ってしまうので
v
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:NG(v)に属する各頂点に対して,
V(G)-NG(u)に属する異なる頂点を対応させることができる.
u
x
y
f(x)
z
f(y)
v
f(z)
x∈NG(v) に対し,x の右隣の頂点 f(x) ∈V(G)-NG(u) を対応させる
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:∴ NG(v)からV(G)-NG(u)への単射fが存在する .
u
x
v
f(x)
x∈NG(v) に対し,x の右隣の頂点 f(x) ∈V(G)-NG(u) を対応させる
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:また,NG(u) ⊆V(P)-{ u }-f(NG(v)) が成立.
u
x
y
f(x)
z
f(y)
v
f(z)
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
証明:NG(u) ⊆V(P)-{ u }-f(NG(v)) と u ∉ f(NG(v)) と fが単射より,
dG(u) =|NG(u)| ≦ |V(P)|-1-|f(NG(v))|=n-1-|NG(v)|=n-1-dG(v).
∴ dG(u)+dG(v) ≦ n-1 となり矛盾
1.1 必要条件と十分条件
次数に関する条件(Ore)
G:位数n≧3以上の単純グラフに対し,
dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)
Gはハミルトングラフ
「dG(u)+dG(v) ≧ n-1 for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」・・・①
だと上の定理は成立しない.
このことを示すには,
例えば,条件①を満たすが,
ハミルトングラフではないグラフの例をつくればよい.
1.1 必要条件と十分条件
「dG(u)+dG(v) ≧ n-1 for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」・・・①
を満たすがハミルトングラフではないグラフの例:
完全2部グラフ Km,m+1
m個
u
v
m+1個
n=|V(G)|=2m+1.
非隣接な2頂点u,vで
次数の和が最小になるものは左図の2頂点で,
dG(u)+dG(v)=2m=n-1
∴ このグラフは条件①を満たす.
1.1 必要条件と十分条件
「dG(u)+dG(v) ≧ n-1 for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」・・・①
を満たすがハミルトングラフではないグラフの例:
完全2部グラフ Km,m+1
m個
S
u
v
ハミルトングラフではない
∵ 左図の頂点集合Sに対し,k(G-S) > |S|
m+1個
提出課題(5/16)
辺の本数に関する条件
G:位数n≧3の単純グラフに対し,
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
問題:
(1) |E(G)| ≧ (n-1)(n-2)/2+1だと上の定理が成立しない
理由を述べよ.
(2) Oreの定理を用いて上の定理を証明せよ.
(3) 上の定理の仮定とDiracの定理の仮定の間には
強弱関係がない.その理由を述べよ.
提出課題(5/16)
辺の本数に関する条件
G:位数n≧3の単純グラフに対し,
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント:
(1) |E(G)| ≧ (n-1)(n-2)/2+1だと上の定理が成立しない
理由を述べよ.
・|E(G)| ≧ (n-1)(n-2)/2+1だがハミルトングラフではない例を作る
・位数n-1の完全グラフの辺の数は(n-1)(n-2)/2
提出課題(5/16)
辺の本数に関する条件
G:位数n≧3の単純グラフに対し,
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント:
(2) Oreの定理を用いて上の定理を証明せよ.
「|E(G)| ≧ (n-1)(n-2)/2+2」のもとで,
「dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」が
成立することを示せばよい
提出課題(5/16)
辺の本数に関する条件
G:位数n≧3の単純グラフに対し,
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント:
(2) Oreの定理を用いて上の定理を証明せよ.
|E(G)| ≧ (n-1)(n-2)/2+2のもとで,
dG(u)+dG(v) < n となる
非隣接なGの2頂点uとvが存在すると仮定し,矛盾を導く
提出課題(5/16)
辺の本数に関する条件
G:位数n≧3の単純グラフに対し,
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント:
(2) Oreの定理を用いて上の定理を証明せよ.
dG(u)+dG(v) < n に注意して辺の数の上限を考える
u
v
G-{u,v}

similar documents