タグ: グラフ理論

← タグ一覧

• 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法禁止された部分グラフをもたないグラフの辺数の最大値（Mantel・Turán・Kővári–Sós–Turán）、彩色に必ず現れる単色の構造（Ramsey・Schur）、数え上げによる存在証明（Erdős の下界、内周も彩色数も大きいグラフ）を証明する。数学グラフ理論学部グラフ理論Turán の定理Ramsey の定理確率的方法極値問題約 52 分
• 彩色：Brooks の定理・Vizing の定理・彩色多項式Brooks・Mycielski・König・Vizing の定理、彩色多項式と Whitney の展開、平面的グラフの 5-リスト彩色可能性（Thomassen）、弦グラフと弱パーフェクトグラフ定理（Lovász）を、証明を省かずに示す。数学グラフ理論学部グラフ理論彩色数辺彩色彩色多項式パーフェクトグラフ約 61 分
• Kuratowski の定理：マイナーと平面性の判定グラフが平面的であることと K_5・K_{3,3} の細分を含まないことの同値性を、3-連結グラフの縮約できる辺と凸な描画の構成（Thomassen の方法）で証明し、Wagner の定理、Fáry の定理、Whitney の一意性定理、外平面的グラフの特徴づけを導く。数学グラフ理論学部グラフ理論平面的グラフKuratowski の定理マイナー3-連結グラフ約 41 分
• 道・閉路・木：Euler 回路と Hamilton 閉路有限グラフの基本語彙を整え、握手補題、二部グラフと奇閉路、木の 6 つの特徴づけ、Euler の定理、Dirac・Ore・Bondy–Chvátal の Hamilton 閉路の十分条件、Havel–Hakimi の定理を、最長の道を取る論法を軸に証明する。数学グラフ理論学部グラフ理論木Euler 回路Hamilton 閉路次数列約 34 分
• 四色定理：地図が4色で塗れる理由と、コンピュータが書いた最初の証明「隣り合う国を違う色にするには4色で足りる」という四色定理を、オイラーの公式から導く六色定理・五色定理の証明とともに追い、1976年のコンピュータ支援証明が数学に残した問いまで扱います。数学数学コラム高校〜一般グラフ理論四色定理平面グラフ彩色コンピュータ支援証明約 37 分