kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

平面グラフ(plane graph)、彩色(cloring)、木(tree)

平面グラフ(plane graph)

辺が交差しないように平面上に描けるグラフ(多重グラフを含む)は、平面的(planer)であるといい、特に、有限多重グラフの平面表現は地図(map)(または単に平面グラフ(plane graph))と呼ばれる。平面グラフと同型なグラフのことを平面的グラフ (planar graph) という。

  • 領域(region)の次数(degree):領域rの境界の閉路または閉じた歩道の長さを領域rの次数(degree)という。

planeGraph
 \deg (r_1)=3, \deg (r_2)=3, \deg (r_3)=5, \deg (r_4) = 4, \deg (r_5)=3
 r_3の境界である閉じた歩道は (C,D,E,F,E,C)


各辺は、2つの領域の境界であるか、領域にふくまれるかのいずれかであり、
後者は、領域の境界に沿ったどんな閉じた歩道においても2度現れるため、(頂点の次数と同様に、)
 \sum_r \deg(r) = 2|E|\cdots (1)
が成り立つ。

Eulerの公式(Euler's formula)

連結平面グラフG(V,E)の領域の個数をRとしたとき、
 |V| - |E| + R = 2 \cdots (2)
(証明)
頂点が一つだけのグラフの場合、 |V|=1, |E|=0, R=1なので(2)を満たす。
他の場合の連結平面グラフは、頂点が1つだけのグラフに、次の(I)または(II)の操作をすることで構成される。

  • (I):新しい頂点v2を加え、それまでの辺と交差しないように、v2ともとからある頂点v1を結ぶ辺を加える
  • (II):それまでの辺と交差しないように、もとからある頂点v1,v2間を結ぶ辺を加える

(I)の操作では、|V|と|E|の値がどちらも1増えるので、操作後も|V|-|E|+Rの値は変わらない。
(II)の操作では、|E|とRの値がどちらも1増えるので、操作後も|V|-|E|+Rの値は変わらない。
したがって、1個の頂点だけのグラフのときと同じ|V|-|E|+Rの値を持たなければならない。
以上より、(2)が成り立つ。(証明終わり)

  • 連結平面的グラフG(V,E), |V| = p \geq 3, |E| = q を考えたとき、

 q \leq 3p-6 \cdots (3)
(証明)
Gの平面的表現における領域の数とすると、Eulerの公式(2)より、
 p-q+r = 2\cdots (a)
また、(1)より、領域の次数の和は2qに等しい。各領域の次数は3以上なので、
 2q\geq 3r
これを(a)に代入すると、
 2 = p-q+r \leq p - q + \frac{2q}{3}
すなわち 2\leq p - \frac{q}{3}
両辺に3をかけて、(3)が得られる。(証明終わり)

Kuratowskiの定理(Kuratowski's theorem)

グラフが非平面的であるのは、 K_{3,3}または K_5と同窓な部分グラフを含むときかつそのときに限る。 \cdots (4)
Kuratowski's theorem - Wikipedia, the free encyclopedia
 K_{3,3}は各頂点の次数が3の2部グラフ(設備グラフ(utility graph)).
 K_5は頂点が5つの完全正則グラフ.

  • 彩色(coloring) 隣接した頂点が異なる色を持つようにGの拡張点へ色を割り当てることを頂点彩色(vertex coloring)または、彩色(coloring)という。n色が使われるGの彩色が存在するとき、n-彩色可能(n-colorable)であるという。

染色数(chromatic number):グラフGを塗るのにひつような色の最小数をGの染色数といい、 \chi (G)と書く。

Welsh–Powellアルゴリズム(Welsh–Powell algorithm)

Gを彩色するアルゴリズム
※このアルゴリズムで染色数は決定できない(塗る色の数が最小になるとは限らない)
離散数学―コンピュータサイエンスの基礎数学 (マグロウヒル大学演習)ではWelchという表記になってますが、ググったところwelshの方が多数派ぽいのでwelshにしときました。

//グラフGの頂点をv[i](i = 0, 2, ..., n-1)とする
Step1. deg(v[i])を求める。(i = 0, 2, ..., n-1)
Step2. deg(v[i])の降順に頂点vをソートする。
Step3. 以下の操作を全ての頂点が彩色されるまで繰り返す。
Step3-1. 新しい色にCを更新し、無色で一番次数が高い頂点v[k]に色Cを塗る。
Step3-2. v[k]と隣接していない無色の頂点すべてに色Cを塗る。

Boost.GraphでWelsh–Powellアルゴリズムを実装している方がいたのでリンク貼っときます。
グラフ理論 Welsh-Powellの頂点彩色アルゴリズムを実装してみた - devm33の備忘録
Welsh-Powellで彩色数にならない例 - devm33の備忘録

  • グラフGについて

Gは2-彩色可能
 \equivGは2部グラフ
 \equivGの各閉路が偶数の長さを持つ \cdots (5)

  • 双対グラフ(dual graph): 地図すなわち有限多重平面的グラフGの、各領域の中に1つ頂点をとり、2つの領域が共通の辺を持つとき、その共通な辺と交差する曲線で対応する頂点を結ぶ辺を加えたとき、その辺を互いに交わらないように書くことができる。このようにしてできたグラフG*は双対(dual)であるといい、G*をGの双対グラフ(dual graph)という。また、GはG*の双対グラフになっている。

dualgraph
双対グラフの作り方の例(Cats Going Straight II(AOJ No.0273))

4色定理(four color theorem)

全ての平面的グラフは(頂点)4-彩色可能である \cdots (6)
※プログラムによる網羅的証明 Four color theorem - Wikipedia, the free encyclopedia

  • 森(forest): 閉路を持たない、無閉路的(acyclic)、非閉路的(cycle-free)なグラフ。(森の連結成分は木)。
  • 木(tree): 連結な森。
  • 退化木(degenerate tree): 1個の頂点で構成され、辺を持たない木。
  • Gを2個以上の頂点を持つグラフとするとき、

Gは木である。
 \equivGの頂点の全ての対は、ちょうど1個の道で結ばれている。
 \equivGは連結であるが、どの辺を除いても非連結なグラフになる。
 \equivGは非閉路的であるが、どのように辺を加えても、ちょうど1個の閉路をもつグラフになる。 \cdots (7)

  • Gをn>1個の頂点を持つ有限グラフとするとき、

Gは木である。
 \equivGは非閉路的であり、n-1本の辺を持つ。
 \equivGは連結であり、n-1本の辺を持つ。 \cdots (8)

  • Gが木(または森)

 \RightarrowGは2-彩色可能である。
 \RightarrowGは2部グラフである。 \cdots (9)
逆は真ではない。

全域木(spanning tree):

TがGの部分グラフで、Gの全ての頂点を含んだ木であるとき、Tを全域木という。とくに、辺の長さの総和が最小になる全域木を最小全域木(minimum spanning tree)という。

根付き木(rooted tree):

指定された木の根(root)を持つ木。

  • 水準(level)、深さ(depth): 根rから頂点vまでの道の長さは、vの水準(level)または、vの深さ(depth)とよばれる。
  • 葉(leaf): r以外の次数1の頂点
  • 枝(branch): 頂点から葉までの道
  • 範囲(scope): 頂点vを根とし、vに後続する頂点全てを含む部分木

根rからuを含むvへの道があるとき、uはvに先行する(preceedes)、あるいは、vはuに後続する(fllows)という。
特に、vがuに後続していて、uに隣接しているなら、vはuの直後(immediately follows)であるという。

  • 順序根付き木(ordered rooted tree): 拡張点から出る辺が順序つけられている根付き木。