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

目次
11 有向グラフ
127
11.1 有向グラフの定義・概念とその性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
11.2 オイラー有向グラフとトーナメント . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

演習問題 10 の解答例
例えば, 三角形を G1 とし, 2 個の点からなる木を G2 とする. このとき, 3 色が使うことのできる色数とす
れば, PG1 (3) = PG2 (3) = 6 である. 具体的に三色を R,B,G として彩色を図示すると図 170 のようになる.
これから明らかに, この G1 , G2 をグラフ G の 2 つの成分としたとき, この 2 つの成分は非連結であるから,
R

B

GR

B

B

R

RGGR

BGR

GB
B

R

GB

GR
GG

B

B

R
GR

B

図 170: G1 , G2 の 3 色での彩色の仕方. それぞれ 6 通りある.

G1 の彩色の仕方は G2 の彩色の仕方に影響を与えない. 従って, 非連結グラフ G を 3 色で色分けする場合,
126

グラフ理論 2005

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

出来上がるグラフの個数は PG1 (3) × PG2 (3) = 36 通りある. この考察を押し進めてグラフの成分数が増えた場合を考えても, 個々の彩色多項式の積で非連結グラフの彩色の仕方の数が決まるのは明らかなので, 題意が言えることになる.

11有向グラフ

今まで扱ってきたグラフは各辺に向きは無く, 例えば, オイラー小道などを考える際には, 辺のどちら向きに進んで道を作っても構わなかった. これに対し, この節からは各辺がそれぞれ向きを持っている「有向グラフ」について, その性質を調べて行くことにする.

11.1

有向グラフの定義・概念とその性質

弧集合 (arc family) A(D) : 点集合 V (D) の元の順序対からなる有限族.
有向グラフ (digraph) D : V (D) と A(D) からなるグラフ (図 171 参照).

Duzvw

図 171: 有向グラフ D の一例. V (D) = {u, v, w, z}, A(D) = {uv, vv, vw, vw, wv, wu, zw}.

D の基礎グラフ (underlying graph) : 有向グラフ D の矢印を取り除いたグラフ (図 171 参照).

uzvw

図 172: 図 171 の有向グラフに対する基礎グラフ.
単純有向グラフ (simple digraph) : D の弧が全て異なり, ループが無いグラフ.

(注) : 単純有向グラフの基礎グラフは必ずしも単純グラフでは無い (図 173 参照).
有向グラフの同形 : 基本グラフの間に同形写像があり, 各点の順序を保存する写像になっているとき.
例えば, 図 174 のグラフ A と B は同形ではない. wz の向きが異なるからである.
有向グラフ D の隣接行列 A = (aij ) : 要素 aij が vi から vj への「弧」の本数を表す, サイズ n のグラフに対して n × n の行列.

ここは 127 ページ目

グラフ理論 2005

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

uuzvzwvw

図 173: 図 171 の単純有向グラフの基礎グラフは必ずしも単純グラフではない.
AuuBzzvwvw

図 174: これら有向グラフ A と B は同形ではない. 辺 wz の向きが異なるからである.

(注) : 無向グラフの場合と異なり, 行列 A は非対称であることに注意されたい.
図 175 の有向グラフ D の隣接行列 A は

A =00 0
 1


1 01 21 00 0 

00 10で与えられる.
1423

図 175: その隣接行列が A で与えられる有向グラフ D.
強連結 (strongly connected) : 任意の 2 点, v, w の間に v から w への道がある.
向き付け可能 (orientable) : グラフ G の全ての辺を方向付けて強連結有向グラフが得られるとき (例として図 176 参照).

定理 22.1
連結グラフ G が向き付け可能であるための必要十分条件, グラフ G の各辺が少なくとも 1 つの閉路に含まれていることである.

(証明)
必要性は明らかなので十分性を示す.
ここは 128 ページ目

グラフ理論 2005

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

図 176: 向き付け可能なグラフの一例.
まず, グラフ G の全てが閉路が含まれている場合には証明は終わる. 従って, 以下ではこれ以外の場合を考える.
さて, 閉路 C には含まれないが, C の各辺に隣接している辺 e を選ぶ (図 177 参照). 「グラフ G の各辺C’eC



図 177: 閉路 C と C .


