グラフ理論 #4
第4回講義 5月14日--- 道と閉路 --情報科学研究科 井上純一
http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/

演習問題3 (1)の解答例
隣接行列

12

歩道生成行列各成分を冪で展開すると自分自身に戻る場合には偶数次、他点に移動する場合には奇数次の冪のみが展開に現れ、その展開係数は全て1である

演習問題3 (2)の解答例
隣接行列

123

歩道生成行列４次まで展開すると4

(1,1)成分の確認

長さ2の歩道長さ3の歩道(1,2)成分の確認

単純グラフの補グラフ
単純グラフGの補グラフ (complement) :単純グラフGの点集合を持ち、2点が隣接するのは、Gにおけるそれらの2点が隣接していないとき、かつ、そのときに限るグラフ
uu

自分自身の補グラフと同型であるグラフ ⇒ 自己同型グラフ
yyvvxwxw例）☆ 完全グラフの補グラフは空グラフ☆ 完全二部グラフの補グラフは2つの完全グラフの和である

例題3.4の2.(1)問題となるグラフとその補グラフの和は完全グラフとなるべきである
問題のグラフの辺数は∴ n = 4k , 4k + 1

n(n − 1)m=4（辺数は整数でなくてはいけない）
k=1のとき, n=4L+2
M=6
次数１の点数 次数２の点数
L+M = 4
この解は( L, M ) = (2, 2)

破線と実線のグラフがそれぞれ自己補対例題3.4の2.(1) #2
k=1, n=4k+1=5の場合には

L + 2 M + 3 N = 10

次数３の点数L+M + N =5
その解は

( L, M , N ) = (1,3,1),(2,1, 2),(0,5,0)
対応する次数列は(3,2,2,2,1), (3,3,2,1,1), (2,2,2,2,2)
これは描けない例題3.4の2.(2)k=2, n = 4k=8 の自己補対グラフの例
1(1) ８個の点を時計回りに並べる
2(2) ８個の点のうち奇数番の点に関して完全グラフを作る

83(3) 奇数番目の点とその点の番号+1番目の点どうしを結ぶ(4) 偶数番目の点とその点+3番目の点を結ぶ

7

自己補対グラフの探し方

46
5

上のアルゴリズムで奇数番目と偶数版目の点の役割を交換したグラフ
が自己補対

歩道・小道・道・閉路
歩道 : vi (i = 1,.., m) ∈ G に対し、
G

v0 v1 , v1v2 ,..., vm −1vm を歩道という
終点始点（※重複する辺があってもよい）
始点をv
終点をzとする小道

小道 : 全ての辺 v0 v1 , v1v2 ,..., vm −1vm が異なる歩道
道:
閉路 :点v0 , v1 ,..., vm が全て異なる歩道
少なくとも1本辺を持つ閉じた道例題4.1 #1
連結単純グラフG : {v1 , v2 ,..., vn } , m本の辺, t 個の三角形(1)⎛ a11.....a1n ⎞⎜⎟A = ⎜ .... .... .... ⎟⎜ a .....a ⎟nn ⎠⎝ n1

第 ij 要素 b: =ij⎛ b11......b1n ⎞⎟と置くと、この2乗は 2 ⎜A = ⎜ .... .... .... ⎟ = B⎜ b ......b ⎟nn ⎠⎝ n1n∑a ak =1ikkj

点vi から点vkを経由してvjに至る
長さ2の歩道の数

経由点vkに関する全ての可能性について足しあげたものはvi とvj間の歩道の総数に等しい(2)nbii = ∑ aik aki

k =1 viからvkを経由してviに戻る

歩道数Viとvkを結ぶ辺の2倍n∑bi =1ii

はGの総辺数の2倍例題4.1 #2(3)

点viから点vkとｖｌを経由して⎛ c11.....c1n ⎞点vjへ至る辺の本数⎜⎟3A = ⎜ .... .... ... ⎟ = C n n⎜ c .....c ⎟ cij = ∑∑ aik akl alj
nn ⎠⎝ n1k =1 l =1

点viから点vjへ至る歩道の総数

対角要素 :
nncii = ∑∑ aik akl ali
k =1 l =1

従ってこのような閉路（三角形)の総数n∑ c = 6ti =1ii

点 i, k, l の並べ方の3!=6通りからくる

定理5・2 #1
グラフGはｎ個の点をもつ単純グラフでありｋ個の成分がある場合Gの辺数mは（証明)1n − k ≤ m ≤ (n − k )(n − k + 1) を満たす
2m ≥ n − k について辺数の下限に関して、であるから、グラフGはできるだけ少ない辺数を持つものとする（極端な場合として木を考える）
辺を1本削除する

Gから辺を1本削除すると

k → k + 1, n → n, m0 → m0 − 1

m0 − 1 ≥ n − (k + 1) m0 − 1本の辺に関して不等式の成立を仮定（帰納法の仮定。m0=0の場合は自明）

m0 ≥ n − k

m0 本の辺について成立⇒全ての辺数について成立

定理5・2 #2

グラフGの中の任意の2成分

m ≤ (n − k )(n − k + 1) / 2の成立について示す
辺数の上界を示すので、グラフGは辺数の最も多い完全グラフとして考える
Ci + C j の辺の総数

