グラフ理論

    更新日時 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の結婚定理とその証明

    平面グラフとオイラーの定理の応用

    完全グラフ K5K_5 および完全二部グラフ K3,3K_{3,3} は平面的グラフでない(平面に交差なしで書けない)。

    → 平面グラフとオイラーの定理の応用

    安定マッチングとGale-Shapleyアルゴリズム

    Gale-Shapleyアルゴリズムを用いて安定マッチングを求めることができる。

    → 安定マッチングとGale-Shapleyアルゴリズム

    巡回セールスマン問題の意味と2近似アルゴリズム

    離散最適化の超有名問題である,巡回セールスマン問題(Traveling salesman problem, TSP)について。問題の意味と簡単な近似アルゴリズムについて解説します。

    → 巡回セールスマン問題の意味と2近似アルゴリズム

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

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

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

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

    四色定理の紹介と五色定理の証明

    四色定理

    任意の地図は四色で塗り分けることができる。

    → 四色定理の紹介と五色定理の証明

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

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

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

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

    美術館定理とその証明

    美術館定理

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

    → 美術館定理とその証明

    隣接行列,接続行列,ラプラシアン行列

    グラフに対応するいろいろな行列を紹介します。 線形代数の議論でグラフの性質が分かるという素敵な理論のための道具です。

    → 隣接行列,接続行列,ラプラシアン行列

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

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

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

    • 定理の応用例

    です!

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

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

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

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

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

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

    強連結成分分解の意味とアルゴリズム

    深さ優先探索を2回すれば強連結成分分解できる。

    → 強連結成分分解の意味とアルゴリズム

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

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

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

    デルタマトロイド

    以前,マトロイドというものについて紹介しました。→マトロイドの定義と具体例

    この記事では,マトロイドの一般化であるデルタマトロイドについて紹介します。

    → デルタマトロイド