組合せとグラフの理論(塩田)2023年度 第9回

 今日のテーマは「グラフの平面性」です。 グラフはいつも平面の上に描いているのに「何を今さら」と思うかもしれませんが、 例えば図の $K_4$ では $ux$ と $vw$ は本当は交点を持っていないのに、 初学者はそこに交点があるように誤解してしまいます。

そこで、交点を持たない辺同士は交わらないように描画したいな、というのが平面性の考え方です。

  1. 平面性の定義
  2. クラトフスキーの定理
  3. オイラーの公式
  4. 交差数と厚さ
  5. デモ動画、今日のまとめと宿題