第3回 - Donald Home Page

講義の概略

グラフの次数とその性質
 次数：ある頂点と隣接する別の頂点の数
H26 グラフ理論
 グラフを特徴付けるパラメータ
 グラフの次数：次数の最大値

―第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：任意のグラフの奇点の個数は偶数．
※ 系とはある定理から直ちに導かれる性質
証明：グラフの奇点の集合を 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| (奇点の数)も偶数
定義（正則グラフ）：
すべての点の次数が等しいグラフを正則グラフ
という．正則グラフの次数が r であるとき，
r-正則グラフという．
K5 (完全グラフ)や K3,3 (完全2部グラフ)は
それぞれ5-正則, 3-正則グラフである．
K5
K3,3
5
6
※次数と正則グラフの関係
定理1.8：任意のグラフ G に対して，G を誘導部分
グラフとして含むΔ(G)-正則グラフ H が存在する．
定理：任意のグラフ G に対して，G を誘導部分
グラフとして含むΔ(G)-正則グラフ H が存在する．
証明：H の構成法を示す．G が正則ならば，
H = G とすればよい．そうでないならば，
G のコピーを2つ作り，それらを Gx,Gy とし，
d(v) <Δ(G) であるような Gx と Gy の対応する
頂点同士を辺で結ぶ．これをG1とする．
誘導部分グラフの例：
この場合 G は H の誘導部分グラフであるが,
HはΔ(G)-正則 (すなわち2-正則) グラフではない．
1
G は H の誘導部分グラフ
4
1
2
3
Δ(G)=3
G のコピー
2
3
G
H
7
8
2
証明（つづき）：G1 が正則ならば，G は G1 の誘導部分
グラフであるので，H=G1 とする．そうでないならばこの
操作を続けていくと, Δ(G)未満の次数が1ずつ増加する
ので,有限回で条件を満たす H = Gk が得られる．
G
Δ(G)-正則グラフ H の構成例
4
G2
2
G1
1
4
1
3
2
3
G
G1 = H
9
定理1.9：δ(G) ≥ 2 (最小次数が2以上) ならば
G には閉路が存在する．
証明：G の任意の歩道※下図参照を (v1,…,vk) とする．
このときある頂点が2回以上含まれていればは閉路
を含みこの定理が成り立つので， v1,…,vk は1度ずつ
含まれるとする．
10
証明(つづき)：
vk は端点ではないので，接続している点 vk+1 がある．
これが v1,…,vk のどれかと等しいなら閉路となり，
そうでないならばこの操作を続けること，頂点の個数は
有限なので，いつかは同じ点が2回現れるため，
結局 G は閉路を含まなければならない．
G
G
v1
vi ≠ vj (i ≠ j )
v2
v1
v2
vk
vk+1
vk+2
vk+m
=vk
vk
Gの歩道
11
いつかは以前現れた頂点が再び現れる
12
3
隣接行列の応用例：PageRank1) によるウェブ
1) Google
ページのランク付け
隣接行列とその応用
隣接行列：グラフを計算機上で表現可能にする
ための有効な概念．
v4
v1
e1
v2
e6
e5
e3
e2
v3
v1
v2
v3
v4
各ノードから出ている辺が，重要度を均等に
分配していると考える(確率遷移行列は隣接行列の正規化)
※単純グラフならば対角成分は常に0
1/2
C
リンクする側とされる側が興味を共有する構造
体をウェブコミュニティーという
Computer vendors
興味を共有する
グループ
 An
lim  B n
n  
C
 n
1 2   An
1 2   Bn

0   C n
 6/5
   3 / 5   ... 
 

 6/5
 






 1 
1
 1 / 2   1


 
3/2
1


 
14
HITSアルゴリズム2)
によるウェブコミュニティの発見
― ウェブコミュニティーの発見 ―
PC vendors
B
0
0
1
13
もうひとつの重要な応用：
Yahoo!
 An 1   1 2
B  0
 n 1  
 C  1 2
 n 1  
A
隣接行列
無向(多重)グラフ
ページAは重要度をAとCに等しく分配．．．
1/2
v1 v2 v3 v4
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 1

ハブとオーソリティーの概念
オーソリティー：（特定のトピックについての情報が豊富なページ）
ハブ（高いオーソリティーへのリンクが豊富なページ）
 相互補完的に計算される概念


