有限幾何学　 　　　　　　第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| 左のグラフはハミルトングラフではない ∵ k(G-{u,v,w})=5, |{u,v,w}|=3 より， 　　　　　　　　　　　　　　　 　　ある空ではないS⊆V(G)に対して， 　　K(G-S) >|S|となるので u v w

ハミルトングラフであるための必要条件の例 1.1　必要条件と十分条件（前回の復習） ハミルトングラフであるための必要条件の例 グラフGがハミルトングラフ 空ではない任意のS⊆V(G)に対して，K(G-S) ≦|S| 注意： 逆は成立しない 　　　　　　　　　　　　　　　 　　　　例えば左のグラフは， 　　　　　　　　　　　　　　　 　　　　空ではない任意のS⊆V(G)に対して， 　　　　　　　　　　　　　　　 　　　　K(G-S) ≦|S|となるが 　　　　　　　　　　　　　　　　　　　ハミルトングラフではない

1.1 必要条件と十分条件 次に十分条件について考える 完全グラフはハミルトングラフ 完全グラフから多少辺を除いてもハミルトングラフ 1.1　必要条件と十分条件 次に十分条件について考える 完全グラフはハミルトングラフ 完全グラフから多少辺を除いてもハミルトングラフ 　　辺の本数がどのくらい多ければハミルトングラフであるか？ 辺の本数に関する十分条件の問題

1.1 必要条件と十分条件 ハミルトングラフであるための十分条件の例 G：位数n≧3の単純グラフに対し， 1.1　必要条件と十分条件 ハミルトングラフであるための十分条件の例 G：位数n≧3の単純グラフに対し， |E(G)| ≧ (n-1)(n-2)/2+2　　　　　　　 Gはハミルトングラフ 証明：今日の提出課題 辺の本数に関する十分条件の例

1.1 必要条件と十分条件 完全グラフはハミルトングラフ 完全グラフは各頂点の次数が|V(G)|-1のグラフ 1.1　必要条件と十分条件 完全グラフはハミルトングラフ 完全グラフは各頂点の次数が|V(G)|-1のグラフ 各頂点の次数が|V(G)|-1より多少小さくてもハミルトングラフ 各頂点の次数がどれぐらい大きければハミルトングラフであるか？ 次数に関する十分条件の問題

1.1 必要条件と十分条件 ハミルトングラフであるための十分条件の例 G：位数n≧3の単純グラフに対し， 1.1　必要条件と十分条件 ハミルトングラフであるための十分条件の例 G：位数n≧3の単純グラフに対し， dG(v) ≧ n/2　for ∀v ∈ V(G)　　　　　　　Gはハミルトングラフ 次数に関する十分条件の例（Dirac）

1.1 必要条件と十分条件 ハミルトングラフであるための十分条件の例 G：位数n≧3以上の単純グラフに対し， 1.1　必要条件と十分条件 ハミルトングラフであるための十分条件の例 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の定理から導くことができる 次数に関する十分条件の例（Ore）

補足2：条件に強弱関係がある2つの定理に関して 1.1　必要条件と十分条件 2つの条件AとBに対して，A ⇒ B が成り立つとき， AはBより強い条件，BはAより弱い条件であるという． 「定理1：A ⇒C」 と 「定理2：B ⇒ C」 に対して， BがAより弱い条件であるとき（A ⇒B が成り立つ）， 定理1は定理2より導くことができる． ∵ 定理2が成り立つとすると，A ⇒ B ⇒ C となるので 補足1：条件の強弱に関して 補足2：条件に強弱関係がある2つの定理に関して

1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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以上の単純グラフに対し， 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以上の単純グラフに対し， 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以上の単純グラフに対し， 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

x 1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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 x v

1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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以上の単純グラフに対し， 1.1　必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， dG(u)+dG(v) ≧ n　for ∀u≠∀v ∈ V(G) with uv ∉ E(G)　　　　　　　 Gはハミルトングラフ 証明：Claim. 以下のような状況は起こり得ない． NG(u) と NG(v) が P上隣同士で交差している状況 u v

1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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以上の単純グラフに対し， 1.1　必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， dG(u)+dG(v) ≧ n　for ∀u≠∀v ∈ V(G) with uv ∉ E(G)　　　　　　　 Gはハミルトングラフ 証明：Claimより，NG(v)に属する各頂点に対して，以下のように 　　　　V(G)-NG(u)-{u}に属する異なる頂点を対応させることができる． x y z u v f(x) f(y) f(z) x∈NG(v) に対し，x の右隣の頂点 f(x) ∈V(G)-NG(u)-{u} を対応させる

1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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}への単射fが存在する ． x u v f(x) x∈NG(v) に対し，x の右隣の頂点 f(x) ∈V(G)-NG(u)-{u} を対応させる

1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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}への単射fが存在するので， 　　　　dG(v) =|NG(v)| ≦|V(G)-NG(u)-{u}|=n-dG(u)-1． ∴ n ≦ dG(u)+dG(v) ≦ n-1 となり矛盾

1.1 必要条件と十分条件 次数に関する条件（Ore） G：位数n≧3以上の単純グラフに対し， 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)」・・・① 1.1　必要条件と十分条件 「dG(u)+dG(v) ≧ n-1　for ∀u≠∀v ∈ V(G) with uv ∉ E(G)」・・・① を満たすがハミルトングラフではないグラフの例： 完全2部グラフ Km,m+1 n=|V(G)|=2m+1. 非隣接な2頂点u,vで 　　　　　　　　　　　　　 次数の和が最小になるものは左図の2頂点で， dG(u)+dG(v)=2m=n-1 　　　　　　　　　　　　　 ∴ このグラフは条件①を満たす． m個 u v m+1個

1.1 必要条件と十分条件 「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 　　　　　　　　　　　　　　　ハミルトングラフではない 　　　　　　　　　　　　　　　∵ 左図の頂点集合Sに対し，k(G-S) > |S| m個 S u v 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の定理を用いて上の定理を証明せよ．

提出課題 辺の本数に関する条件 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}