前へ / 戻る

デモ動画

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

• $K_{2,n}$ の平面性( 271KB )
• 正八面体グラフの平面性( 328KB )
• $\overline{C_6}$ の平面性( 550KB )
• ランダムグラフの平面性( 661KB )

今日のまとめ

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

宿題

• ここから download してください。
• 提出期限：6月25日(金)
• 提出方法：スキャンするか写メを撮るなどして、pdf ファイル・画像ファイル等を shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。
  • 上手く送れない人はメールで連絡してください。
  • ＠の後ろは is.kochi-u.ac.jp です。皆さんの s.kochi-u.ac.jp より1文字多いのでお間違え無いように。
• 件名に「組合せとグラフの理論第9回の宿題」と書いておいて頂けると有難いです。
• 宿題を複数回分まとめて提出されると見落とす危険があります。１回分ずつ送信してください。

前へ / 戻る