が少なくとも 1 つの閉路に含まれている」のであるから, e はある閉路 C に含まれている. C の辺を C にも含まれている C の辺の向きは変えないで向き付ける. この操作でできる有向グラフは強連結である.
従って, この操作を続けて, 各ステップで少なくとも 1 つの辺を向き付ける. 各ステップで有向グラフは強連結なので, グラフ全体を向き付けた後にできるグラフは強連結である. (証明終わり).
有向グラフの応用問題として, 次の例題を見ておこう.

✎
例題 30
図 178 のネットワークで点 A から点 G への最長路を見つけよ.
✍BE40830A✌

635D19G111250C102320F

図 178: ここでの例題のネットワーク.

(解答例)
点 A からの各点 V への最長路の長さを示す数値 l(V) 計算すると

A :

0

B :

l(A) + 30 = 30

C :l(A) + 50 = 50D

max{l(B) + 6, l(C) + 12} = max{36, 62} = 62:

ここは 129 ページ目

グラフ理論 2005

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

F :max{l(D) + 23, l(C) + 10} = max{85, 60} = 85

E :max{l(B) + 40, l(B) + 35, l(F) + 11} = max{70, 97, 96} = 97

G :max{l(E) + 8, l(F) + 20} = max{105, 105} = 105となるから, 最長路の長さは 105 であり, 最長路を図 179 に載せる.
BEB

E8A

D50

G A
2312D

C2050

G3512FCF

図 179: 最長路を与える 2 通りの経路. どちらも最長路の長さは 105 である.

#

✥

例題 31
有向グラフ D の逆 D̃ は D の辺の向きを反転して得られる. 以下の問題に答えよ.

(1) その逆と同形であるような有向グラフの一例を描け.
(2) D と D̃ の隣接行列の間にはどんな関係があるか, 答えよ.
✧✦

(解答例)
(1) 互いに同形であるような有向グラフ D 及び, その逆 D̃ を図 180 に描く.
-DDABAB図 180: 互いに同形であるような有向グラフ D 及び, その逆 D̃ の一例.

(2) 図 181 に載せた基礎グラフ G に対して有向グラフ D 及び, その逆 D̃ を作り, それぞれの隣接行列
AG , AD , AD̃ を書き下してみると-DD

51425134235G1243

図 181: 例として考える基礎グラフ G, 有向グラフ D 及び, その逆 D̃.

ここは 130 ページ目

グラフ理論 2005

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

AG

1 10 0001 00 1000 00 0 1
AD =  0 101 20 1011 00 1001 00 1 2
= 
 0

 100



0 

0 


1 0(185)

1 10 1010 00 0001 00 1
 1AD̃ = 
 0

 10

0 

0 


1 000



0 

0 


0 0(186)となる. AD + AD̃ を作ってみると

AD + AD̃

2 20 101

1 00 1001 00 1


 2

 0
 10=0



0 

0 

1 0(187)が得られるが, これは一行一列成分 ([AD + AD̃ ]11 ) だけが異なる以外は基礎グラフの隣接行列と一致する. この食い違いが生じた成分は基礎グラフの「ループ」に相当する. 従って, ループが無い基礎グ
ラフに関しては関係式 :AG= AD + AD̃

(188)が成立することがわかる. ループを含むグラフに関しても, 非対角成分に限れば上関係式が成り立つ.

ここでは図 181 に載せた特定のグラフに関して議論したが, これが一般のグラフに関しても成り立つのは明らかである. グラフの逆は辺の向きを逆転してできるわけであるから, 一方のグラフで弧 vw が存在するならば，その逆のグラフでは vw は存在しない. 従って, ループが無い場合には関係式 (188) の非対角成分に関して [AG ]vw = [AD + AD̃ ]vw が成り立つ. ループがある場合には各隣接行列に対して[AD ]vv = [AD̃ ]vv が成り立つわけであるから，関係式 (188) の対角成分に関して 2[AG ]vv = [AD +AD̃ ]vv
が成り立つ. ループが無い場合には隣接行列の対角成分はゼロであるから, 関係式 (188) を成分で書けば全ての場合に関して, 異なる任意の 2 点 v, w に対し[AG ]vw=[AD + AD̃ ]vw(189)

2[AG ]vv=[AD + AD̃ ]vv(190)

が成り立つ.

11.2

オイラー有向グラフとトーナメント

連結有向グラフ D の全ての弧を含む閉じた小道が存在する場合, その有向連結グラフ D をオイラーであると言う. 図 182 に載せた例は, オイラーではないが, その基礎グラフはオイラーである場合である.
ここは 131 ページ目

