グラフ理論
オイラーグラフの定理とその証明
一筆書きの条件:
連結なグラフにおいて,
オイラーグラフ⇔全ての頂点の次数が偶数
準オイラーグラフ⇔次数が奇数であるものがちょうど2つ
2014年JJMO本選第4問の解説
組み合わせの良問です。JJMO(日本ジュニア数学オリンピック)の組み合わせの問題はJMOの対策にもなります。
証明だけでなく,考え方や重要なテクニックも紹介します。
ラムゼーの定理と6人の問題
ラムゼー問題:6人いると互いに知り合いである3人組か互いに知らない3人組が存在することを証明せよ。
「パーティー問題」「Theorem on friends and strangers」などとも呼びます。
握手の補題とエルデシュガライの定理
グラフ の頂点 の次数を とおくとき,
主張1:
グラフ理論の最も基本的な定理の一つです。グラフ理論の知識は不要です。前半は簡単,後半はやや難しくなります。
Hallの結婚定理とその証明
Hall(ホール)の結婚定理:頂点集合が と分割された二部グラフ に対して,以下は同値。
条件1: の頂点を全てカバーするマッチングが存在する
条件2(Hallの条件):任意の の部分集合 に対して,
ただし, は と辺でつながっている頂点の集合。
巡回セールスマン問題の意味と2近似アルゴリズム
離散最適化の超有名問題である,巡回セールスマン問題(Traveling salesman problem, TSP)について。問題の意味と簡単な近似アルゴリズムについて解説します。
二部グラフの最大マッチングと増加道
グラフが与えられたときに要素数最大のマッチングを求める問題を最大マッチング問題と言う。
マッチングは離散最適化の最も重要な話題の一つです。
ボロノイ図とその3つの性質
点(母点)がいくつか与えられたとき,どの点に一番近いかによって平面を分割したものをボロノイ図(Voronoi diagram)と言う。
三つ目の性質&その証明が美しいのでおすすめです。
深さ優先探索と幅優先探索
深さ優先探索とは「とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってそこから探索する」という探索方法。
幅優先探索とは「出発点に近い点から順に探索する」という探索方法。
この記事では「深さ優先探索」「幅優先探索」について解説します。非常に基本的なグラフ探索のアルゴリズムです。
極値集合論の美しい2つの定理
極値集合論(extremal set theory)の美しい定理を二つ解説します。けっこう難しいですが,数学オリンピックを目指す高校生には理解して欲しい内容です。