有限幾何学        第5回.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
2015 年度 有限幾何学 期末試験 次の各問に答えよ.( (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい) (1) 有向閉路が存在しない位数 4 のトーナメントを描け. (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ. (3) グラフ.
1. 補間多項式 n 次の多項式 とは、単項式 の 線形結合の事である。 Definitions: ( 区間, 連続関数, abscissas (データ点、格子点、差分点), 多項 式 ) Theorem. (補間多項式の存在と一意性) 各 i = 0, …, n について、 をみたす、次数が高々 n.
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
3.2.3~3.3 D3 川原 純.
・力のモーメント ・角運動量 ・力のモーメントと角運動量の関係
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
計算量理論 6. 4: tightning a constraint 6
第4章 Matching(後半) 情報学研究科 湯浅研究室M1 藤川浩光.
算法数理工学 第9回 定兼 邦彦.
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
    有限幾何学        第8回.
曲面上のグラフの彩色 ~種数の増加,面の制限及び局所平面性~
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
Extremal Combinatorics 14.1 ~ 14.2
Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム
    有限幾何学        第5回.
Probabilistic Method.
Extremal Combinatrics Chapter 4
Approximation of k-Set Cover by Semi-Local Optimization
8.クラスNPと多項式時間帰着.
JAG Regional Practice Contest 2012 問題C: Median Tree
    有限幾何学        第12回.
Semantics with Applications
    有限幾何学        第13回.
Probabilistic Method 6-3,4
A path to combinatorics 第6章前半(最初-Ex6.5)
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
8.Intersecting Families
第 4 章 : 一般回路の定理 4.3 ノートンの定理 ノートンの定理 キーワード : ノートンの定理を理解する. 学習目標 :
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
計算量理論輪講 岩間研究室 照山順一.
A First Course in Combinatorial Optimization Chapter 3(前半)
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
Bridge It と Connections の 必勝法について
計算の理論 I -Myhill-Nerodeの定理 と最小化-
7.4 Two General Settings D3 杉原堅也.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
Bridge It と Connections の 必勝法について
25. Randomized Algorithms
九州大学大学院 情報学専攻特別講義 (3) 配列解析
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
モバイルエージェントネットワークの拡張とシミュレーション
計算量理論輪講 chap5-3 M1 高井唯史.
A First Course in Combinatorial Optimization Chapter
離散数学 07. 木 五島.
計算機科学概論(応用編) 数理論理学を用いた自動証明
7 Calculating in Two Ways: Fubini’s Principle
2016年度 有限幾何学 中間試験 問1 次のグラフを描け.(描けない場合は理由を述べよ) 各20点
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
14. The Basic Method M1 太田圭亮 14.3 Spaces of polynomials
5.3, 5.4 D2 岡本 和也.
Max Cut and the Smallest Eigenvalue 論文紹介
論理回路 第5回
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
Chapter5 Systems of Distinct Representatives
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
生物情報ソフトウェア特論 (4)配列解析II
図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15
13.近似アルゴリズム.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Time Reversal E-Text: pp.80-83(PDF: pp.49-50) FM08002 太神 諭
Presentation transcript:

    有限幾何学        第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}