グラフ理論 配布資料 #6 (教科書 pp. 60 〜 66 の内容)
担当 : 井上 純一 (情報科学研究科棟 8-13)
平成 17 年 5 月 23 日

目次
77.162木の基本的な性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7.2

全域木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7.3

基本閉路集合と基本カットセット集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

木とその数え上げ

演習問題 5 の解答例
1. まずは点数 n = 4 の場合の二部グラフの例を図 84 に載せるが, これは明らかにハミルトン閉路を含むのでハミルトン・グラフである. 次に n = 6 の場合の二部グラフの一例とその同形なグラフを図 85 に

n=4

図 84: n = 4 の場合の二部グラフの例.
載せるが, これも明らかにハミルトン閉路を含むのでハミルトン・グラフである. これら 2 つの例から

n=6

図 85: n = 6 の場合の二部グラフの一例とそれと同形なグラフ (下). 閉路が存在する.

60

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

わかるように, 二部グラフを白点と黒点が交互に来るように閉路グラフとして描ける場合には必ずハミルトン・グラフになる.
一方, n が奇数の場合には図 86 に n = 7 の例で示すように, このような白, 黒点の配置は不可能であり, 必ず閉路上には黒黒, あるいは白白が並んでしまう. 従って, 二部グラフはその点数が奇数の場合

n=7

図 86: n = 7 の場合には二部グラフを閉路で表現することができない.にはハミルトン・グラフにはならない.

2. まず, 問題に与えられたグラフの中央の点を除去したグラフを考えると, これにはハミルトン閉路が存在する (図 87 参照). 以下の議論ではこれを基準として考える. また, 話の見通しを良くするため, この閉路と同形なグラフを考えることにしょう (図 87 の下図). 問題のグラフはこのグラフに 1 点を加え121131427812111210569109834576

図 87: 問題に与えられたグラフの中央の点を除去すると, それはハミルトン・グラフでハミルトン閉路が存在する.て, その点 (13 としょう) と図 87 の点 2,4,6 とを結んでできるので, それを具体的に描くと図 88 のようになる. そこで, このグラフでは点 13 は点 2,4,6 と点 3,5 に「1 つ飛ばし」で結ばれていることから,点 2 を出発して, 点 3,4,5, 及び, 点 13 を経由して点 6 に至るためには, 必ず, 点 3 か点 5 にはとまらずに通過しなければならないことに注目しよう. また, 点 2 から 2 → 3 → 4 と進んで, 点 9 に移った
場合には, 9 → 8 と進むと, それ以後部分グラフ {10, 11, 12} には進めなくなり, 逆に, 9 → 8 へと移った場合には部分グラフ {6, 7, 8} へは進めなくなる.
このことから直ちに全ての点を 1 回ずつ通って元に戻る閉路は存在しないことがわかるので, このグラフはハミルトン・グラフではないことになる. もちろん, ここで考えた経路以外にも点 1 → 点 12→ · · · のように回る経路も存在するが, 結局, ここで考えた, 点 {2, 3, 4, 5, 6, 13} を含んだ「部分グラフ」にぶつかれば上記の問題が生じ, 決してハミルトン閉路を描くことはできないことになる.
ここは 61 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

12111210398457613図 88: 問題に与えられたグラフと同形なグラフ. このグラフにハミルトン閉路があるか否かを考察すればよい.

