スライド 1

有限幾何学
第5回
有限幾何学第5回
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|
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はハミルトングラフ
証明：Claim. 以下のような状況は起こり得ない．
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はハミルトングラフ
証明：Claimの証：Gはハミルトングラフではないので
以下のような状況は起こり得ない．
u
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はハミルトングラフ
証明：Claimより，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)．
∴ n ≦ 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個
提出課題
辺の本数に関する条件
G：位数n≧3の単純グラフに対し，
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
問題：
(1) |E(G)| ≧ (n-1)(n-2)/2+1だと上の定理が成立しない理由を述べよ．
(2) Oreの定理を用いて上の定理を証明せよ．
--------(3)は余裕がある人用---------(3) nが6以上のとき，上の定理の条件とDiracの定理の条件の間には
強弱関係がない．その理由を述べよ．
提出課題
辺の本数に関する条件
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
提出課題
辺の本数に関する条件
G：位数n≧3の単純グラフに対し，
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント：
(2) Oreの定理を用いて上の定理を証明せよ．
上の定理の条件がOreの定理の条件より強いことを言えばよい．
つまり，
「|E(G)| ≧ (n-1)(n-2)/2+2」のもとで，
「dG(u)+dG(v) ≧ n for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」が
成立することを示せばよい
提出課題
辺の本数に関する条件
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が存在すると仮定し，矛盾を導く
提出課題
辺の本数に関する条件
G：位数n≧3の単純グラフに対し，
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント：
(2) Oreの定理を用いて上の定理を証明せよ．
dG(u)+dG(v) < n に注意して辺の数の上限を考える
u
v
G-{u,v}
提出課題
辺の本数に関する条件
G：位数n≧3の単純グラフに対し，
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント：
(3) nが6以上のとき，上の定理の条件とDiracの定理の条件の間には
強弱関係がない．その理由を述べよ．
|E(G)|≧(n-1)(n-2)/2+2かつδ(G)<n/2であるグラフが見つかると
上の定理の条件からDiracの定理の条件が導けないことがいえる．
（完全グラフと1頂点を2辺でつないだグラフを考える）
提出課題
辺の本数に関する条件
G：位数n≧3の単純グラフに対し，
|E(G)| ≧ (n-1)(n-2)/2+2
Gはハミルトングラフ
ヒント：
(3) nが6以上のとき，上の定理の条件とDiracの定理の条件の間には
強弱関係がない．その理由を述べよ．
δ(G)≧n/2かつ|E(G)|<(n-1)(n-2)/2+2であるグラフが見つかると
Diracの定理の条件から上の定理の条件が導けないことがいえる．
(nが偶数：部集合の位数が等しい完全2部グラフ Kn/2 n/2を考える
nが奇数：K(n-1)/2 (n-1)/2と他の1頂点を辺で結んだグラフを考える)

Download Report