離散数学講義ノート（グラフ理論）

グラフ理論のモチベーション つながりは集合上に構造を定める. V={a,b,c,d,e,f,g}. E={{a,b},{c,d},{c,g},{d,f},{f,g},{e,g}}. 空でない集合Vと,Vの2元からなる部分集合の集合E⊆(V/2)の組(V,E) をグラフと呼ぶ. グラフで「つながり」を研究しよう. 一筆書きパズル 最短ルート検索アルゴリズム 化合物検索 通信ネットワーク設計 ネットワーク疫学 電気回路解析 ソーシャルネットワーク分析

組合せ論, 位相幾何学 計算機科学 応用 Graph Theory グラフ理論 Graph Algorithm グラフアルゴリズム Network Science ネットワーク科学 パズル アルゴリズム 化学 情報工学 疫学 電気工学 社会科学

グラフ理論の最初の定理

グラフ理論の歴史の参考書 GRAPH THEORY 1736-1936 現代の数理科学シリーズ6 グラフ理論への道 GRAPH THEORY 1736-1936 N.L.ビッグス・E.K.ロイド・R.J.ウィルソン 一松信・秋山仁・恵羅博 訳 数学者というのは、しばしば彼らの研究を気 ままに、気がむくままに、かつ直観的に進 めるものであり、明確な論理に照らして追究を していないことが多々ある。したがって研究テ ーマの歴史的展開は、本直に言って私たちが多 くの教科書で見るような系統立った進め方とか 離れているのである。 この本では、歴史的展開をたどることにより、 グラフ理論についての自己充足的解説を試みた。 ある学問が数学的な理論として一つの形を成す に至るまで、複雑に入り組んだアイディアや相 互に影響を与えあって発達したいきさつを、読 者が正しく認識していただければ幸いである。 グラフ理論の起源は、単純で、他愛もないも のでさえある。数学の多くの分野が、計算や運 動、または測定の基本的な問題によって、それ らの発展の動機を与えられたのに対し、グラフ 理論の発展を導いた問題は、創造力を刺激する というよりも、むしろ緻密な頭脳を試すために 作られたパズルのようなものであった。しかし、 N. L. Biggs, E. K. Lloyd, R. J. Wilson 地人書館