IBM
高いハブ度
高いオーソリティー度
TOSHIBA
FUJITSU
wikipedia周辺のコミュニティ
http://ja.wikipedia.org/wiki/
興味の対象
典型的なウェブコミュニティー
15
2) Jon M. Kleinberg: Authoritative Sources in a Hyperlinked Environment.
16
J. ACM 46(5): 604-632 (1999). 2006 Rolf Nevanlinna Prize
4
隣接行列の表現
ハブとオーソリティーのランキング
初期値
グラフを計算機上でどのように実現するか
1
1
2
2
3
3
4

無向グラフ(多重辺を含む場合)の隣接行列A(G)
v1
1
1
この結果を用いて
ハブのランクを更新
1
3
2
3
2
2
1
2
4
3
4
3
v2
更新されたオーソリティー
v4
v3
G
0
1
A(G)=
0
0
1
1
1
0
0
1
0
1
0
0
1
0
この計算を繰り返す
17
定理1.10：グラフ G の頂点集合を V(G)＝｛v1,…,vp｝
とし，A(G) を G の隣接行列とする．行列A (n) (G) の
(i,j)成分 a (n)ij は，長さ n の vi-vj 歩道の総数に等しい．
v1
v2
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
1
1
2
0
0
1
0
1
v3からv2までの長さ2の歩道
の数はちょうど１つある 19
18
証明：帰納法で示す．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のときも正しい．
したがって定理が成立する．
20
5
系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
y
頂点xから長さ3でxに返る場合の数は？
(この数がA3(G)の対角成分に並ぶ)
21
グラフの他の表現(計算機でどのよう
vbxzay
に実現するか)
v000010

隣接行列の利点
 単純な構造（実装しやすい）
 辺の追加・削除が最も高速
隣接リストによる表現
b101001
x100000
z000010
a000100
y100000

配列とリストの先頭へのポインタで表現
 配列のi番目が、ノードiで定義されている辺を順
に指している
 利点：サイズが辺数とほぼ同じ（効率的）&追加・
削除が容易
 欠点：二つのノードに辺があるかを
v
a
調べるのに時間がかかることがある
b
v
x
 二つのノードに辺があるかが直ちにわかる

22
欠点
 無駄が多い（ほとんどの値はゼロ）
 大きなグラフを行列で表すのは困難
23
b から y へ辺があることを
知るためには、リストの最後まで
みなければわからない
x
z
a
y
v
a
z
v
y
24
6
辺リストによる表現

隣接行列のもう一つの応用
配列に辺を並べて表現


 ノードを整数で表し、整数の組み(i,j)を配列に格
納する
 利点：圧縮を考えなければ最も小さい表現&追加
が容易
 欠点：辺のチェックをするために，常にすべての
値をみなければならない(最も効率が悪い)&削除
が困難


5
6
3
G
3


5
1
4
2
6
2
G
010010
001000
010000
000001
000100
000010
Gの隣接行列A(G)
26
隣接行列による推移閉包の表現
有向グラフGでxからyへ到達可能なら辺(x,y)を加えたグラフを
Gの推移閉包という
推移閉包が求まれば, 任意のx,yに対してその到達可能性を高
速に計算できる
1
4
25
有向グラフの推移閉包

5
1
v a b v b x b y x v z a a z y v
一組で辺を表す
有向グラフG(辺に向きのあるグラフ)を考える
辺は向きがある方向にしかたどることが出来ない
頂点xからyへ道があるとき, xからyへ到達可能であるという
6
3
5
1
4
2
Gの推移閉包を表すグラフの隣接行列をGの推移閉
包行列といい，A*(G)と表す
xからyへ到達可能 ⇔ A*(G)[x][y]=1
4
6
2
Gの推移閉包
27
3
Gの推移閉包
111111
011000
011000
000111
000111
000111
Gの推移閉包行列
A*(G)
28
7
推移閉包行列の計算


初期行列からの計算
初期行列：隣接行列の対角成分を1に変更する(自分自身に
は到達できる)
推移閉包行列：初期行列からどう計算すればよいか？
010010
001000
010000
000001
000100
000010
110010
011000
011000
000101
000110
000011
111111
011000
011000
000111
000111
000111
Gの隣接行列
初期行列
Gの推移閉包


以下の基本アイディアを各A(G)[x][y]で行う
A(G)[x][y]=1 ⇒ xからyへ到達可能であることを次々
に拡張していく
z
A(G)[x][z]=0
x
A(G)[x][y]=1
29
z
A(G)[x][z]=1
x
A(G)[y][z]=1
y
A(G)[x][y]=1
A(G)[y][z]=1
y
30
推移閉包を計算するアルゴリズム
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)
31
8

Download Report