H28 グラフ理論 - Donald Home Page

講義の概略

グラフの次数とその性質
 次数：ある頂点と隣接する別の頂点の数
H28 グラフ理論
 グラフを特徴付けるパラメータ
 グラフの次数：次数の最大値

―第3回―
グラフの次数と隣接行列
グラフを計算機上で表現するための技法
 隣接行列とその表現法
 推移閉包
 到達可能性
1
1.3: グラフの次数と隣接行列
定理1.5：グラフ G に対して，
が成り立つ．
定義（グラフの次数）
グラフ G の点 v∈V(G) に隣接する辺の数 d(v) を，
v の次数という．d(v) = 0 のとき v を孤立点，
d(v) = 1 のとき端点という．Gの最大次数，最小次数を
それぞれ Δ(G)，δ(G) で表す．
次数が偶数の点を偶点，奇数の点を奇点という．
奇点
定理の直感的意味：次数の総和は
辺数の２倍になっている．
ﾚ
d(u)
ﾚ
辺をちょうど2回ずつ
数えている
d(v)
証明：任意の頂点 u,v に対して，(u,v) が G の辺
であれば，d(u) と d(v) が1度ずつ数えられている
ので，左辺の総和は辺のちょうど2倍に等しい．
端点
Δ(G)＝4
δ(G)=1
2
偶点
3
4
1
系1.6：任意のグラフの奇点の個数は偶数．
定理1.9：δ(G) ≥ 2 (最小次数が2以上) ならば
G には閉路が存在する．
※ 系とはある定理から直ちに導かれる性質
証明：G の任意の歩道※下図参照を (v1,…,vk) とする．
このときある頂点が2回以上含まれていればは閉路
を含みこの定理が成り立つので， v1,…,vk は1度ずつ
含まれるとする．
証明：グラフの奇点の集合を Vo とし，
偶点の集合を Ve とすると，定理1.3より，
Σ v ∈V(G) d(v)
= Σ v∈Vo d(v) + Σ v∈Ve d(v)
= 2|E(G)| となる．
中段第2項が偶数なので，|Vo| は偶数である．
※補足： Σv∈ Vo d(v) + 偶数 = 偶数なので
Σv∈ Vo d(v) は偶数でなければならず
|Vo| (奇点の数)も偶数
v1
6
隣接行列とその応用
隣接行列：グラフを計算機上で表現可能にする
ための有効な概念
vk+1
vk+2
=vk
vk+m
v4
v1
e1
vk
vk
5
G
v2
v2
Gの歩道
証明(つづき)：
vk は端点ではないので，接続している点 vk+1 がある．
これが v1,…,vk のどれかと等しいなら閉路となり，
そうでないならばこの操作を続けること，頂点の個数は
有限なので，いつかは同じ点が2回現れるため，
結局 G は閉路を含まなければならない．
v1
vi ≠ vj (i ≠ j )
G
v2
e6
e5
e3
e2
v3
無向(多重)グラフ
いつかは以前現れた頂点が再び現れる
7
v1
v2
v3
v4
v1 v2 v3 v4
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 1
隣接行列
※単純グラフならば対角成分は常に0
8
2
隣接行列の応用例：PageRank1) によるウェブ
1) Google
ページのランク付け
各ノードから出ている辺が，重要度を均等に
分配していると考える(確率遷移行列は隣接行列の正規化)
 An 1   1 2
B  0
 n 1  
 C  1 2
 n 1  
A
1/2
B
 An
lim  B n
n  
C
 n
0
0
1
1 2   An
1 2   Bn

0   C n

 6/5
   3 / 5   ... 
 

 6/5
 






v4
v3
G
0
1
A(G)=
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
A2(G)=
1
0
1
3
1
1
v2
v4
 1 
1
 1 / 2   1


 