ケーニヒスベルクの橋の問題 17世紀 ケーニヒスベルク プルーゲル川が土地を4つに分けており, 川を渡る7つの橋が架けられていた. KONINGSBERGA Matthäus Merian作, Martin Zeiller著, Topographia prussice et pomerellie, 1652年出版. (画像はモラヴィア図書館のMoll's Map Collectionより)

ケーニヒスベルクの橋の問題 当時の住人たちの疑問 7つの橋をちょうど1度ずつ渡る道順はあるか？ KONINGSBERGA Matthäus Merian作, Martin Zeiller著, Topographia prussice et pomerellie, 1652年出版. (画像はモラヴィア図書館のMoll's Map Collectionより)

グラフ理論の起源
ケーニヒスベルクの橋の問題を解いた1736年のオイラーの論文
KONINGSBERGA
SOLVTIO PROBLEMATIS
SOLVTIO PROBLEMATIS
AD
GEOMETRIAM SITVS
PERTINENTIS.
AVCTORE
Leonb. Eulero.
§. I.
Tabula VIII. Praeter illam Geometriae partem, quae circa quan-
titates versatur, et omni tempore fummo studio
est exculta, alterius partis etiamnum admodum
ignotae mentionem fecit Leibnitzius, quam Geo-
metriam situs vocavit. Ista pars ab ipso in solo situ
determinando, fitusque proprietatibus eruendis occupata
esse statuitur; in quo negotio neque ad quantitates re-
fpiciendum, neque ad quantitatem virendum fit.
Cuiusmodi autem problemata ad hanc fitus Geometriam
pertineant, et quali methodo in iis refoluendis vti opor-
teat, non fatis eft definitum. Quamobrem, cum nuper
problematis cuiusdam mentio effet facta, quod quidem
ad geometriam pertinere videbatur, at ita erat com-
paratum, vt neque determinationem quantitatum requi-
reret, neque folutionem quantitatum ope admie-
teret, id ad geometriam fitus referre haud dubitani:
praefertim quod in eius folutione folus fitus in confide-
rationem veniat, calculus vero nullius prorfus fit vfus.
Methodum ergo meam quam ad huius genere proble-
mata
Matthäus Merian作, Martin Zeiller著, Topographia prussice et pomerellie, 1652年出版.
(画像はモラヴィア図書館のMoll's Map Collectionより)
ライプニッツが言及していた
大きさや測量に関係せず
"位置"のみが重要な幾何学
の例として, ケーニヒスベルクの橋の問題
に取り組んだ論文.
Commentarii Academiae scientiarum Imperialis Petropolitanae 8 (1736), 128-140.

グラフ理論の起源 ケーニヒスベルクの橋の問題を解いた1736年のオイラーの論文 KONINGSBERGA Matthäus Merian作, Martin Zeiller著, Topographia prussice et pomerellie, 1652年出版. (画像はモラヴィア図書館のMoll's Map Collectionより) ライプニッツとオイラーの すごいところ 土地の大きさや形, 橋の長さなど 従来の"計量"を捨象してもなお おもしろい数学があることを発見した. ケーニヒスベルクの橋の問題は 土地と土地が いくつの橋でつながっているか という情報だけが重要であることを オイラーは看破した.

オイラーの解法 4つの区域をA,B,C,Dとおく. (区域の形や大きさを捨象) 橋を渡る道順をA,B,C,Dの4文字の列で表す. (移動距離などを捨象) 例 ACABADC ABACDB 同じ?? CACDABA ABACDB 区域XからYへ渡るときに 渡れる橋が複数ある場合 どちらを渡っても結論は変わらないので 通った区域の順だけ分かれば十分.

オイラーの解法 主張1 k+1文字の道順X1X2X3…XkXk+1があるならば, その道順では橋をちょうどk回渡る. 例 7文字 ACABADC 6回渡る 主張2 区域Xに奇数本の橋が架かっているとき, もし所望の道順があるならば, その道順では文字XがXに架かる橋の数+1 / 2 回現れる. 主張3 区域Xに偶数本の橋が架かっているとき, もし所望の道順があるならば, その道順では文字Xが (1) Xが出発点でないとき Xに架かる橋の数 / 2 回現れる. (2) Xが出発点のとき Xに架かる橋の数+1 / 2 回現れる.

オイラーの解法 主張1 k+1文字の道順X1X2X3…XkXk+1があるならば, その道順では橋をちょうどk回渡る. 主張2 区域Xに奇数本の橋が架かっているとき, もし所望の道順があるならば, その道順では文字XがXに架かる橋の数+1 / 2 回現れる. 主張3 区域Xに偶数本の橋が架かっているとき, もし所望の道順があるならば, その道順では文字Xが (1) Xが出発点でないとき Xに架かる橋の数 / 2 回現れる. (2) Xが出発点のとき Xに架かる橋の数+1 / 2 回現れる. ケーニヒスベルクの橋の問題で, もし所望の道順が存在するならば, 主張1より 8文字の道順である. 一方, どの区域も奇数本の橋が架かっているから, 主張2より Aは3回, B,C,Dはそれぞれ2回現れるので, 3+2+2+2=9文字の道順であり, 矛盾する

オイラーの解法 一般の場合は次のような表を書いて判定する. (区域) (Aiに架かる橋の数) A1 a1 A2 a2 A3 a3 : : An an 橋の総数+1 主張1より, 道順に現れるべきAiの数の合計と橋の数を 書いてチェックする 主張4 (1) Σbi = 橋の総数+1 ならば, Aiが奇数の区域Aiを出発点とする所望の道順が存在する. (2) Σbi = 橋の総数 ならば, Aiが偶数の区域Aiを出発点とする所望の道順が存在する. (3) それ以外ならば所望の道順は存在しない. bi = { (Ai+1)/2 (Aiが奇数) ai/2 (Aiが偶数) 注)出発点, 終点は1つずつしかなく その他はすべて途中だから, とりあえずすべての区域にai/2を 対応付けた オイラーの論文ではこの証明は 書かれていない. (オイラーには自明だった?)

オイラーの解法 より簡単な判定法を示すために, オイラーは次の補題を証明した. 補題 各区域に架かる橋の数の総和は, 橋の総数の2倍である. 例 A 4 B 3 C 4 D 4 E 3 18 = 9 x 2 橋の総数 オイラーの 証明) どの橋もちょうど2つの区域をつないでいるため, 各区域に架かる橋の数を数え上げると, どの橋もちょうど2回ずつ数えられるから.

オイラーの解法 主張4と補題から, 次の定理を得る. 定理 一般に, すべての橋をちょうど1度ずつ渡る道順は…, (1) 奇数本の橋が架かる区域が3つ以上あるときは, 存在しない. (2) 奇数本の橋が架かる区域がちょうど2つあるときは, その一方を出発点, もう一方を終点とする道順が存在する. (3) 奇数本の橋が架かる区域が無いときは, どの区域から出発しても所望の道順が存在する. 証明) (1) Σbi ≥ (Σai/2) + 3/2 = 橋の総数+1 + 1/2 > 橋の総数+1 (2) Σbi = (Σai/2) + 2/2 = 橋の総数+1. (3) Σbi = Σai/2 = 橋の総数 よって, 主張4より, 定理が成り立つ.

現在のグラフ理論の言葉で整理
空でない集合Vと, Vの2元からなる部分集合の集合E⊆(V/2)の組(V,E)
をグラフとか単純グラフとか単純無向グラフと呼ぶ.
Vの元を頂点と呼び, Vを頂点集合と呼ぶ.
Eの元を辺と呼び, Eを辺集合と呼ぶ.
頂点vを元に持つ辺の数をvの次数と呼び, deg(v)で表す.
例 V:={a,b,c,d,e,f,g}.
E:={{a,b},{c,d},{c,g},{d,f},{f,g},{e,g}}.
(V,E)はグラフである.
右図は(V,E)を表した図の一例である.
とても重要!!! 頂点を○, 辺を線分で表して図(ダイアグラム)を描くことが多いが,
原則としてグラフは2つの集合VとEの組でしかなく, 図は補助にすぎない.
「グラフ」という用語を創ったのは
シルベスター(J.J.Sylvester).
Chemistry and Algebra, Nature 17 (1877-8), 284.
化学の分野の化合物の図式が
グラフ的(図的)表現と呼ばれて
いたことに由来すると思われる.
v 次数
a 1
b 1
c 2
d 2
e 1
f 2
g 3

現在のグラフ理論の言葉で整理 空でない集合V, 集合Eと, Eから(V/2)への写像ψの組(V,E,ψ) を多重グラフとか多重無向グラフと呼ぶ. 例 V:={v1,v2,v3,v4,v5,v6,v7} E:={a,b,c,d,e,f,g,h,i,j} ψ(a)={v1,v2}, ψ(b)={v1,v2}, ψ(c)={v1,v2}, ψ(d)={v3,v4}, ψ(e)={v3,v4}, ψ(f)={v3,v4}, ψ(g)={v3,v7}, ψ(h)={v4,v6}, ψ(i)={v6,v7}, ψ(j)={v5,v7}. (V,E,ψ)は多重グラフである. 右図は(V,E,ψ)を表した図の 一例である. 2頂点間に辺が2本以上 あると, E={A,B}, {A,B} ={A,B} だからψが必要になる. v 次数 v1 3 v2 3 v3 4 v4 3 v5 1 v6 2 v7 4

現在のグラフ理論の言葉で整理 多重グラフG=(V,E,ψ)に対して, Gの頂点と辺の交互列で, 次の条件をすべてみたすものをGの歩道と呼ぶ. ・頂点から始まり頂点で終わる. ・列中で辺eを挟む2頂点x,yがψ(e)={x,y}をみたす. 列中でどの辺も高々1度しか現れない歩道を小道と呼ぶ. 列中でどの頂点も高々1度しか現れない歩道を道と呼ぶ. Gのどの2頂点x,yについても, xから始まりyで終わるGの道が存在するとき, Gは連結であると言う. 例 (v3,e,v4,d,v3,e,v4,h,v6)は歩道 (v3,e,v4,d,v3,g,v7)は歩道かつ小道 (v3,e,v4,h,v6)は歩道かつ小道かつ道. v3からv3への道は無いからGは非連結. Hはどの2頂点間にも道があるから連結.

現在のグラフ理論の言葉で整理 定理(オイラー,1736) 連結グラフGに, すべての辺をちょうど1度ずつ含む小道が存在するならば, Gには次数が奇数の頂点がちょうど2つある, または1つも無い. また, この逆も成り立つ. さらに, 奇数次の頂点が2つのときは必ずその2頂点が始点と終点であり, 奇数次の頂点が無いときは, どの頂点も始点になれる(そしてその頂点が終点である). 例 ケーニヒスベルクの橋の問題 V={A,B,C,D}. E={a,b,c,d,e,f,g}. ψ(a)={A,B}, ψ(b)={A,B}, ψ(c)={A,C}, ψ(d)={A,C}, ψ(e)={A,D}, ψ(f)={B,D}, ψ(g)={C,D}. 奇数次の頂点が4つあるから, 定理より, 所望の道順は無い. 後にBC間に新しく橋が架かり, ABCABDACDのような道順が可能となった.

現在のグラフ理論の言葉で整理 定理(オイラー,1736 & ヒアホルツァー,1873) ←グラフ理論の最初の定理? 連結グラフGに, すべての辺をちょうど1度ずつ含む小道が存在するならば, Gには次数が奇数の頂点がちょうど2つある, または1つも無い. また, この逆も成り立つ. さらに, 奇数次の頂点が2つのときは必ずその2頂点が始点と終点であり, 奇数次の頂点が無いときは, どの頂点も始点になれる(そしてその頂点が終点である). オイラーの論文では, 逆が成り立つことの証明は書かれていない. その証明が初めてきちんと書かれたのは1873年のヒアホルツァーの論文である. そこでは, 一筆書きを節点と線のネットワークシステム上の問題と捉えており, より現在のグラフに近いものを研究している. ヒアホルツァーは若くして亡くなった. 1873年の論文は彼が生前に仲間に報告した内容を 同僚のウィーナー(C.Wiener)とリュロス(Lüroth)が 代筆したものである. 一筆書き できない できる できる

グラフ理論の最初の定理 オイラーの論文に登場した次の補題は握手補題と呼ばれが, グラフ理論の最初の定理と呼ばれることもある. 補題 各区域に架かる橋の数の総和は, 橋の総数の2倍である. 例 A 4 B 3 C 4 D 4 E 3 18 = 9 x 2 橋の総数 定理(オイラー,1736) どんな単純グラフ(V,E)や多重グラフ(V,E,ψ)についても Σdeg(v) = 2|E| が成り立つ. v∈V 各人が握手した 人の数の総和は 会場で発生した 握手の総回数の 2倍.

山登り問題 moutain climbing problem

山登り問題 2人の登山家が山の両端から同時に出発する. ・この山の起伏はスタート地点より低くならない. ・2人は常に同じ高度を保たなければならない. 2人は出会えるか?

山登り問題 2人の登山家が山の両端から同時に出発する. ・この山の起伏はスタート地点より低くならない. ・2人は常に同じ高度を保たなければならない. 2人は出会えるか? 出会える!! どんな山でも出会える?

山登り問題 2人の登山家が山の両端から同時に出発する. ・この山の起伏はスタート地点より低くならない. ・2人は常に同じ高度を保たなければならない. 2人は出会えるか? 定理 どんな山でも出会える.

この先 ネタバレ 注意!! 自分で証明にトライしてから続きへ進もう

山登り問題のグラフ理論的証明 山の局所的な頂や谷と同じ高度になる地点に P2,P3,…,Pn-1をラベル付ける. 山の両端にP1,Pnをラベル付ける. P:={P1,P2,…,Pn}とおき, 2人の登山家をX,Yとおく. V:={(x,y)|x,y∈P, 地点xとyは同じ高度である}. E:={{(x1,y1),(x2,y2)}|(x1,y1),(x2,y2)∈V, Xがx1, Yがy1にいる状態と Xがx2, Yがy2にいる状態が 1ステップで移り合える}. グラフG:=(V,E)について考える. 例 Gには 頂点(P1,Pn)から(P6,P6)への道がある. よって, 2人は出会える.

山登り問題のグラフ理論的証明 Gには 頂点(P1,P21)から(Pn,Pn)への 道がある. よって, 2人は出会える.

山登り問題のグラフ理論的証明 グラフGの頂点(x,y)∈Vに対応する状態は以下の12パターンである. (1) x・y 斜面 斜面 (4) x・y 頂 斜面 (7) x・y 谷 斜面 (10) x・y 谷 端 (2) x・y 斜面 頂 (5) x・y 頂 頂 (8) x・y 谷 頂 (11) x・y 端 谷 (3) x・y 斜面 谷 (6) x・y 頂 谷 (9) x・y 谷 谷 (12) x・y 端 端

山登り問題のグラフ理論的証明 グラフGの頂点(x,y)の次数はパターン⑫のみ奇数で, 他は偶数である. (1) x・y 斜面 斜面 deg((x,y)) = 2 (4) x・y 頂 斜面 deg((x,y)) = 2 (7) x・y 谷 斜面 deg((x,y)) = 2 (10) x・y 谷 端 deg((x,y)) = 2 (2) x・y 斜面 頂 deg((x,y)) = 2 (5) x・y 頂 頂 deg((x,y)) = 4 (8) x・y 谷 頂 deg((x,y)) = 0 (11) x・y 端 谷 deg((x,y)) = 2 (3) x・y 斜面 谷 deg((x,y)) = 2 (6) x・y 頂 谷 deg((x,y)) = 0 (9) x・y 谷 谷 deg((x,y)) = 4 (12) x・y 端 端 deg((x,y)) = 1

山登り問題のグラフ理論的証明 グラフGの頂点(P1,Pn)から辺を辿って到達できる頂点の集合をV', グラフGの頂点(P1,Pn)から辺を辿って通過できる辺の集合をE', とおき, グラフG'=(V',E')を考える. G'は連結グラフである. 各頂点の次数はGのときと変わっていない. 頂点(P1,Pn)はパターン⑫の状態に対応するから その次数は(G'においても)1である. 握手補題より, 奇数次の頂点は偶数個ある. 定理(握手補題) どんな単純グラフ(V,E)や多重グラフ(V,E,ψ)についても Σdeg(v) = 2|E| が成り立つ. v∈V もしかすると, Gは非連結なグラフかも… (P1,Pn)を含む連結なグラフG'に 絞って考えることにした.

山登り問題のグラフ理論的証明 グラフGの頂点(P1,Pn)から辺を辿って到達できる頂点の集合をV', グラフGの頂点(P1,Pn)から辺を辿って通過できる辺の集合をE', とおき, グラフG'=(V',E')を考える. G'は連結グラフである. 各頂点の次数はGのときと変わっていない. 頂点(P1,Pn)はパターン⑫の状態に対応するから その次数は(G'においても)1である. 握手補題より, 奇数次の頂点は偶数個ある. よって, (P1,Pn)以外に少なくとももう1つ, パターン⑫の状態に対応した頂点が G'にはあり, それは(P1,P1), (Pn,Pn), (Pn,P1)のいずれかである. G'は連結だから, いずれの場合も(P1,Pn)からその頂点への道がある. したがって, 2人は出会える.

オイラーの多面体定理

多面体の非計量的性質 問. 多面体の形や体積, 面の形や面積, 辺の長さ などを忘れてもなお おもしろいことはあるか? 面の数 4 6 7 6 頂点数 4 8 10 8 辺の数 6 12 15 12 共通する性質は?

オイラーの多面体定理 定理(オイラー,1752) ??? 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. 面の数 4 6 7 6 頂点数 4 8 10 8 辺の数 6 12 15 12 4+4=6+2 6+8=12+2 7+10=15+2 6+8=12+2

1750年 11月 14日 オイラーがゴールドバッハに宛てた手紙の要約. 表面が平面によって囲まれる立体の 面の数をH, 頂点数をS, 辺の数をAとおくと. H + S = A + 2 が成り立つ. 例 三角プリズム H=5, S=6, A=9. H+S=11, A+2=11. この種の発見をまだ誰もしていないことは驚きです. この命題は証明がとても難しく, 十分に納得のいく証明がまだできていません.

オイラーの多面体定理 定理(オイラー,1752) ??? 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. オイラーの証明の方針. 多面体からを次々に切り取っていくと, 最後はになる. f-e+vの値がを切り取る前後で不変であるように切り取れる. 最後に残るはf-e+v=2だから, 元の多面体もf-e+v=2. 6面12辺8頂点 6+1面12辺8-1頂点 7面12辺7頂点 7-2面12-3辺7-1頂点 5面9-1辺6-1頂点 5-1面8-2辺5-1頂点 4-6+4=2.

証明の歴史 1752年 オイラー を切り取る手法. ・いつでも上手くを切り取れるのだろうか? 凸を保ったままでは不可能 どこかで非凸多面体になるけどそれでも上手く切り取れる? 1794年 ルジャンドル 凸多面体について証明した. ・凸多面体を球面に投影し, 球面上の多角形の面積を用いる手法. 1813年 コーシー 凸多面体についての別証明を与えた. ・凸多面体を平面に投影し, (今で言うところの)グラフ理論的に示す手法.

ルジャンドルの証明 大円(球の中心を中心とする球面上の円)によって分割される 球面の部分を球面上の多角形と呼ぶ. 球の半径をrとおくと球面の面積は4πr². 球面上の三角形の面積をsとおくと. 4πr² = s + s = 2 x (s + s + s - s - s) 大円の線に沿って みかんの皮をむくように球面を二等分できる α/2π x 4πr² β/2π x 4πr² γ/2π x 4πr² ∴ 4πr² = (α+β+γ)x4r² - 4s ∴ s = r²(α+β+γ - π) (球面上の)n角形はn-2個の(球面上の)三角形に分割できるから, その面積は r²(内角の和 - (n-2)π).

ルジャンドルの証明 凸多面体の内部に光源を置く. 光源を中心とし, 凸多面体を内部に含む 球の表面には, 凸多面体の影が投影される. 多面体は凸だから, 影において辺同士は交差しない. 凸多面体の面, 辺, 頂点は, それぞれ 影における面, 辺, 頂点に対応している. 影における各面Fの面積をS(F), 内角の和をθ(F), 辺数をe(F)とおく. 凸多面体の面, 辺, 頂点の数をそれぞれ f, e, vとおく. 球面の面積4πr² = ΣS(F) = Σr²(θ(F)-(e(F)-2)π) = r²Σθ(F) - πr²Σe(F) + 2πr²Σ1 = r²x2πv - πr²x2e + 2πr²f よって, f-e+v=2//

コーシーの証明 外す. 覗く. 凸多面体が 平面的に見える 言い換えると… 外した面の近くに光源を置いて 平面に投影した影は平面図形. 凸多面体の面, 辺, 頂点の数をf, e, v, この平面図形の面, 辺, 頂点をf', e', v'とおくと f=f'+1, e=e', v=v'だから, f'-e'+v'=1を示せばよい. f=6, e=10, v=6 f'=5, e'=10, v'=6.

コーシーの証明 補題 f'個の多角形に分割された平面図形の辺数をe', 頂点数をv'とおくと. f'-e'+v'=1. 証明). f'個の多角形のうち, 三角形でないものがあれば 三角形分割をする. できあがった図形の面, 辺, 頂点の数を それぞれf'', e'', v''とおく. 辺を1本追加するごとに面が1つ増えるから, f'-e'+v'=f''-e''+v''. よって, f''-e''+v''=1を示せばよい. f'=7, e'=19, v'=13 f''=7+8, e''=19+8, v''=13

コーシーの証明 以下のルールで三角形を1つずつ除去していくと, 最後は1つの三角形になる. (1) "とんがり"があるときは, 優先的に除去する. このとき, 面と頂点が1つずつ減り, 辺が2本減るため, 面の数 - 辺の数 + 頂点数は不変である. (2) "とんがり"がないときは, "内向き"な三角形を除去する. このとき, 面と辺が1つずつ減るため, 面の数 - 辺の数 + 頂点数は不変である.

コーシーの証明 (1) (2) 例

コーシーの証明 以下のルールで三角形を1つずつ除去していくと, 最後は1つの三角形になる. (1) "とんがり"があるときは, 優先的に除去する. このとき, 面と頂点が1つずつ減り, 辺が2本減るため, 面の数 - 辺の数 + 頂点数は不変である. (2) "とんがり"がないときは, "内向き"な三角形を除去する. このとき, 面と辺が1つずつ減るため, 面の数 - 辺の数 + 頂点数は不変である. 最後に残った三角形は面の数 - 辺の数 + 頂点数 = 1 - 3 + 3 = 1. よって, f''-e''+v''=1. //

コーシーの証明 以下のルールで三角形を1つずつ除去していくと, 最後は1つの三角形になる. (1) "とんがり"があるときは, 優先的に除去する. このとき, 面と頂点が1つずつ減り, 辺が2本減るため, 面の数 - 辺の数 + 頂点数は不変である. (2) "とんがり"がないときは, "内向き"な三角形を除去する. このとき, 面と辺が1つずつ減るため, 面の数 - 辺の数 + 頂点数は不変である. 疑問 いつでも上手く△を除去できるのだろうか? 例 面2, 辺7, 頂点6 除去する順序によっては最後が三角形にならない

グラフ理論の言葉で補強したい グラフを辺が(頂点以外で)交差しないように平面上に描き表した図を 平面グラフと呼ぶ. 厳密には平面R²上の点集合Vと曲線分集合Eの組(V,E'). 例 V={a,b,c,d}, E={{a,b},{a,c},{b,c},{a,d}}. 以下の図はいずれもグラフ(V,E)を表した図だが, 図としてはすべて異なる. (V,E') 平面グラフ 平面グラフ 平面グラフではない. (以降, グラフの頂点集合は有限集合とする). 平面グラフは平面をいくつかの閉じた面と, 1つの開いた面に分割する. それらをその平面グラフの領域と呼ぶ. 3領域, 7辺, 6頂点 1領域, 7辺, 8頂点 4領域, 12辺, 12頂点

平面グラフのオイラーの公式 定理 連結な平面グラフの領域, 辺, 頂点の数を それぞれr, m, nとおくと. r - m + n = 2. 例 3領域, 7辺, 6頂点 3-7+6=2. 1領域, 7辺, 8頂点 1-7+8=2. 4領域, 12辺, 12頂点. 4-12+12≠2. 連結でないとダメ. コーシーの証明では多角形に限定されていたため△△などの 扱いに困ったが, 平面グラフに拡張すると解消される.

平面グラフのオイラーの公式 定理 連結な平面グラフの領域, 辺, 頂点の数を それぞれr, m, nとおくと. r - m + n = 2. 証明の概略). mに関する数学的帰納法で示す. m = 0のとき, ・ r=1, m=0, n=1よりr-m+n=2. kを非負整数とする. m=kのとき定理が成り立つと仮定して, m=k+1のときを示す. (1) r=1のとき. 次数が1の頂点が存在する(要証明). その頂点と, それにつながる辺を除去してできる平面グラフ は連結であり, 辺の数はm-1=kだから. 帰納法の仮定より r-k+(n-1)=2. したがって, r-m+n=r-(k+1)+n=r-k+(n-1)=2.

平面グラフのオイラーの公式 定理 連結な平面グラフの領域, 辺, 頂点の数を それぞれr, m, nとおくと. r - m + n = 2. 証明の概略). mに関する数学的帰納法で示す. (2) r≥2のとき. 閉じた領域が存在する. その領域の境界を作っている辺を1つ選び eとおく. eを除去してできる平面グラフは連結であり, 辺の数はm-1=kである. 領域の数は1つ減っている(厳密にはジョルダンの閉曲線定理より). よって, 帰納法の仮定より(r-1)-k+n=2. したがって, r-m+n=r-(k+1)+n=(r-1)-k+n=2. 以上より, 定理は成り立つ.

コーシーの証明をグラフ理論で補強 定理(オイラー,1752) 凸 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. 証明). 外す. 外した面の近くに光源を置いて 平面に投影した影は平面グラフ この平面グラフの領域, 辺, 頂点の数はf, e, vだから, 平面グラフのオイラーの公式より f - e + v = 2.

