組合せとグラフの理論(塩田)第9回 (5) デモ動画、今日のまとめと宿題

デモ動画

 mp4 が再生可能なブラウザでご覧ください。

今日のまとめ

  • グラフの平面性については「平面グラフ」と「平面的グラフ」という2つの概念があります。
  • 「平面グラフ」というのは、描き方に依存した性質です。
  • これに対し「平面的グラフ」は同型で変わらない(描き方に依存しない)性質です。
  • 平面性を判定する「クラトフスキーの定理」は、美しい定理ですが、実用的ではありません。ソフトウェアを組むには他のアルゴリズムを使います。
  • 平面グラフでは「面」を定義することができ、オイラーの公式 $n-m+f=2$ が成り立ちます。これは幾何学の基本的定理でもあります。
  • グラフの平面性を測る目安として「交差数」と「厚さ」が定義されています。

宿題

  • 授業時間に紙媒体で配布しますが、pdf もここから download できます。
  • 提出方法:スキャンしたり写メを撮ったり、pdf を編集したりして、pdf ファイル・画像ファイル等を送信してください。
  • 宛先は shiota@is.kochi-u.ac.jp(@は小文字)
  • 件名は、組合せとグラフの理論第9回の宿題 [自分の学籍番号]
  • 上手く送れない人はメールで連絡してください。
  • 提出期限:6月23日(金) 10:30am