3/2
1


 
v3
G
0
1
A(G)=
0
0
1
1
1
0
0
1
0
1
0
0
1
0
9
定理1.10：グラフ G の頂点集合を V(G)＝｛v1,…,vp｝
とし，A(G) を G の隣接行列とする．行列A (n) (G) の
(i,j)成分 a (n)ij は，長さ n の vi-vj 歩道の総数に等しい．
v2
無向グラフ(多重辺を含む場合)の隣接行列A(G)
v1
このベクトルx=(An,Bn,Cn)の極限値は, M をこの確率遷移行列としたときの
x = Mx を満たす固有値1に属する固有ベクトルxに等しい
v1
グラフを計算機上でどのように実現するか
ページAは重要度をAとCに等しく分配．．．
1/2
C
隣接行列の表現
1
1
2
0
0
1
0
1
v3からv2までの長さ2の歩道
の数はちょうど１つある 11
10
証明：帰納法で示す．n =1 のときはあきらか．
A(G)n = (aijn) に対して，(i,j) 成分aijnが
長さ n の vi-vj 歩道の本数であると仮定する．
A(G)n+1 = A(G)n・A(G) より， A(G)n+1 の (i,j) 成分
aijn+1 は，
... (1.2) となる．
一方，長さ n+1 の歩道は，長さ n の vi-vk 歩道に
辺 (vk,vj) を加えることにより得られる．
よって帰納法の仮定と(1.2)式よりn+1のときも正しい．
したがって定理が成立する．
12
3
系1.11 (3)の補足
系1.11: 定理1.7よりつぎが成り立つ．
(1)グラフ G がループを持たないとき，A(G)2
の成分 a(2)ij は，長さ2の vi-vj 道(i ≠ j)の本数
6 7 3 1
A3(G) = 5 12 1 4 の対角成分は何を意味するか？
0 1 0 6
8 6 3 6
(2) G が単純グラフのとき， a(2)ii=degG vi
(3) G がループを持たないとき，
G の３角形の個数
は
x
z
※ ただし，tr(A)＝a11＋・・・＋ann
頂点xから長さ3でxに返る場合の数は？
(この数がA3(G)の対角成分に並ぶ)
y
13
グラフの他の表現(計算機でどのよう
vbxzay
に実現するか)
v000010

隣接行列の利点
 単純な構造（実装しやすい）
 辺の追加・削除が最も高速
隣接行列の素朴な実装（C言語）
b101001
x100000
z000010
a000100
y100000


 二つのノードに辺があるかが直ちにわかる

14
欠点
n×m行列を1本の配列Aに格納する
[i,j]成分にアクセスするには,A[i*m+j]番目にアクセスすれば
よい
[0,0]
[0,1]
[0,2]
[1,0]
[1,1]
[1,2]
[2,0]
[2,1]
[2,2]
0
1
2
i*mが各セクションの先頭を指す
 無駄が多い（ほとんどの値はゼロ）
 大きなグラフを行列で表すのは困難
15
3
4
5
6
7
8
16
4
2次元配列の実装



2値行列
長さnのポインタ配列Aを定義する
長さmの配列をn個作り、ポインタがそれぞれの先頭を指す
ようにする
[i,j]にアクセスするにはA[i][j]にアクセスする




2値行列：1-bit (0 or 1)の値しか持たない行列
グラフの隣接行列は2値行列で表現可能
素朴な表現ではA[i,j]は一つ当たりint型32-bit必要
この表現を圧縮してA[i,j]を1-bitで表す
m
[0]
[1]
n
[0]
[1]
[2]
[3]
[4]
[0]
[1]
[2]
[3]
[4]
[0]
[1]
[2]
[3]
[4]
[0]
[1]
[2]
[3]
[4]
[2]
[3]
int *MATRIX ( int n, int m ){
int i, **A;
A = malloc ( sizeof(int *)*n );
for ( i=0 ; i<n ; i++ )
A[i] = malloc (sizeof(int)*m);
return A;
}
00000001
00000000
00000001
1
0
1
00000000
00000001
00000000
0
1
0
00000001
00000001
00000000
1
1
0
例えばint型が8-bitの場合
1要素当たり8-bit使用する
本当はこのように表現したいが
int型のままで読み書きをしたい。
どうすればよいか？
17
18
int型(例えば16-bit)による2値行列
int型2値行列の操作





アイディア：普通のint型行列を作って、ビット列を16-bit毎に区切って読む
[i,j]にアクセスするには、i行目のj/16（切り捨て）個目の整数のj%16（余り
）個目にアクセスすればよい
以下のデータの[i,18]にアクセスする場合、まずj=18に対してj/16（切り捨
て） = 1を計算して、直近のint型整数の開始位置を探す。
さらにそこからj%16 = 2個目のビットにアクセスする。
j/16（切り捨て） = 1
が表すint型整数
[0]
…
[i]
0
1
0101011010101010 0111011011101011
BITMASKx[] =
[0111111111111111, 1011111111111111, 1101111111111111, …]
アクセス：A[i][j/16] & BITMASK[j%16] で 0111011011101011 と 0010000000000000
のANDを取れば目的のbitを取り出せる
 1に書き換える：A[i][j/16] = A[i][j/16] | BITMASK[j%16] （j番目以外は変わらない）
 0に書き換える： A[i][j/16] = A[i][j/16] & BITMASKx[j%16] （j番目以外は変わらない）

