スライド 1

有限幾何学
第7回
有限幾何学第7回
1. 木の性質と最小全域木
用語の説明
2. 木の性質
3. 最小全域木
1.
1.1 用語の説明
森：閉路を含まないグラフ
木：閉路を含まない連結グラフ
全域木：あるグラフの全域グラフで木であるもの
森
木
全域木
1.2 木の性質（木であることと同値な条件①）
木の辺の性質からの特徴づけ
位数3以上のグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(2) T は連結で，全ての辺が橋である．
(3) T の任意の2点は丁度1本の道で結ばれている．
(4) T は閉路を含まないが，
辺を追加すると丁度1つの閉路ができる．
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(2) T は閉路を含まず，|E(T)|= p-1．
(3) T は連結で，|E(T)|= p-1．
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(2) T は閉路を含まず，|E(T)|= p-1．
(3) T は連結で，|E(T)|= p-1．
証明：Tの位数pに関する帰納法
p=1 のとき，(1)～(3)が同値であることは明らか．
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(2) T は閉路を含まず，|E(T)|= p-1．
証明：(1)⇒(2)
T の辺eを除くと，
Tは2つの木 T1,T2 に分離される．
∵ 木の辺の性質からの特徴づけ(2)より
T は全ての辺が橋である．
e
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(2) T は閉路を含まず，|E(T)|= p-1．
証明：(1)⇒(2)
e
帰納法の仮定より，
|E(T1)|=|V(T1)|-1, |E(T2)|=|V(T2)|-1．
∴|E(T)|=|E(T1)|+|E(T2)|+1
=(|V(T1)|-1)+(|V(T2)|-1)+1=|V(T)|-1． T1
T2
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(2) T は閉路を含まず，|E(T)|= p-1．
(3) T は連結で，|E(T)|= p-1．
証明：(2)⇒(3)
Tが非連結とし，Tの連結成分を T1, T2, …, Tp とすると (p ≧ 2)，
各 Ti は閉路を含まない連結グラフ，すなわち木となるので，
帰納法の仮定より，|E(Ti)|=|V(Ti)|-1 (1 ≦ i ≦ p)，
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(2) T は閉路を含まず，|E(T)|= p-1．
(3) T は連結で，|E(T)|= p-1．
証明：(2)⇒(3)
|E(Ti)|=|V(Ti)|-1 (1 ≦ i ≦ p)，
∴ 1≦ p-1 =|E(T)|=|E(T1)|+・・・+|E(Tp)|
= (|V(T1)|-1)+・・・+(|V(Tp)|-1)=|V(T)|-p=0 となり矛盾．
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(3) T は連結で，|E(T)|= p-1．
証明：(3)⇒(1) （教科書とは別の証明）
∀u ∈ V(T) に対して，degT(u) ≧ 2 とすると，
握手補題より，
2p ≦ ∑degT(u) =2|E(T)|=2(p-1) となり矛盾．
u ∈ V(T)
1.2 木の性質（木であることと同値な条件②）
木のサイズからの特徴づけ
位数pのグラフ T に対し，次の各命題は同値．
(1) T は木（閉路を含まない連結グラフ）である．
(3) T は連結で，|E(T)|= p-1．
証明：(3)⇒(1) （教科書とは別の証明）
よってTは次数1の頂点uを持つ．このときT-uは連結で，（∵Tは連結）
|E(T-u)|=|E(T)|-1=p-2=|V(T-u)|-1．
よって帰納法の仮定より，T-uが木となるので
T-uにuを1辺でつなげたTも木であることが分かる．
1.2 木の性質
特徴づけから得られる系1
位数2以上の木は，次数1の頂点を少なくとも2つ含む．
特徴づけから得られる系2
位数p，成分数kの森 T に対し．|E(T)|= p-k
特徴づけから得られる系3
連結グラフは全域木を含む．
系1と系2の証明は省略
1.2 木の性質
特徴づけから得られる系3
連結グラフは全域木を含む．
証明：
G：連結グラフ
T：1辺でも取り除くと連結ではなくなるGの連結な全域部分グラフ
T は連結で，全ての辺が橋なので，
木の辺の性質からの特徴づけ(2)より，Tは木．
よってTはGの全域木となる．
1.3 最小全域木
重み付き連結グラフにおける全域木を考える．
重み付き連結グラフは全域木を含むが，
（∵連結グラフは全域木を含む）
全域木の取り方によってその重みが変わってくる．
5
8
7
7
5
9
15
6
重さ 39
9
8
11
1.3 最小全域木
重み付き連結グラフにおける全域木を考える．
重み付き連結グラフは全域木を含むが，
（∵連結グラフは全域木を含む）
全域木の取り方によってその重みが変わってくる．
5
8
7
7
5
9
15
6
重さ 54
9
8
11
1.3 最小全域木
最小全域木：重み付き連結グラフの全域木の中で重みが最小のもの
最小全域木問題：・最小全域木を求める問題
・効率の良いアルゴリズムが知られている
例：・クルスカルのアルゴリズム
・プリムのアルゴリズム
・クラスター分析やネットワーク・デザインなどの
分野で利用されている
1.3 最小全域木
クルスカルのアルゴリズム
・重み付き連結グラフの最小全域木を求めるアルゴリズム．
・貪欲アルゴリズムという種類に分類される．
貪欲アルゴリズム：各計算ステップで局所的な情報から
その時点で最適なものを選択していくことで
最適解または近似解を求める方法
（クルスカルのアルゴリズムでは最適解）
・入力：重み付き連結グラフ G
・出力：最小全域木 T
1.3 最小全域木
クルスカルのアルゴリズム
入力
5
8
7
7
5
9
15
6
9
8
11
1.3 最小全域木
クルスカルのアルゴリズム
出力
5
8
7
7
5
9
15
6
9
8
11
1.3 最小全域木
クルスカルのアルゴリズム
1. T をGから全ての辺を除いたグラフとする．
2. E={e∈ E(G): e ∉ E(T), T+eに閉路がない} とする．
(i) E ≠ ∅ ならば，Eの中から重みが最小の辺eを選び，
T=T+e とし，再度手順2 を行う．
(ii) E = ∅ ならば終了．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
1：T をGから全ての辺を除いたグラフとする．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
2 (i)：E={e ∈ E(G): e ∉ E(T), T+eに閉路がない} ≠ ∅ ならば，
Eの中から重みが最小の辺eを選び，T=T+e とする．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
2 (i)：E={e ∈ E(G): e ∉ E(T), T+eに閉路がない} ≠ ∅ ならば，
Eの中から重みが最小の辺eを選び，T=T+e とする．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
2 (i)：E={e ∈ E(G): e ∉ E(T), T+eに閉路がない} ≠ ∅ ならば，
Eの中から重みが最小の辺eを選び，T=T+e とする．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
2 (i)：E={e ∈ E(G): e ∉ E(T), T+eに閉路がない} ≠ ∅ ならば，
Eの中から重みが最小の辺eを選び，T=T+e とする．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
2 (i)：E={e ∈ E(G): e ∉ E(T), T+eに閉路がない} ≠ ∅ ならば，
Eの中から重みが最小の辺eを選び，T=T+e とする．
1.3 最小全域木
クルスカルのアルゴリズム
5
8
7
7
5
9
15
6
9
8
11
2 (ii)：E={e ∈ E(G): e ∉ E(T), T+eに閉路がない} = ∅ ならば終了．
1.3 最小全域木
クルスカルのアルゴリズム
このアルゴリズムにより最適解（最小全域木）が得られる．
次に，得られたグラフが最小全域木であることを証明する．
このことを証明するには，
・全域木であること
・重みの最小性
この2つが示せればよい．
1.3 最小全域木
クルスカルのアルゴリズム
全域木：
得られるグラフが全域木であることは簡単に分かる．
∵ 手順2は2つの木を辺でつなぐ操作になるので
最小性：
このことは簡単には分からない．
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：背理法で示す．
クルスカルのアルゴリズムによって得られる
全域木 T がG の最小全域木ではないとする．
T
Gの最小全域木T1を |E(T) ∩ E(T1)| が最大になるように選ぶ．
E(T) – E(T1) に属す辺の中から
クルスカルのアルゴリズムによって最初に選ばれる辺をeとする．
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：背理法で示す．
クルスカルのアルゴリズムによって得られる
全域木 T がG の最小全域木ではないとする．
T1
Gの最小全域木T1を |E(T) ∩ E(T1)| が最大になるように選ぶ．
E(T) – E(T1) に属す辺の中から
クルスカルのアルゴリズムによって最初に選ばれる辺をeとする．
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：背理法で示す．
クルスカルのアルゴリズムによって得られる
全域木 T がG の最小全域木ではないとする．
T T1
e
Gの最小全域木T1を |E(T) ∩ E(T1)| が最大になるように選ぶ．
E(T) – E(T1) に属す辺の中から
クルスカルのアルゴリズムによって最初に選ばれる辺をeとする．
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：
このとき，T1+eはある閉路Cを含む．
Tは木なので ∃f ∈ E(C) –E(T)⊆E(T1)-E(T)．
T T1
e
f
また，T1+e-f は全域木なので
T1 が最小全域木であることより，w(f) ≦ w(e)．
w(f)=w(e) とすると T1+e-f が最小全域木となり，
T1を|E(T) ∩ E(T1)|が最大になるように選んだことに矛盾．
∴ w(f) < w(e)
C
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：
ここまでのまとめ
(1) e：E(T) - E(T1) に属す辺の中から
クルスカルのアルゴリズムによって最初に選ばれる辺
(2) f ∈ E(T1) - E(T)
(3) w(f) < w(e)
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：
クルスカルのアルゴリズムによって
eを追加する1つ手前のグラフを T’とする．
このとき(1)より，T’ は T1 の部分グラフ．
(1) e：E(T) - E(T1) に属す辺の中から
クルスカルのアルゴリズムによって最初に選ばれる辺
1.3 最小全域木
クルスカルのアルゴリズム
最小性の証明：
T’ は T1 の部分グラフなので(2)より，T’+ f には閉路がない．
しかし，(3)とアルゴリズムの手順2より，T’+ f は閉路を含み矛盾．
(2) f ∈ E(T1) - E(T)，
(3) w(f) < w(e)
手順2. E={e∈ E(G): e ∉ E(T), T+eに閉路がない}
の中から重みが最小の辺eを選び，T=T+e とする．
提出課題7
問題1： P.55 問3.6 (a), (b)
注意：教科書P.53のプリムのアルゴリズムを各自で読むこと
問題2：Gが木で，Gの頂点の次数が全て奇数ならば，
辺の個数は奇数であることを示せ．
問題２のヒント・握手補題を用いる
・|V(G)| - 1= |E(G)| を用いる
提出課題7
問題3(提出しなくてもよいです)：
次数がkの頂点をl個持つ木は次数1の頂点を
少なくとも(k-2)l+2個持つことを示せ．
ヒント・握手補題を用い
・|V(G)| - 1= |E(G)| を用いる
提出課題7
問題4（提出しなくてもよいです）：
50×600の格子になっているネットがある．
このネットを二つに分けるとすると，最大でいくつの
格子を作っている単位の糸を切ればよいか？
ヒント：① 格子をグラフ，糸の切断を辺の除去とみなして考える
② 連結グラフの極小連結部分グラフは木

Download Report