Presentation is loading. Please wait.

Presentation is loading. Please wait.

    有限幾何学        第5回.

Similar presentations


Presentation on theme: "    有限幾何学        第5回."— Presentation transcript:

1     有限幾何学        第5回

2 有限幾何学 第5回 ハミルトングラフ 必要条件と十分条件

3 1.1 必要条件と十分条件(前回の復習) ハミルトン閉路 :グラフの全ての頂点を含む閉路 ハミルトングラフ :ハミルトン閉路をもつグラフ
1.1 必要条件と十分条件(前回の復習) ハミルトン閉路 :グラフの全ての頂点を含む閉路 ハミルトングラフ :ハミルトン閉路をもつグラフ ハミルトン道 :グラフの全ての頂点を含む道 グラフがハミルトングラフであるための 必要十分条件は知られていない

4 ハミルトングラフであるための必要条件の例
1.1 必要条件と十分条件(前回の復習) ハミルトングラフであるための必要条件の例 グラフGがハミルトングラフ 空ではない任意のS⊆V(G)に対して,K(G-S) ≦|S| k(G-S):GからSを取り除いてできるグラフの連結成分の数 ハミルトングラフであるための必要条件の例

5 ハミルトングラフであるための必要条件の例
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

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

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

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

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

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

11 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)

12 補足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つの定理に関して

13 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はハミルトングラフ 証明:上の定理が正しくないと仮定し,矛盾を導く. 上の定理が正しくないと仮定すると, 「定理の仮定を満たすが,ハミルトングラフではないグラフ」 が存在する.

14 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とする.

15 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辺追加すると 注:少なくとも一つは    ①のグラフが存在する 注:辺を追加しても    定理の仮定を満たす 注:辺を追加し続けると    ハミルトングラフになる

16 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

17 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

18 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

19 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

20 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

21 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} を対応させる

22 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} を対応させる

23 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 となり矛盾

24 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)」・・・① だと上の定理は成立しない. このことを示すには, 例えば,条件①を満たすが, ハミルトングラフではないグラフの例をつくればよい.

25 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個

26 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個

27 提出課題 辺の本数に関する条件 G:位数n≧3の単純グラフに対し, |E(G)| ≧ (n-1)(n-2)/2+2 Gはハミルトングラフ
問題: (1) |E(G)| ≧ (n-1)(n-2)/2+1だと上の定理が成立しない理由を述べよ. (2) Oreの定理を用いて上の定理を証明せよ.

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

29 提出課題 辺の本数に関する条件 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)」が 成立することを示せばよい

30 提出課題 辺の本数に関する条件 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が存在すると仮定し,矛盾を導く

31 提出課題 辺の本数に関する条件 G:位数n≧3の単純グラフに対し, |E(G)| ≧ (n-1)(n-2)/2+2 Gはハミルトングラフ
ヒント: (2) Oreの定理を用いて上の定理を証明せよ. dG(u)+dG(v) < n に注意して辺の数の上限を考える u v G-{u,v}


Download ppt "    有限幾何学        第5回."

Similar presentations


Ads by Google