グラフ理論 2005

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

uvw

図 182: オイラー有向グラフではないが, その基礎グラフはオイラーであるグラフの一例.

出次数 (out-degree) outdeg(v) : vw の形をした有向グラフ D の弧数.
入次数 (in-degree) indeg(v) : wv の形をした有向グラフ D の弧数.
握手有向補題
有向グラフ D の全点についての入次数の合計と出次数の合計は等しい.

定理 23.1
連結有向グラフ D がオイラーであるための必要十分条件は, D の各点で outdeg(v) = indeg(v) が成立することである.
ハミルトン有向グラフ (Hamiltonian digraph) : 全ての点を含む閉路がある有向グラフ.
半ハミルトン有向グラフ (semi-Hamiltonian digraph) : 全ての点を通る道があるグラフ.

定理 23.2

D は強連結有向グラフであり, 点が n 個あるとする. 各点 v に対し, outdeg(v) ≥ n/2, かつ,indeg(v) ≥ n/2 ならば, D はハミルトン有向グラフである.

トーナメント (tournament) : 任意の 2 点がちょうど１本の弧で結ばれている有向グラフ (図 183 参照).
vzwyx

図 183: トーナメントの一例.

ここは 132 ページ目グラフ理論 2005担当 : 大学院情報科学研究科 井上 純一

定理 23.3(i) ハミルトンでないトーナメントは全て半ハミルトンである.
(ii) 強連結なトーナメントは全てハミルトンである.

(証明)
(i) 点 n 個のトーナメントは全て半ハミルトンであると仮定する. T には点が n 個あるので, 半ハミルトン道がある (図 184 参照).

TT’v i-1v3viv2vnv1v



図 184: T には半ハミルトン道がある.

(1) vv1 が T の弧ならば, v → v1 → v2 → · · · → vn が所望の道である.
(2) vv1 が T の弧ではなく, v1 v が T の弧であれば, 図 185 のように点 vi を選べばよい.
v i-1v4viv3v2v i+1v1vnv

図 185: vv1 が T の弧ではなく, v1 v が T の弧であれば, 図のように点 vi を選べばよい.

(3) vvi の形をした弧が T にないのであれば, v1 → v2 → · · · → vn → v が所望の道である. (証明終わり).

最後にトーナメント (「トーナメントが推移的である」という概念) に関する例題を一つ見ておこう.

✬✩

例題 32
トーナメントが推移的であるというのは, 弧 uv と vw があれば必ず弧 uw があることである. 以下の問いに答えよ.

(1) 推移的トーナメントの一例を描け.
(2) 推移的トーナメントにおいては全てのチームに順位を付けられることを示せ. ただし, どのチームもそれより下位のチーム全てを負かしていなければならないものとする.
(3) 点が 2 個以上ある推移的トーナメントは強連結になり得ないことを示せ.
✫✪

ここは 133 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一(解答例)(1) 推移的トーナメントグラフの一例を図 186 に載せる.
wvu

図 186: 推移的トーナメントグラフの一例.

(2) 図 186 に示したグラフにおいて, 点 k = u, v, w 出次数 : outdeg(k) 及び 入次数 : indeg(k) と順位の関係を書くと1 位 (u) : outdeg(u) = 2, indeg(u) = 0
2 位 (v): outdeg(v) = 1, indeg(v) = 1

3 位 (w): outdeg(w) = 0, indeg(w) = 2となる. 従って, outdeg の多い順 (あるいは indeg の少ない順) に 1 位から 3 位への順位が付けられる.
また, 推移的トーナメントの定義から outdeg あるいは indeg の数が等しい点が現れることはあり得ないから, 全てのチームに順位をつけることができる.

(3) 点が 2 個以上ある推移的トーナメントのグラフならば, 必ず outdeg(k) = 0 となるような点 k が存在するから, 強連結にはなり得ない.

演習問題 11
以下の問いに答えよ.

(1) ハミルトン・グラフは全て向き付け可能であることを示せ.
(2) Kn (n ≥ 3), および, Kr,s (r, s ≥ 2) は向き付け可能であることを, 個々のグラフの向き付けを具体的に見つけることにより示せ.
(3) ピーターソン・グラフの向き付けを見つけよ.

ここは 134 ページ目