[i]
19
ビット操作のためのマスク配列を2種類用意しておく
BITMASK[] =
[1000000000000000, 0100000000000000, 0010000000000000, …]
…
0001011000101010
j%16（余り） = 2
が表す位置

[0]
2
実際に値にアクセスしたり、値を書き換えたりするにはどうするか
BITMASKx[2] = 1101111111111111
0101011010101010 0111011011101011
0001011000101010
j=18が表す位置
20
5
隣接リストによる表現
接続行列


配列とリストの先頭へのポインタで表現

 配列のi番目が、ノードiで定義されている辺を順に指して

いる
 利点：サイズが辺数とほぼ同じ（効率的）&追加・削除が
容易
 欠点：二つのノードに辺があるかを調べるのに時間がか
かることがある
v
a
b から y へ辺があることを
知るためには、リストの最後まで
みなければわからない
b
x
z
a
y
v
v
a
z
v
5
x
y


1
4
6
2
3
G
2
0
1
3
4
4
2
3
ノードに接続する
辺のリスト
辺に接続する
ノードのリスト
0: 1,3,5
1: 0,2,4
2: 1
3: 0,4
4: 1,5
5: 0,4
0: 0,1,2
1: 0,3,4
2: 3
3: 2,6
4: 4,5
5: 1,5
0: 0,1
1: 0,5
2: 0,3
3: 1,2
4: 1,4
5: 5,4
6: 3,4
接続行列
22
有向グラフの推移閉包


010010
001000
010000
000001
000100
000010
Gの隣接行列A(G)
0
隣接行列の
リスト表現
（ノード同士の接続関係）
21
有向グラフG(辺に向きのあるグラフ)を考える
辺は向きがある方向にしかたどることが出来ない
頂点xからyへ道があるとき, xからyへ到達可能であるという
5
1
6
隣接行列のもう一つの応用

5
隣接行列は(i,j) = 1 ならばiとjに辺があることがわかるだけで、グラフの
探索には向かない
例えばiにと隣接している頂点に効率よくアクセスしたい
このようなグラフの表現に、接続行列がある
有向グラフGでxからyへ到達可能なら辺(x,y)を加えたグラフを
Gの推移閉包という
推移閉包が求まれば, 任意のx,yに対してその到達可能性を高
速に計算できる
5
1
4
6
2
23
3
G
5
1
4
6
2
3
Gの推移閉包
24
6
隣接行列による推移閉包の表現


推移閉包行列の計算
Gの推移閉包を表すグラフの隣接行列をGの推移閉
包行列といい，A*(G)と表す
xからyへ到達可能 ⇔ A*(G)[x][y]=1
111111
011000
011000
000111
000111
000111
5
1
4
6
2
3
Gの推移閉包
Gの推移閉包行列
A*(G)

z
x
A(G)[x][y]=1
z
A(G)[x][z]=1
x
A(G)[y][z]=1
y
010010
001000
010000
000001
000100
000010
110010
011000
011000
000101
000110
000011
111111
011000
011000
000111
000111
000111
Gの隣接行列
初期行列
Gの推移閉包
26
推移閉包を計算するアルゴリズム
以下の基本アイディアを各A(G)[x][y]で行う
A(G)[x][y]=1 ⇒ xからyへ到達可能であることを次々
に拡張していく
A(G)[x][z]=0

初期行列：隣接行列の対角成分を1に変更する(自分自身に
は到達できる)
推移閉包行列：初期行列からどう計算すればよいか？
25
初期行列からの計算


A(G)[x][y]=1
A(G)[y][z]=1
y
27
Warshallのアルゴリズム
入力Gの隣接行列 A(G)[n][n]
出力Gの推移閉包行列 A*(G)
for y=1,...,n
for x=1,...,n
if A(G)[x][y] = = 1
for z=1,...,n
if A(G)[y][z] = = 1, then A(G)[x][z] = 1
return A*(G) =A(G)
28
7

Download Report