7木とその数え上げ
今回と次回の 2 回の講義では系統図や分子構造, あるいはコンピュータのファイルシステム等, 多くの現象/対象を表現することのできる, 簡単な構造ではあるが重要なグラフである「木」, 及び, その数え上げ法(Cayley の定理とその系）について学習する. なお, 教科書 pp. 72-82 の「応用の追加」に関しては, 情報工学演習 II(B) で演習問題を通じて見て行く予定なので, この講義では触れない.

7.1

木の基本的な性質

ここでいう「木」とは次のようにグラフ「林」の特別な場合として定義される.
林 (forest) : 閉路を含まないグラフ.
木 (tree) : 連結な林.
例えば, 図 89 に載せたグラフが林であり, 3 つある成分のうちの各々が木である.

図 89: 林の例. 3 つある成分の各々が木に相当する.

これらの木の基本的な性質は次の定理によりまとめられている. 証明は教科書 p.61 を読んでもらうことにして, 講義では説明しない. 各命題を例に挙げた木に当てはめて確認されたい.

ここは 62 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

定理 9.1
点 n 個からなるグラフ T を考えるとき, 次の各命題は同値である.

(i) T は木である.
(ii) T には閉路は無く, 辺が n − 1 本ある.
(iii) T は連結であり, 辺が n − 1 本ある.
(iv) T は連結であり, 全ての辺は「橋」である.
(v) T の任意の 2 点を結ぶ道はちょうど 1 本である.
(vi) T に閉路は無いが, 新しい辺をどのように付け加えても閉路ができ, しかも, 1 個の閉路である.

ここで, 上の定理の命題 (ii)(iii) より, 林 G の辺の数に関して次の系が得られる.
系 9.2
林 G には n 個の点と k 個の成分があるとする. このとき, 林 G には n − k 本の辺がある.

(証明)
閉路が無く連結だとすると, n − 1 本の辺がある. これから辺を 1 本ずつ切断する操作を進めると1 本辺を切断すると⇒成分数 2, n − 2 本の辺2 本辺を切断すると⇒成分数 3, n − 3 本の辺3 本辺を切断すると⇒成分数 4, n − 4 本の辺··· ··· ······ ··· ···k − 1 本辺を切断すると⇒成分数 k, n − k 本の辺となる. (証明終わり).
さらに, 定理 9.1 の (ii) より木の端点数に関して次の系が得られる.
系 9.3
単点でない木は, 少なくとも 2 点の端点を含む.

(証明)
木 T : V (T) = {v1 , v2 , · · · , vp }, p ≥ 2, E(T) = {e1 , e2 , · · · , eq } とすると, 定理 9.1(ii) よりq= p−1であり, 辺の総数の 2 倍はグラフの次数に等しい (握手補題) :pdeg(vi ) =2qi=1

から直ちに
pdeg(vi )= 2(p − 1)

i=1

ここは 63 ページ目グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一が得られる. 従って, 木の端点が 0, 1 だとすると, 上式右辺が負またはゼロとなり, 点の数が 2 以上のグラフに対する次数の定義に反する. (証明終わり).

7.2

全域木

全域木 (spanning tree) : 連結グラフ G に対し, 閉路が無くなるまで辺を除去して残るグラフ (図 90 参照).
これを一般化すると全域林 (spanning forest) : n 個の点と m 本の辺, k 個の成分があるとして, G の各成分に対して, 閉路が無くなるまで辺を除去する操作を繰り返して得られるグラフ.
vwe6v

we3e3e1e4e1e4e2e2e8xe5ye7zxyz

図 90: 連結グラフから生成された全域木の一例.

閉路階数 (cycle rank) γ(G) : 全域林を得るまでに切断しなければならない辺の本数.

γ(G) ==(G の辺数) − (n 個の点, k 成分からなる林 G の辺数)m − (n − k)(系 9.2 より) = m − n + k

カットセット階数 (cutset rank) ξ(G) : 全域木の辺数

ξ(G)

=n−k

当然, γ(G) と ξ(G) の間には γ(G) + ξ(G) = m の関係がある.
定理 9.3

T がグラフ G の全域林ならば(i) G の全てのカットセットは T と共通な辺を持つ.
(ii) G の全ての閉路は T の補グラフと共通な辺を持つ.

(証明略) : 教科書 p. 63 を読んでおくこと.

ここは 64 ページ目

グラフ理論 2005

7.3

担当 : 大学院情報科学研究科 井上 純一

基本閉路集合と基本カットセット集合

木 T に関連した基本閉路集合 : T に含まれない G の任意の辺を一つ T に付加すると, 閉路が一つできる.
この操作によりできる閉路の集合を基本閉路集合と呼ぶ (その一例として図 91 参照).

vwv
e3e1e4we4e2e3e2xe8yvyzvvzwe6e3e1e4e2e3e2xe5yye7zz

図 91: 基本閉路集合の一例.

木 T に関連した基本カットセット集合 : T の各辺を除去して得られるカットセット集合 (その一例を図 92に載せる).

vw

e3e1xe2e4yzv

V2we1

V1{e1,e5}xe5yz

図 92: 基本カットセット集合の一例.

ここは 65 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

✬✩

例題 14
G が連結グラフであるとき, G の中心 (centre) とは次のような点 v のことである : v と G の他点の間の距離の最大値ができるだけ小さい. このとき, 以下の問いに答えよ.

(1) 端点を除去する操作を続けて行くことにより, 図 93 の木 T の中心を求めよ.
(2) どんな木でも中心は 1 つか 2 つであることを示せ.
(3) 木の中心が 2 つある場合, それらの 2 点は隣接していることを示せ.
(4) 7 点からなる木で, 中心が 1 つの木と, 2 つの木をそれぞれ一つずつ例示せよ.
✫✪

(解答例)
4T

596
8

2107

3
11211181413171516

図 93: この木 T の中心を考える.

(1) 問題文中に与えられた木 T に対し, 「端点を除去する操作」1 を行うと, 1 回目に削除される端点グルー
プは {1, 2, 4, 5, 8, 9, 12, 13, 15, 16} であり, 2 回目に削除される端点グループは {3, 6, 10, 14, 17}. そして, 最後に削除される端点グループは {7, 8} である. 従って, これら一連の操作により最後まで生き残る木 T の中心は 11 である.

(2) 仮に木の中心が 3 つあるとする. このとき, 定理 9.1 (iv) から, 木の全ての辺は橋になっていることから, 端点を除去していく操作により, 残る木としては図 94 の場合しかない. この場合に対して, さらに次の 2 通りの可能性があり得る.

(I) 点 1 と点 2 に結合している成分の大きさが等しい場合(II) 点 1 と点 2 に結合している成分の大きさが異なる場合(I) の場合について考えると, 点 1 と点 2 と v に接続する 2 つの辺を除去することにより, 唯一の中心v が得られる.
(II) の場合に関して, 点 2 に結合している成分の方が大きいとすると, 点 1 と点 v を結ぶ辺を除去する
ことにより, (v, 2) という 2 つの中心が得られる.
従って, (I)(II) のいずれの場合にしても, 木の中心が 3 つあるという可能性はあり得ず, 必ず, 引き続く除去のプロセスにより, 1 つまたは 2 つの中心に行き着くことになる.
1 ここで言う「端点を除去する操作」とはもう少し正確に言うと, この解答に示したように「端点のグループを除去する操作」のことです.

ここは 66 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

2v

1

図 94: 端点を削除することによってできるグラフの一例.

(3) もしも仮に, 木の中心が 2 つあり, それらが隣接していないとすると, その場合には定理 9.1 (iv) により, 木の全ての辺は橋であり, 中心である点 1,2 は次数が 2 の点 v を介して結合しているはずである (図95 参照). 従って, 点 1,2 とこの v との接続辺を除去すると中心が 1 つとなってしまい, 中心が 2 つあ
1v2図 95: 木では全ての辺が橋である.
るという仮定に反する. よって, 木の中心が 2 つある場合には, それらは必ず隣接していると結論付けられる.

(4) 点が 7 つで, 中心が１つまたは 2 つのグラフの一例をそれぞれ図 96 に載せる.
26167133524475

図 96: 7 点からなる木で中心が 1 つのもの (左) と中心が 2 つのものの一例.

ここは 67 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

演習問題 6(1) 図 97 に示したグラフの全域木を全て描け.
abedc

図 97: ここで全域木を考えるグラフ.

(2) グラフ G の辺のある集合を C ∗ とする. どの全域林にも C ∗ と共通な辺があるならば, C ∗ にはカットセットが含まれることを例を挙げて示せ.

※ 連絡 : 次回 (5/30) は情報工学演習 II(B) としてグラフ理論の演習を行います. 今回のレポート締め切
りは 6/6 の講義開始時までとします.

ここは 68 ページ目