オイラーの多面体定理 定理(オイラー,1752) ??? 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. 凸でない多面体だとどうなる? 6面12辺8頂点 6-12+8=2 11面24辺16頂点 11-24+16=3 16面32辺16頂点 16-32+16=0 10面24辺16頂点 10-24+16=2 多面体とは何か?

多面体 直線分で囲まれた平面図形であって, 穴が空いていないものを 多角形と呼ぶ. 多角形で囲まれた立体図形であって, 以下をすべてみたすものを 多面体と呼ぶ. (1) どの異なる2面も 頂点か辺でしか交わらない ダメ! (2) どの辺もちょうど2面の境界. ダメ! (3) 多面体の表面のどの2点も 表面を辿って行き来できる. これで1つの多面体と呼んではダメ! (4) どの頂点Aについても, Aを通らずにAを含むすべての面を ぐるっと一周できる. 1点でつながるのはダメ!

オイラーの多面体定理 定理(オイラー,1752) ??? 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. 凸でない多面体だとどうなる? 6面12辺8頂点 6-12+8=2 11面24辺16頂点 11-24+16=3 16面32辺16頂点 16-32+16=0 10面24辺16頂点 10-24+16=2 多面体ではない この面が多角形ではない 多面体ではない

オイラーの多面体定理 定理(オイラー,1752) ??? 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. 凸でない多面体だとどうなる? 6面12辺8頂点 6-12+8=2 16面32辺16頂点 16-32+16=0

