離散数学平面グラフ

落合 秀也

今日の内容• 平面的グラフ、平面グラフ、彩色、四色定理• ボロノイ図• ドロネー図2

今日の内容• 平面的グラフ、平面グラフ、彩色、四色定理• ボロノイ図• ドロネー図3

平面的グラフ(Planar Graph)とは• 平面上に辺が交差しないように描けるグラフ（または多重グラフ）のこと

4

平面グラフ(Plane Graph) or 地図• 有限多重グラフを平面上に表現したもの (平面表現)• 平面グラフは、平面をいくつかの領域に分割する• 領域rの次数 deg(r)とは、領域を構成する閉じた歩道の辺の数• 次数の総和に関する性質: ∑ deg(r) = 2 |E|

r5

CAB
r1r2r4Fr3

DEdeg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=35

オイラーの公式• 連結な平面グラフにおいて、頂点の個数V、辺の本数E、領域の個数R とするとき

V-E+R=2である

r5CA

B

r1r2r4Fr3DE

左図において・頂点数 = 6・辺の数 = 9・領域数 = 5（確かに6-9+5=2が成立）

6

オイラーの公式の証明(a)のケース: V=1, E=0, R=1  V-E+R=2
平面グラフは、(b)(c)を組み合わせることで構成できる(b)のケース: V, Eはそれぞれ+1、Rは変化しない
よって V-E+Rは変化しない
V-E+R=2(c)のケース: Vは変化しない E, Rはそれぞれ+1である
 V-E+Rは変化しない
追加(a)

(b)

追加(c)

7

非平面的グラフの例• 以下のグラフは平面的ではない。
(理由) 平面的グラフであるとすると、V=6, E=9なので、オイラーの公式より、平面表現ではR=5個の領域を持つ。どの3頂点も互いに結ばれていない(領域ができるなら4辺以上)ことに着目すると、領域の次数の総和は20以上。これは、平面グラフであれば、辺の数が10以上であることを意味し、E=9と矛盾する。

A1

A2A3

B1B2B38

彩色グラフ：頂点彩色• 頂点彩色 (vertex coloring)• 隣り合う頂点を異なる色で塗ること• n色で塗れれば、n-彩色可能(n-colorable) であると言う。

このグラフの場合

4-彩色可能9

Welch-Powellのアルゴリズム• グラフの頂点を、次数の大きい順に並べる• 1番目の頂点を塗るのに1番目の色を使う、その頂点に隣接していない頂点を順に1番目の色で塗っていく• 2番目の色を用いて、同様の操作を繰り返す• 3番目の色を用いて、同様の操作を繰り返す．．．
EA

E, C, B, F, G, H, I, D, A

GBHC

赤赤青青緑 緑DFI

青緑

一般に、何色あれば十分か？
 四色定理(後述)へ

黄10

双対グラフ (Dual Graph)• 平面グラフMの各領域に1つの点を取り、隣接する2つの領域の点を、その隣接する辺に交差する辺で結ぶグラフM*は、Mの双対と呼ばれる。

11

練習：以下の平面グラフの双対グラフを作成せよ

12

解：

13

平面グラフの彩色：面彩色• 面彩色(face coloring)• 隣り合う領域を異なる色で塗ること• n色で塗れれば、n-面彩色可能 であると言う。

• 双対グラフを作って、Welch-Powell の頂点彩色アルゴリズムを適用、頂点の色を領域の色に対応づけする
14

四色定理
• 平面グラフの隣接した領域を異なる色となるように彩色したとき、５色以上を必要としない• すべての平面グラフは 4-彩色可能である

15

実験： 以下のグラフは4-面彩色可能であることを確かめよr4r1r2r3

16

今日の内容• 平面的グラフ、平面グラフ、彩色、四色定理• ボロノイ図• ドロネー図17

ボロノイ図 (Voronoi Diagram)• 距離を定義可能な空間に、複数の点（母点）が与えられたときに、その他の点が、どの母点に近いかで領域分けされた図18

ボロノイ図の定義• 距離空間の有限部分集合 P={p1, …, pn} および距離関数d(pi,pj) が与えられたとする。このとき、
Ri = { x | d(x,pi) ≦ d(x,pj), i≠j}で定義される領域 Ri をボロノイ領域と呼び、集合{Ri} をボロノイ図と呼ぶ。
• ボロノイ領域の境界： ボロノイ境界• ボロノイ境界の交点： ボロノイ点

19

練習• 以下の母点に対して、（おおよその）ボロノイ図を作成してみよ。距離関数としてはユークリッド距離を用いてみよ。

20

解

21

ボロノイ図: 距離関数の違い

ユークリッド距離d(p1, p2)=√{(x1-x2)2+(y1-y2)2}

マンハッタン距離d(p1, p2)=|x1-x2|+|y1-y2|
引用: https://en.wikipedia.org/wiki/Voronoi_diagram

22

ボロノイ図の特徴・性質• ボロノイ点から周辺各領域の母点までの距離は等しい• ボロノイ領域は凸領域である

この角度は π を超えない23

ボロノイ図の応用• 最近傍探索（Nearest Neighbor Search）• ある地点に最も近い母点を探す• 最も近い基地（病院、ガソリンスタンド、レストラン etc.）を探す• 無線通信基地局の配置• 無線端末が、最も近い基地局に接続されると仮定すると、その基地局が通信する端末数 = 領域に含まれる端末数と考えることができる。

• 自律ロボットのナビゲーション• 母点: 障害物
• ボロノイ境界: 最も安全なルート
24

今日の内容• 平面的グラフ、平面グラフ、彩色、四色定理• ボロノイ図• ドロネー図25

ドロネー図 (Delaunay Diagram)

ドロネー三角形分割 (Delaunay Triangulation)• 母点３点が円周上に乗る円を、その内部に他の母点が入らないように作成できるときに、それらの３点を線で結んでできる図• 面を３角形で分割することができる• ただし、3点が1直線上に並ぶ場合や4点が同一円周上に並ぶ場合 (5点～も同様)も含む

正しい例

間違った例

26

練習
以下の母点に対して、(1) ドロネー図を作成してみよ(2) ドロネー図の上にボロノイ図を作成してみよ27

解：ドロネー図28

解：ドロネー図＆ボロノイ図

しかし・・・
ここはおかしい？

Question: ドロネー図とボロノイ図は、双対関係にあるのか？？？
29ドロネー図の特徴・性質• ドロネー図は、ボロノイ図の双対グラフの平面表現である• ボロノイ図の点  ドロネー図の面• ボロノイ図の辺  ドロネー図の辺 (直交)• ボロノイ図の面  ドロネー図の点(*) ドロネー図とボロノイ図が、直接的に双対グラフであるわけではない• ボロノイ図の隣接領域の母点間を結ぶとドロネー図ができる• ドロネー分割時の三角形の外接円の中心がボロノイ点になっている• ドロネー図の母点の周囲には平均しておおよそ6個の領域がある
30

ボロノイ図からのドロネー図の導出

考察： 母点の周囲に、平均的におよそ6個の領域があることを確認しよう31ドロネー図の応用• 局面 z=f(x,y) の三角形近似

引用: http://www.kanenko.com/~kanenko/KOUGI/CompGeo/cpgeoc.pdf• 離散データの補完 (例: 潮流)

32

今日の内容• 平面的グラフ、平面グラフ、彩色、四色定理• ボロノイ図• ドロネー図33