グラフ理論

    更新日時 2021/03/11

    オイラーの多面体定理の証明

    オイラーの多面体定理:

    任意の(穴のない)多面体において,頂点の数を VV, 辺の数を EE, 面の数を FF とおくと,VE+F=2V-E+F=2 が成立する。

    → オイラーの多面体定理の証明

    オイラーグラフの定理とその証明

    一筆書きの条件:

    連結なグラフにおいて,

    オイラーグラフ⇔全ての頂点の次数が偶数

    準オイラーグラフ⇔次数が奇数であるものがちょうど2つ

    → オイラーグラフの定理とその証明

    2014年JJMO本選第4問の解説

    組み合わせの良問です。JJMO(日本ジュニア数学オリンピック)の組み合わせの問題はJMOの対策にもなります。

    証明だけでなく,考え方や重要なテクニックも紹介します。

    → 2014年JJMO本選第4問の解説

    ラムゼーの定理と6人の問題

    ラムゼー問題:6人いると互いに知り合いである3人組か互いに知らない3人組が存在することを証明せよ。

    「パーティー問題」「Theorem on friends and strangers」などとも呼びます。

    → ラムゼーの定理と6人の問題

    握手の補題とエルデシュガライの定理

    握手の補題

    グラフ G=(V,E)G=(V,\:E) の頂点 vv の次数を dvd_v とおくとき,

    主張1:vVdv=2E\displaystyle\sum_{v\in V}d_v=2|E|

    グラフ理論の最も基本的な定理の一つです。グラフ理論の知識は不要です。前半は簡単,後半はやや難しくなります。

    → 握手の補題とエルデシュガライの定理

    グラフ理論の基礎

    グラフ理論は組み合わせの問題を簡潔に記述するための道具です。

    → グラフ理論の基礎

    Hallの結婚定理とその証明

    Hall(ホール)の結婚定理:頂点集合が U,VU,\:V と分割された二部グラフ GG に対して,以下は同値。

    条件1:UU の頂点を全てカバーするマッチングが存在する

    条件2(Hallの条件):任意の UU の部分集合 AA に対して,AΓ(A)|A|\leq |\Gamma(A)|

    ただし,Γ(A)\Gamma(A)AA と辺でつながっている頂点の集合。

    → Hallの結婚定理とその証明

    二部グラフの最大マッチングと増加道

    グラフが与えられたときに要素数最大のマッチングを求める問題を最大マッチング問題と言う。

    マッチングは離散最適化の最も重要な話題の一つです。

    → 二部グラフの最大マッチングと増加道

    ボロノイ図とその3つの性質

    点(母点)がいくつか与えられたとき,どの点に一番近いかによって平面を分割したものをボロノイ図(Voronoi diagram)と言う。

    三つ目の性質&その証明が美しいのでおすすめです。

    → ボロノイ図とその3つの性質

    美術館定理とその証明

    美術館定理

    穴のない nn 角形の全領域を監視するために必要な監視カメラの台数は高々 n3\big\lfloor\dfrac{n}{3}\big\rfloor

    → 美術館定理とその証明

    ランダムウォークと電気回路

    • グラフ上の単純ランダムウォークについて

    • 電気回路との対応についての定理

    • 定理の応用例

    です!

    → ランダムウォークと電気回路

    深さ優先探索と幅優先探索

    深さ優先探索とは「とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってそこから探索する」という探索方法。

    幅優先探索とは「出発点に近い点から順に探索する」という探索方法。

    この記事では「深さ優先探索」「幅優先探索」について解説します。非常に基本的なグラフ探索のアルゴリズムです。

    → 深さ優先探索と幅優先探索

    極値集合論の美しい2つの定理

    極値集合論(extremal set theory)の美しい定理を二つ解説します。けっこう難しいですが,数学オリンピックを目指す高校生には理解して欲しい内容です。

    → 極値集合論の美しい2つの定理