オイラーの多面体定理 定理(オイラー,1752) 穴の空いていない 多面体の面の数をf, 辺の数をe, 頂点の数をvとおくと. f - e + v = 2. 6面12辺8頂点 6-12+8=2 定理(リュイリエ,1811~1813) 穴がg個空いている多面体の面の数をf, 辺の数をe, 頂点をvとおくと. f - e + v = 2 - 2g. 16面32辺16頂点 16-32+16=0 16面42辺24頂点 16-42+24=-2

正多面体が 5種類しかない ことの証明

プラトンの立体 正四面体 正八面体 正二十面体 正六面体 正十二面体 面の形 正三角形 正三角形 正三角形 正四角形 正五角形 各頂点に 集まる 辺の数 3 4 5 3 3 面の数 4 8 20 6 12 辺の数 6 12 30 12 30 頂点数 4 6 12 8 20

プラトンの立体 正四面体 正八面体 正二十面体 正六面体 正十二面体 面の形 正三角形 正三角形 正三角形 正四角形 正五角形 各頂点に 集まる 辺の数 3 4 5 3 3 次の条件をすべてみたす多面体を正多面体と呼ぶ. (1) 凸である. (2) どの面も合同な正多角形である. (3) どの頂点にも同じ本数ずつ辺が集まる.

正多面体は5種類しかない 定理 正多面体は5種類(プラトンの立体)しかない. 証明). Sを正多面体とする. Sの各面は正n角形(n≥3), 各頂点にはd本(d≥3)ずつ辺が集まるとする. Sの面,辺,頂点の数をそれぞれf,e,vとおく. 正多面体の条件(1)とオイラーの多面体定理より f-e+v=2. 正多面体の条件(2)より nf=2e. 正多面体の条件(3)と握手補題より dv=2e. ∴ dnf - dne + dnv = 2dn. ∴ 2de - dne + 2ne = 2dn. ∴ 2d - dn + 2n = 2dn/e > 0. ∴ (2-n)(d-2) + 4 > 0. ∴ (n-2)(d-2) < 4. よって, (n,d)は(3,3), (3,4), (3,5), (4,3), (5,3)のいずれかである. それぞれについて, 正四,八,二十,六,十二面体しか存在しない.// 両辺に dmをかける