グラフ理論入門 ８ グラフの図
８ グラフの図
8.1 平面的グラフ
- 単純曲線(simple curve)
- 単純閉曲線(simple closed curve)
- ジョルダンの曲線定理(Jordan Curve Theorem):どんな単純閉曲線も平面を2つの領域、内部と外部とに分割する。
- 平面的グラフ(planar graph)
- 辺を交差させることなく、平面に描くことのできるグラフ。
- ※辺を交差させずに平面上にグラフを描くことは、辺を交差させずに球の表面にそのグラフを描くことと同じである。
- 平面図(plane drawing)
- 辺を交差させることなく平面上に得たいが「グラフの図」である。
- ※グラフとそれを描いた図とは別物であることに注意する。
- 面(faces)と領域(regions)
- 平面的グラフの平面図において、その辺によって作られる多角形のことを面または領域と言う。
- 極大平面的(maximal planar)
- 平面的グラフがあり、その隣接していない任意の2頂点間に辺を加えると非平面的となる場合、このグラフは極大平面的であるという。
8.2 4色定理
- 地図(map)
- 連結で、橋を持たない平面的多重グラフの平面図を地図と呼ぶ。
- 正規地図(normal map)
- 地図であって、3-正則でもある多重グラフを正規地図と呼ぶ。
- 国(countries)
- 地図における領域のこと。
- 隣接(adjacent)
- 2つの国が共通の辺を持つとき、その2つの国は隣接していると言う。
- 地図の彩色(coloring)
- 地図において、どの隣接2国も同じ色とならないように色を割り当てること。
- 双対(dual)
- 正規地図Mに対して、各国の中央に1頂点を置き(首都(capital))、隣接関係にある国の首都通しを辺で結ぶことでできる平面図(G(M))をMの双対と呼ぶ。
- 正規地図であるMの各頂点の次数は3であるから、Mの双対G(M)の平面図の各領域は三角形である。
8.3 5色定理
8.4 グラフと幾何学
- 凸(convex)
- 平面的グラフの平面上における領域が凸であるとは、その領域およびその領域の境界上の任意の2点を結ぶ線分が、その領域に含まれている場合を言う。
- 伸張可能(stretchable)
- 平面的グラフGの辺がすべて線分となる平面図が存在するとき、Gは伸張可能であると言う。
- コイン(coin)とコイングラフ(coin graph)
- 平面上に互いに重ならない有限個の円の集合を与え、これらの円をコインと呼ぶ。コインの中心を頂点と考え、2つのコインが接触するとき、この2コインは隣接するとみなし、2コインの中心を辺で結び、グラフを構成する。このような方法で構成されるグラフをコイングラフと呼ぶ。
- すべてのコインの大きさが等しい場合に、ペニーグラフと呼ぶ。
- [グラフ]グラフ理論入門 ９ 平面性への近さの測定
９ 平面性への近さの測定
9.1 交差数
- 細分(subdivision)
- 細分とは、グラフの辺上に次数2の頂点を付け加えて得られるグラフを意味する。
- 単純図(simple drawing)
- グラフの平面上の図は、次の条件を満たすとき、単純図であると言う：
- (1)異なる2辺は高々1つの交差点を持つ。
- (2)同じ頂点に接続する2辺は交差しない。
- (3)3辺が共通の点で交差することはない。
- グラフの平面上の図は、次の条件を満たすとき、単純図であると言う：
- 多重点(multiple crossing)
- 3つ以上の辺が交差する点。
- 交差数(crossing number,cr(G))
- グラフを多重点なしに平面上に描くとき、交差点の個数が最小のものが少なくとも1つある。この最小数をGの交差数と呼ぶ。
- 交差点の個数が交差数であるような図は常に単純図である。
9.2 厚みと離散数
- 厚み(thickness,θ(G))
- グラフGを平面的な部分グラフに分解したときの、平面的部分グラフの最小個数のこと。
- 平面性への近さ
- 交差数と厚みは平面性への近さの測定の例である。
- 同一視(identifying)と分離(splitting)
- Gをグラフとし、u,vをその頂点とする。uとvを新しい頂点wに置き換え、新しいグラフG'を構成する。ただし、wはGにおいて、uまたはｖと隣接していたすべての頂点とG'において隣接する。このようなにG'を構成することを同一視と言う。
- 逆に、Gの1頂点wを2つの新しい頂点u,vに置き換え、wが隣接していた頂点を2分して、uまたはvに隣接させることで新しいグラフG'を構成する。このようにG'を構成することを分離と呼ぶ。
- 分離数(splitting number,σ(G))
- 頂点分離によってGを平面的グラフに変えるのに要する頂点分離の最小回数である。
- 平面的分離(planar splitting)
- グラフGを分離数回数の分離によって平面的グラフHを構成したとき、HをGの平面的分離と呼ぶ。
9.3 ヒーウッドの帝国問題
