地理情報科学教育用スライド ©久保田李光一 第4章 空間解析 2

第4章 空間解析
2.ネットワーク分析
(3) ネットワーク構造分析
久保田光一
[email protected]
地理情報科学教育用スライド ©久保田李光一
ネットワーク構造分析の道具
• グラフ・ネットワークの頂点の探索方法
– 深さ優先探索,DFS,スタックLIFO
– 幅優先探索,BFS,キューFIFO
• グラフ・ネットワークの接続構造
– 木,DAG
– 直径,連結性,連結成分
– 近接度,近接性
地理情報科学教育用スライド ©久保田李光一
グラフの探索の基本
• グラフ中の頂点を一つ指定し,その頂点から
辿れる頂点を適当な順番に辿る方法のひと
つ
• 深さ優先探索,あるいは,縦型探索
– Depth First Search (DFS)
• 幅優先探索,あるいは,横型探索
– Breadth First Search (BFS)
• 混合タイプ,反復深化(iterative deepening)
地理情報科学教育用スライド ©久保田李光一
深さ優先探索(DFS)
探索開始頂点
1
2
3
4
番号は探索順序を表す
8
6
5
9
7
地理情報科学教育用スライド ©久保田李光一
10
深さ優先探索(DFS)
探索開始頂点
1
2
3
4
番号は探索順序を表す
8
6
5
9
7
地理情報科学教育用スライド ©久保田李光一
10
深さ優先探索(DFS)
• 各頂点 u に探索済みかどうかを表す真偽値変数
u.flag を用意し,最初はそれを false にする.
• 探索開始頂点を u をスタック(LIFO)にプッシュ.
while stack.empty() ≠ true do
v = stack.pop()
v.flag = true
/* 頂点 v に関する処理 */
for all u such that 枝(v,u)が存在
if u.flag ≠ true do stack.push(u)
地理情報科学教育用スライド ©久保田李光一
スタック(FILO, or, LIFO)
• FILO: First In Last Out 先に入れたものが後に
出てくる抽象構造
• 二つの操作が可能
– stack.push(x)
– stack.pop()
: スタックに x を入れる
: スタックから取り出す
– 山積みするようにしてものを出し入れする方法
3
2
1
stack
地理情報科学教育用スライド ©久保田李光一
1
2
3
幅優先探索(BFS)
探索開始頂点
1
2
4
7
番号は探索順序を表す
3
5
8
6
9
地理情報科学教育用スライド ©久保田李光一
10
幅優先探索(BFS)
探索開始頂点
1
2
4
7
番号は探索順序を表す
3
5
8
6
9
地理情報科学教育用スライド ©久保田李光一
10
幅優先探索
• 各頂点 u に探索済みかどうかを表す真偽値変数
u.flag を用意し,最初はそれを false にする.
• 探索開始頂点を u をキュー(FIFO)にプッシュ.
while queue.empty() ≠ true do
v = queue.pop()
v.flag = true
/* 頂点 v に関する処理 */
for all u such that 枝(v,u)が存在
if u.flag ≠ true do queue.push(u)
地理情報科学教育用スライド ©久保田李光一
キュー(FIFO)
• FIFO: First In First Out 先に入れたものが先
に出てくる抽象構造
• 二つの操作が可能
– queue.push(x)
– queue.pop()
: キューに x を入れる
: キューから取り出す
– パイプにものを入れて,押し出す方法
3
2
1
queue
地理情報科学教育用スライド ©久保田李光一
3
2
1
グラフの構造(木,DAG)
• 木(き),Tree
– グラフの n 個の頂点を繋げるn-1本の枝からなる
グラフ
• DAG (Directed Acyclic Graph) 無閉路有向グラフ
– 有向グラフであって,閉路が無いもの
地理情報科学教育用スライド ©久保田李光一
グラフの構造(道,有向道)
• 道(無向グラフ,有向グラフ)
– 頂点 v0 (始点)から,枝を辿って頂点 vq (終点)に至る頂点と枝の系列.
– q+1個の頂点 v0, v1, …, vq と q 個の枝 e1, e2, …, eq の系列として (v0, e1,
v1, e2, v2, …, eq, vq) と表すとき,ek={vk-1, vk} ,ek=(vk-1,vk), または,ek={vk,
vk-1} , ek=(vk, vk-1) となるもの
枝の向き無視
• 有向道(有向グラフ)
– 頂点 v0(始点)から,有向枝を辿って頂点 vq (終点)に至る頂点と枝の系列.
– q+1個の頂点 v0, v1, …, vq と q 個の枝 e1, e2, …, eq の系列として (v0, e1,
v1, e2, v2, …, eq, vq) と表すとき,ek=(vk-1, vk) となるもの
枝の向き重要
地理情報科学教育用スライド ©久保田李光一
グラフの構造(連結性)
• 連結性(無向グラフ,有向グラフ)
– グラフGのどの二つの頂点に対しても,一方を始点,他方を終点とす
る道が存在するとき,グラフG を連結グラフという.
– 連結でないグラフを非連結グラフという.
連結グラフ
非連結グラフ
地理情報科学教育用スライド ©久保田李光一
グラフの構造(2連結性)
• 2連結性(無向グラフ)
– 任意の2個の頂点を選び,その2個の頂点を結ぶ2本の有向道(同じ
頂点を経由しないもの)が存在するとき,そのグラフは2連結性がある
という
2連結グラフ
2連結グラフではない
地理情報科学教育用スライド ©久保田李光一
グラフの構造(連結成分)
• 連結成分
– 連結性を満たす頂点の集合で元のグラフを分割したとき,各部分集
合を連結成分という
全体で1個の連結成分
地理情報科学教育用スライド ©久保田李光一
2個の連結成分
グラフの構造(近接度)
• ネットワーク上の頂点を固定し,その頂点が他の頂点にどの
程度近いのかという近さを表す指標として,近接度がある
• 2頂点間の最短距離を d(u,v) と記す.頂点 u の近接度は,u から u 以外
の全ての頂点への最短経路の値の総和で定義される.
Au 
 d (u, v)
vはu以外の全ての頂点
– ウォーシャル・フロイド法で d(u,v) を計算すればよい.
池
池袋
新宿
御茶ノ水
秋葉原
東京
新 御 秋 東 近接性
0 6 11 13 15
6 0 15 17 19
11 15
0
2
4
13 17
2
0
2
15 19
4
2
0
地理情報科学教育用スライド ©久保田李光一
45
57
32
34
40