連結性

連結: グラフの各2点の間に道がある.

歩道: v_i(i= 1,· · ·, m)∈Gに対し, 辺列v₀v₁, v₁v₂,· · ·, v_m−1v_mを歩道 (walk)という.

⇒別の表現: v₀→v₁→v₂→ · · · →v_m (v₀ : 始点,v_m: 終点) 小道: 全ての辺v₀v₁,· · ·, v_m−1v_mが異なる歩道

道: 点v₀, v₁,· · ·, v_m が全て異なる歩道(※ v₀=v_mであっても良いとする) 閉路: 少なくとも1本辺を持つ閉じた道

v

w

y x

z

図4.66: このグラフにおいて,閉路はx→v→w→x

'

&

$

%  

例題 4.1

 (2003年度 レポート課題#3 問題1)

連結単純グラフGの点集合は{v₁, v₂,· · ·, v_n} であり, m本の辺およびt個の三角形があるとする. 以 下の(1)〜(3)に答えよ.

(1)Gの隣接行列をAとすると,行列A²のij要素はv_iとv_j間の長さ2の歩道の個数に等しいこと を示せ.

(2)行列A²の対角要素の総和は2mであることを示せ.

(3)行列A³の対角要素の総和は6tであることを示せ.

(解答例)

(1)これは前回の例題3.8の復習でもある. 連結グラフGに関するn×nの隣接行列を

A =

⎛

⎜⎝

a₁₁ · · · a_1n

· · · · a_n1 · · · a_nn

⎞

⎟⎠ (4.92)

と置くと隣接行列の自乗A²は

A²=

⎛

⎜⎝ _n

k=1a_1ka_k1 · · · _n

k=1a_1ka_kn

· · · · · · · · · _n

k=1a_nka_k1 · · · _n

k=1a_nka_kn

⎞

⎟⎠≡

⎛

⎜⎝

b₁₁ · · · b_1n

· · · · b_n1 · · · b_nn

⎞

⎟⎠≡B (4.93)

と書け,A²のij要素であるb_ijは

b_ij =

n k=1

a_ika_kj (4.94)

である. ところで,隣接行列の定義からa_ikは点v_iと点v_kを結ぶ辺の本数,a_kjは点v_kと点v_jを結ぶ 辺の本数であるから,積a_ika_kjは点v_iから点v_kを経由して点v_jに至る長さ2の歩道の数に相当する (図4.67参照). 経由点v_k(k= 1,· · ·, n)の選び方の可能性(i=k, j=k の場合には「ループ」がある

.. . v

v

v

i

k

j

図4.67: 点vkは点viから点vjへ至る経由点.

と考える)に関し,この積a_ika_kj を足し上げた

n k=1

a_ika_kj = b_ij (4.95)

はv_iからv_jへ至る長さ2の歩道の数である. すなわち,A²のij要素b_ijはv_iからv_jへ至る長さ2の 歩道の数に等しい.

(2) (1)の結果を考慮すると,行列B=A²の対角成分 b_ii =

n k=1

a_ika_ki (4.96)

は点v_i から点v_kを経由してv_iへ戻る長さ2の歩道の数であるから,これはv_iとv_kを結ぶ辺の数の 2倍になっている(図4.68参照). 従って,行列A² の対角和

n i=1

b_ii =

n i=1

n k=1

a_ika_ki (4.97)

は連結グラフGに含まれる辺の本数の2倍,すなわち2mである.

v

v

i

k

図 4.68: 中継点v_kを経て,v_iへ戻る経路.

(3)A³を計算すると

A³=

⎛

⎜⎝ _n

k=1

_n

l=1a_1ka_kla_l1 · · · _n

k=1

_n

l=1a_1ka_kla_ln

· · · · · · · · · _n

k=1

_n

l=1a_nka_kla_l1 · · · _n

k=1

_n

l=1a_nka_kla_ln

⎞

⎟⎠≡

⎛

⎜⎝

c₁₁ · · · c_1n

· · · · c_n1 · · · c_nn

⎞

⎟⎠=C (4.98)

であるから,A³のij成分は

c_ij =

n k=1

n l=1

a_ika_kla_lj (4.99)

と書ける.

ところで,隣接行列の定義からa_ikは点v_iと点v_k間の辺の本数,a_klは点v_kと点v_l間の辺の本数,a_lj は点v_lと点v_j間の辺の本数であるから,これらの積a_ika_kla_ljは点v_i から点v_k及び点v_lを経由して 点v_jへ至る歩道の数である. 従って,経由点{v_k, v_l}の可能性について足し合わせた

n k=1

n k=1

a_ika_kla_lj = c_ij (4.100)

つまり,行列A³のij要素は点v_iから点v_jへ至る長さ3の歩道の数に等しい(図4.69参照). また,

v v

v

i v

k

l

j

図4.69: 点v_iから経由点{vk, v_l}を経てv_jへと至る経路.

c_ii =

n k=1

n l=1

a_ika_kla_li (4.101)

は点v_iから点v_k及び点v_lを経由してv_iへ至る長さ3の閉路の数であるから. これは点v_i, v_k及び点 v_lを結ぶ三角形の数である. 従って, これを経由点{v_k, v_l}の可能性について足し上げた

n i=1

c_ii =

n i=1

n k=1

n l=1

a_ika_kla_li (4.102)

は連結グラフGに含まれる三角形の個数の6倍(i, k, lの並べ方3 ! = 6通りに縮退)に等しい(図4.70 参照). すなわち

v

v

v

i

k

l

図 4.70: 点v_iを出発し,点{vk, v_l}を経て点v_iへと戻る閉路は三角形を形成する.

n i=1

c_ii = 6t (4.103)

に等しい.

定理 5.2

グラフGはn個の点を持つ単純グラフであるとする. Gにはk個の成分があるとき, Gの辺の本 数mは次式を満たす.

n−k≤m≤1

2(n−k)(n−k+ 1) (4.104)

(証明)

まず, (4.104)における下界を表す不等式 : m≥n−k について示す. 空グラフm= 0のときは自明であ り,n=kより, 0≤0−0 = 0で成立する. 従って,以下ではこの場合を除外して考える. 方針としては,辺 数がm₀−1のときに不等式の成立を仮定し,m₀のときの成立を示すという数学的帰納法により証明する ことにしょう.

このために,単純グラフGから任意の辺を1本削除した場合,成分数,点数,辺数はどのように変化するの かを考察すると

成分数:k → k+ 1 点数:n → n 辺数:m₀ → m₀−1

となるから,上の矢印の右側のそれぞれの量(k+ 1, n, m₀−1)に関して不等式を作ると m₀−1 ≥ n−(k−1)

が成立する. 従って, この辺数m₀−1に関する不等式の成立を仮定し,これから辺数m₀についての不等 式の成立を導けばよいわけであるが,これは上不等式を書き直せば直ちに

m₀ ≥ n−k

が得られるので,帰納法により,全てのmに対して不等式: m≥n−kの成立が示された.

次に, (4.104)の上界を示す不等式: m≤(n−k)(n−k+ 1)/2についての成立を示す. 辺の数の上界を考 えるわけであるから,グラフGを成分数がkのグラフで,辺の数が一番多いものとすれば,このグラフGの 各成分は完全グラフであるとしてよい. そこで,この成分の中で任意の2成分C_i,C_jを選び, C_iにはn_i個, C_jにはn_j個の点があったとする(n_i≥n_j). つまり, C_i+ C_jの辺の総数Nij はそれぞれが完全グラフで あることを考慮すると(図4.71を参照).

Nij = 1

2n_i(n_i−1) +1

2n_j(n_j−1) (4.105)

Ci

Cj

nⁱ

n^j

ni +1

n^j-1

C

C

i

j

図4.71: 完全グラフCiに点を一つ足して完全グラフを作り,完全グラフCjから点を一つ引き,完全グラフを作る.

となる. さて,ここで次の操作を考える.

(操作)

C_i ⇒n_i+ 1個の点を持つ完全グラフ  C_j ⇒n_j−1個の点を持つ完全グラフ

この置き換えにより, C_i+ C_jの点数は不変であるが,辺数N_ij は N_ij = 1

2n_i(n_i+ 1) + 1

2(n_j−1)(n_j−2) (4.106)

のように変化する. 従って,この(操作)により, 辺の数は ΔN_ij = N_ij − N_ij

= 1

2n_i(n_i+ 1) + 1

2(n_j−1)(n_j−2)− 1

2n_i(n_i−1) +1

2n_j(n_j+ 1)

=n_i−n_j+ 1>(4.107)0 だけ増加する.

この議論を進めると,結局,成分数がkであるグラフで最も辺数が多いグラフGは点の数がn−(k−1) = n−k+ 1個の完全グラフとk−1個の孤立点(空グラフ)からなるグラフであると結論付けられるので,辺 数mの上限は不等式:

m ≤ 1

2(n−k)(n−k+ 1) (4.108)

を満たすことがわかる(証明終わり).

'

&

$

%  

例題 4.2

 (2003^{年度 情報工学演習}II(B) #2)

連結グラフにおいて,点vからwへの距離d(v, w)はvからwへの最短路の長さである. このとき, 以 下の問い(1)(2)に答えよ.

(1)d(v, w)≥2ならば

d(v, z) +d(z, w) = d(v, w) (4.109)

なる点zが存在することを示せ.

(2)ピータースン・グラフにおいて,任意の異なる2点vとwに対してd(v, w) = 1またはd(v, w) = 2 であることを示せ.

(解答例)

(1)図4.72のような状況を考える. 点vからwへの最短路をCとする. Cの全長はd(v, w)である. この

v

z w

C

C

1

2

C

C

1

2

*

*

図 4.72: v→z→wの経路C=C¹+C²はvからwへの最短路であり,その長さはd(v, w)で与えられる.

経路C上に任意の点zをとり,この点zを中継点として経路Cを2つの部分に分けて,部分路v→z をC¹,部分路z→wをC²とする.

この点zに対し, C¹はvとzを結ぶ全ての経路のうちで最短路である. なぜならば,もしvとzを結 ぶ別の経路の中でC¹よりも短いものが存在するとすれば, その経路C_∗¹とC²を合わせた新しい経路 C_∗¹+C²がvとwを結ぶ全ての経路の中で最短となり,仮定に反する. 従って,経路C¹が点vとzを 結ぶ全ての経路の中で最短であり, C¹の全長がd(v, z)である.

次に,zとwを結ぶ経路の中で最短のものであるが,これがC²であることは明らかである. なぜなら ば,この経路と別な経路C_∗²が存在するとすれば, C¹とC_∗²を足し合わせた経路C¹+C_∗²がvとwを 結ぶ全経路の中で最短となり,仮定に反する. 従って,C²がzとwを結ぶ全経路のうちで最短であり, その全長はd(z, w)である. 従って,考えるグラフは連結であるから,経路C上に中継点zをいつでも 任意にとることができ,この点zに対して

d(v, z) +d(z, w) = d(v, w) (4.110)

が成り立つ.

(2)図4.73のように,ピータースン・グラフの各点に番号を付ける. ピータースン・グラフの対称性から, 点1,6をスタート地点に選んだ場合の各他点への最短路を考えれば十分である(括弧内は長さdを与 える経路).

d(1,2) = 1 (1→2), d(1,3) = 2 (1→2→3), d(1,4) = 2 (1→5→4) d(1,5) = 1 (1→5), d(1,6) = 1 (1→6), d(1,7) = 2 (1→2→7),

d(1,8) = 2 (1→6→8), d(1,9) = 2 (1→6→9), d(1,10) = 2 (1→5→10)

1

2

3 4

5 6

7

8 9

10

図4.73: ピータースン・グラフ

d(6,1) = 1 (6→1), d(6,2) = 2 (6→1→2), d(6,3) = 2 (6→8→3) d(6,4) = 2 (6→9→4), d(6,5) = 2 (6→1→5), d(6,7) = 2 (6→9→7) d(6,8) = 1 (6→8), d(6,9) = 1 (6→9), d(6,10) = 2 (6→8→10)

以上より,ピータースン・グラフの任意の2点v, wに対してd(v, w) = 1またはd(v, w) = 2であるこ とが示せた.

ドキュメント内 GRAPH2007.dvi (ページ 63-69)