平面グラフ
- 2. 平面グラフ 平面グラフの定義 以下の条件を満たす有限集合の組 (V,E ) ただし、V は頂点集合、 E は辺集合 (1) V ? R2 (2) 各辺は2つの頂点を結ぶ弧である。 (3) 異なる辺の端点は異なる。 (4) 辺の内部は、頂点も他の辺の点も含まない。
- 3. 平面グラフの例
- 5. 本当に平面グラフでないのか Euler の定理 連結な平面グラフの頂点数、辺数 、面数をそれぞ れ n,m,l としたとき、 n-m+l=2 が成り立つ。 辺数の帰納法で証明できる。 この定理を使えば、簡単に K5 , K3,3 が平面グ ラフでないことがわかる。
- 7. 有名事実 平面グラフである ? K5 , K3,3 をマイナーに含まない これは、 遅い!!
- 8. アイディア グラフ G(V, E)が平面あるには、すべての非可分成 分が平面であればよい。 (それぞれの非可分成分での平面埋め込みが得られ れば、容易に得られる) だから、 G が非可分成分のときを考えればよい。
- 9. アイディア st-番号付け (s,t) を任意の辺としたとき、グラフ G が非可分 であるならば、s,t と異なる頂点 v は v よりも大き い番号の頂点と小さい番号の頂点のどちらとも隣 接しているように頂点の番号付けが可能である。 ただし、s の番号は 1、t の番号は n=|V| である。
- 10. 例 s=1,t=5 ５ 1１
- 12. アイディア 以降、st-番号付けでつけた頂点番号で考える。 Gk を頂点 1~k からなる G の誘導部分グラフとす る。 Gk (Vk , Ek ) が平面グラフのときに、Gk に点 k+1 を追加して、Gk+1 が平面グラフであるかを判 定したい。
- 13. 例 G1 １ ５２ ３ ４
- 14. 例 G2 １ ５ ２ ３ ４
- 15. 例 G2 １ ５ ２ ４ ３
- 16. 例 G2 １ ５ ２ ４ ３
- 17. 例 G3 １ ５ ２ ４３
- 18. 例 G3 １ ５ ２ ４３
- 19. 例 G4 １ ５ ２ ４３
- 20. 例 G5 １ ５ ２ ４３
- 21. どうすればよいのか P 点を可分点、Q 点を非可分成分とすると、 P 点から出ている辺の順序は反転以外できず、 Q 点から出ている辺の順序は自由に置換できるの で、そのような操作を繰り返して、k+1 番目の頂 点が連続するようにならべかえると、交わらな いように辺が引ける。
- 22. 例 G1 Ｐ
- 23. 例 G2 ＰＰ
- 24. 例 G3 Ｐ ＰＰ
- 25. 例 G3 Ｐ ＰＰ
- 26. 例 G4 Ｐ ＰＰ Ｐ
- 27. 例 G4 Ｑ
- 28. 例 G5 Ｑ Ｐ
- 29. 例 G5 Ｑ
- 33. ありがとうございました。