今日の講義で学ぶこと 2/23 • グラフの一筆書き グラフとネットワーク（6） – オイラー閉路（Euler circuit） – オイラー路（Euler path） – ケーニスベルグ橋の問題 – オイラーの定理 ～オイラーの一筆書き～ • 関連する問題 – ハミルトン閉路（Hamilton circuit） – ハミルトン路（ハミルトンパス、Hamilton path） 3/23 一筆書きとは？ 4/23 【例題】一筆書きが出来ますか？ 厳密には以下で定義します。 【定義】無向連結グラフに対して、全ての辺 を 1 度ずつ通って元に戻る閉路を、オイラー 閉路(Euler circuit) と呼ぶ。 【定義】無向連結グラフに対して、閉路でな く、ある始点から出発した後、全ての辺を 1 度ずつ通るパスを、オイラー路(Euler path) と呼ぶ。 Leonhard Euler とグラフ理論 • 18 世紀の数学者・物理学者・天文学者 • 解析学・数論・幾何学など広範囲にわたり 膨大な業績がある • 与えられた無向連結グラフが、一筆書き可 能かという問題（ケーニスベルグ橋の問 題）は、1736 年にオイラーによって解決 された • 一筆書きは、オイラーの名前を冠している （オイラー閉路、オイラー路） • この問題が、グラフ理論の始まりになった と言われている 5/23 ケーニヒスベルグ橋の問題 6/23 図のように、川なのかの 2 つの島と両岸の間に全部で 7 本 の橋がかかっている。いずれかの地点から出発して、全て の橋をちょうど一回だけ通ってもとの地点に戻ってくる経路 を求めよ Wikipedia より 【ケーニスベルグ】 • 中世後期から1945年まで の東プロイセンの中心地 • 現在はロシアの一部 • カリニングラートの旧称 Wikipedia より 現在のケーニスベルグ橋 7/23 8/23 現在のケーニスベルグ橋 C 川 B A 川 D ©2013 Google 9/23 【解答例】 【練習問題】両岸と中須島を頂点、それらを結ぶ 橋を辺として、現在のケーニスベルグ橋の周辺を グラフで表現しなさい 【オイラーの定理】連結無向グラフ G = (V,E) にオイラー閉路が存在するための必要十分条件 は、全ての点の次数が偶数となることである。 10/23 また、オイラー路が存在するための必要十分 条件は 2 点を除き、全ての点の次数が偶数にな ることである。除外された 2 点がオイラー路の 始点と終点になる。 deg=2 deg=2 オイラーの定理の証明 11/23 閉路に関してのみ証明する。 必要性）一筆書きが存在するとき、各点では 入った回数だけ出ることになるので、両方合わ せると偶数になることから明らか。 十分性）各頂点が全て偶数であるという仮定の 下で、辺の数に関する帰納法で証明する。 辺の数が 1 のときは、自己ループをもつ場合 なので、明らかに成り立っている。 辺の数が k 以下では、定理が成り立ってい ると仮定する。 deg=3 deg=3 deg=2 deg=2 deg=2 deg=2 deg=2 deg=4 deg=2 deg=2 12/23 このとき、辺数が k + 1 のグラフでは、 任意の頂点に対して、その頂点から出発して、 出発点に戻る閉路 W が存在する。 W が G の全ての頂点 V を通っていれば、 これがオイラー閉路である。 そうでない場合は、G から W で使った辺 を全て除いたグラフ H を考える。 H は一般に非連結になるが、その連結成分 は、帰納法の仮定により、オイラー閉路を持 つ。W を辿りながら、H の連結成分に出会 うたびに、そのオイラー閉路を先に辿ること で G のオイラー閉路が構成できる。□ 【練習問題】 オイラー閉路が存在するなら 1 つ求めなさい 13/23 現在のケーニスベルグ橋 14/23 C 川 B A 川 D 【練習問題】両岸と中須島の何れからか出発して、 全ての橋を1回だけ渡ることは可能か？理由を付け て答えなさい。 【解答例】 15/23 計算量 16/23 オイラー閉路およびオイラー路は、定理の 証明の方針で計算できる。 【定理】オイラー閉路およびオイラー路を 1 つ見つけるための計算量は、 O(|V|+|E|) この問題はクラスPに属する である。 【注】ここまでに紹介した結果は、 有向グラフにも容易に拡張できる 関連する問題 17/23 【定義】無向連結グラフに対して、全ての 頂点を 1 度ずつ通って元に戻る閉路を、 ハミルトン閉路(Hamilton circuit) と呼ぶ。 【定義】無向連結グラフに対して、閉路で なく、ある始点から出発した後、全ての 頂点を 1 度ずつ通るパスを、ハミルトン路 (Hamilton path)と呼ぶ。 【注】与えられた無向連結グラフが、ハミルトン閉路、 または、ハミルトン路を持つかどうかを判定する効率的 アルゴリズムは、現在まで知られていない。（クラスNP） ハミルトングラフ 18/23 【定義】ハミルトン閉路が存在するグラフを ハミルトングラフと呼ぶ 【注】ハミルトングラフなどの名は、グラフがハミルトン 閉路を持つかどうかを最初に研究したイギリスの数学者 ウイリアム・ハミルトンに由来する。 【注】空間図形は、5種類の正多面体（正4面体、正6面体、 正8面体、正12面体、正20面体）が存在する。それらの 頂点をグラフの頂点、面の境を辺と見做したグラフは、 プラトングラフと呼ばれる。 プラトングラフは、ハミルトングラフであることが知ら れている。 19/23 【練習問題】次のグラフは、ハミルトングラフか？ もし、ハミルトングラフならハミルトン閉路を 1 つ 答えなさい 【注】 上記の例は、プラトングラフ（正12面体）である 21/23 【練習問題】4×4 盤のナイトグラフを描きなさい 20/23 ナイトグラフ（knight graph） 【定義】チェスにおいて、盤上でナイトの 駒が動くマス目を結ぶことで出来るグラフ をナイトグラフと呼ぶ ナイトの動き = 桂馬の動き 3×3 盤のナイトグラフ 22/23 【練習問題】 （1）4×4 盤のナイトグラフにオイラー閉路は 存在するか？ 次数3の頂点が8つ存在するので、オイラー 閉路は存在しない （2）4×4 盤のナイトグラフにハミルトン閉路は 存在するか？ 存在しない オイラー路とハミルトン路 23/23 オイラー路の問題 – – – – 辺の一筆書き問題 最初に研究した数学者オイラーに由来する クラスPに属する 効率的な判定、および、構成アルゴリズムが存在 する ハミルトン路の問題 – – – – 頂点の一筆書き問題 最初に研究した数学者ハミルトンに由来する クラスＮＰに属する 任意のグラフに対する効率的な判定、および、 構成アルゴリズムは、知られていない 【注】効率的アルゴリズムは、存在しないと考えられている
© Copyright 2024 ExpyDoc
![5 月 20 日 （授業のまとめ） 定理 4.5 f,g ∈ Q[X], g ̸= 0 に対して f = qg](http://s3.expydoc.com/store/data/007455355_1-ec7d8d345da9ed62a3758f9b0fc211c0-250x500.png)