11N ij = ni (ni − 1) + n j (n j − 1)22

次の操作を行うni > n j

Ci ⇒ ni + 1 個の点をもつ完全グラフ

C j ⇒ n j − 1 個の点をもつ完全グラフ

ΔN ij = ni − n j + 1 > 0 だけ点の総数は増える
この操作を繰り返すとn-k+1個の点からなる1つの完全グラフとk-1個の孤立点が得られる

1m ≤ (n − k )(n − k + 1)
2が成立する例題4.2 (1)d (v, w)はvからwへの最短路の長さ
d (v, w) ≥ 2ならば , d (v, z ) + d ( z , w) = d (v, w)なる点zが存在する(証明のアウトライン)

点vと点w間の最短路C上の任意の点

図において

C1 は点vと点zを結ぶ最短路である仮定もし、これ以外に最短路C*1 があるとすれば経路C*1 + C 2 がvとwを結ぶ最短路となり仮定に反する

C2に関しても同様の議論ができる

考えるグラフは連結であるから、いつでもC上にzをとることができる

例題4.2 (2)ピータースン・グラフにおいて、任意の2点v, wに対しd (v, w) = 1 または d (v, w) = 2 である
ピータースン・グラフの対称性から

v = 1, v = 6をスタート点を選んだときの可能な経路の長さを調べればよい。実際に調べてみるとd (1, 2) = 1, d (1,3) = 2,..., d (1,10) = 2,d (6,1) = 1,...., d (6,10) = 2となり、満たす。

詳細は講義ノート非連結化集合とカットセット
非連結化集合 :要素数最小のカットセット

それを除去するとグラフが非連結となる辺の集合

非連結化集合の各要素

カットセット :そのどのような部分集合も非連結化集合ではない非連結化集合

辺連結度 :λ (G )

連結グラフの最小なカットセットの大きさ
例に挙げた右図ではλ (G ) = 2

この中のどれが抜けても非連結化集合にはならない分離集合とカット点分離集合 :それを除去するとグラフが非連結となる点の集合（※点を除去する際にはその接続辺も除去する）

カット点 :
1個の点からなる分離集合

連結度 :グラフの最小な分離集合の大きさ
図の例では

κ (G ) = 2

分離集合κ (G ) ≥ k のときグラフGはｋ連結であるとい分離集合の各要素

例題4.4 (タイセット行列）
タイセット行列a

B = (bij )⎧1 ( Liが枝jを含む)
bij = ⎨
⎩0 (それ以外)
右図の例では

1L1

b

閉路L1を構成する辺2⎛1 1 1 0 0 0 ⎞B=⎜⎟
1 1⎠
⎝ 0 0 0 1閉路L2を構成する辺

c4d3
L265e

例題4.4 #2（カットセット行列）
カットセット行列

C = (cij )C1⎧1 (Ciが枝jを含む)
cij = ⎨
⎩0 (それ以外)⎛1 1 0 0 0 0 ⎞
⎜
⎟
10
1000
⎜
⎟
⎜0 0 0 1 1 0⎟C=⎜⎟000011⎜⎟⎜0 1 1 0 0 0⎟⎜⎜⎟⎟
⎝0 0 0 1 0 1⎠

右図の例では

aC3
1C2

d2
43bc

56C5e

C6C4

例題4.4 (1)-(3)タイセット行列⎛1 1 0 1 0 ⎞⎜⎟B = ⎜ 0 1 1 0 1⎟
⎜1 0 1 1 1 ⎟⎝⎠aC5C1213dL1bL2

カットセット行列⎛1 1 1 0 0 ⎞⎜⎟10010⎜⎟
C = ⎜0 1 0 1 1⎟⎜⎟
⎜0 1 1 1 0⎟
⎜1 1 0 0 1 ⎟⎝⎠C24C45L3cC6C3

一般に次が成立

BC = 0 (mod 2)
T例題4.5の1
右図より、ネットワークが正常である確率はR(q ) = (1 − q ) + 3q (1 − q )3a2bc

ネットワークが正常である場合
aaa1R
c0.8

bba0.6

0.4

b0.2

c00.2

0.40.6q0.8

1bcbcbaa0cacbc

例題4.5の2 (1)辺eを含まない閉路として
L1,L2の和からeを削除してできる閉路L3を選べる

L1e

共通する辺L2L3

例題4.5の2 (2)辺 e, e1,e2が三角形をなしている場合にはカットセットとして{e,e1}, {e,e2} 以外に必ず {e1,e2} を選ぶことができる
G2
C1C3

e1

G1e2

G3eC2

例題4.6 (1)K2K3

K 2とK 3の結びK 2 + K 3

例題4.6 (2)A group
B group

この両者は同形である

C group

K2(K 2,2,2E K2 + K2 + K2A)

K2
B

= {u Au B | u A ∈ V ( A) ∩ u B ∈ V ( B)}∪ {u BuC | uB ∈ V ( B ) ∩ uC ∈ V (C )}∪ {uC u A | uC ∈ V (C ) ∩ u A ∈ V ( A)}K2C

演習問題4完全に証明できなくても、考察過程を全てレポートに書くこと