グラフとネットワーク (第1回) グラフ, ネットワークとは何か

グラフ, ネットワークとは何か?
グラフとネットワーク (第 1 回)
グラフの例 1 (電気回路)
システムにおける構成要素間の「つながり」を
抽象化した概念.
a10
静岡大学システム工学科
v1
安藤 和敏
v4
a1
a4
a5
v5
a2
a8
a3
a6
v2
a9
a7
v3
G
グラフとネットワーク (第 1 回) – p.1/31
グラフとネットワーク (第 1 回) – p.2/31
グラフとネットワーク (第 1 回) – p.3/31
グラフの例 2 (コンピュータ・ネットワーク)
グラフとネットワーク (第 1 回) – p.4/31
グラフとネットワーク (第 1 回) – p.5/31
グラフとネットワーク (第 1 回) – p.6/31
グラフの例 3 (アローダイヤグラム)
本講義で学べること
作業 処理時間 先行作業
A
2
—
B
5
—
C
4
—
D
3
A,B
E
3
B,C
F
4
C
G
5
D,E
H
2
E,F
D
3
A
2 B
5
start
5
0
E
3
C
4
0
H
最短路問題
2
最大流問題
0
最小費用流問題
F
4
に対するアルゴリズムについて学ぶ.
グラフとネットワーク (第 1 回) – p.8/31
最小木問題
16
a
h
31
d
22
21
23
b
15
(a)
k
a
d
25
b
16
g 12
k
35
f
a
d
22
21
23
(b)
15
(a)
a
d
25
32
21
g 12
20
35
f
k
グラフ G = (V, A) と枝の重み w: A → R が与
えられているとする. G の木 T に対して,
h
22
18
g 12
20
25
b
32
29
k
35
f
w(T ) =
25
(b)
(a) グラフ G と w: A → R; (b) G の木 T (太字
の枝)
グラフとネットワーク (第 1 回) – p.10/31
グラフとネットワーク (第 1 回) – p.9/31
木の重み
h
31
32
21
20
35
f
h
22
18
g 12
20
木
32
29
最小木問題
end
0
グラフとネットワーク (第 1 回) – p.7/31
b
グラフについての諸概念を学んだ後, グラフや
ネットワーク上で定義される以下の問題
G
0
グラフとネットワーク (第 1 回) – p.11/31
w(a)
(2.1)
a∈T
を木 T の重みという.
グラフとネットワーク (第 1 回) – p.12/31
木の重み (例)
b
16
22
d
23
15
16
18
20
d
22
32
21
15
23
a
g 12
29
h
31
32
21
a
b
h
31
g 12
29
k
35
18
20
k
35
25
25
f
f
重み= 155
最小木問題
最短路問題
最小木問題とは, 重みが最小である木を見付け
る問題である.
最小木問題を解くためのアルゴリズムには, 貪欲
アルゴリズムとヤルニーク-プリムのアルゴリズ
ムが良く知られている.
有向グラフ G = (V, A) の各枝 a に対して, その
長さ l(a) を指定する関数 l: A → R が与えられ
ている.
h
4
重み= 112
1
1
f
g
e
1
4
3
1
4
3
b
d
2
8
7
s
グラフとネットワーク (第 1 回) – p.13/31
グラフとネットワーク (第 1 回) – p.14/31
有向道
f
1
1
4
g
3
1
1
b
8
7
P = (v0, a1, v1, a2, v2, a3, · · · , ak , vk )
1
4
3
d
2
g
4
e
3
4
3
1
1
f
4
e
ネットワーク N = (G = (V, A), l) が与えられ
ているとする. G の中の有向道
h
1
有向道の長さ (例)
有向道の長さ
h
4
グラフとネットワーク (第 1 回) – p.15/31
b
d
2
8
に対して,
k
s
(a)
(b)
l(ai) を P の長さと呼ぶ.
グラフとネットワーク (第 1 回) – p.16/31
a4
a2
v1
1
1
f
1
g
a3
v2
v3
v4
a5 a6
v6
v7
7
v8
(a)
長さ= 16
グラフとネットワーク (第 1 回) – p.17/31
g
4
e
3
1
4
3
d
s
v5
f
4
2
1
1
1
1
b
a8
4
4
e
8
a7
a1
(a) ネットワーク N ; (b) N の s から h への有向
道 (青い枝)
4
3
v0
s
h
3
i=1
7
h
b
d
2
8
7
s
(b)
長さ= 3
グラフとネットワーク (第 1 回) – p.18/31
最短路問題
ネットワーク N = (G = (V, A), s+, s−, c)
最大流問題
最短路問題とは, 与えられた 2 点 u, v ∈ V に対
して, u から v への長さが最小の有向道を見付け
る問題である.
2
2
g
b
1
s+
2
e
5
2
3
sd
2
f
2
ネットワークには, 特別な 2 点: s+ と s− があ
る. さらに, 各枝 a ∈ A に対して容量 c(a) が与
えられている.
グラフとネットワーク (第 1 回) – p.19/31
グラフとネットワーク (第 1 回) – p.20/31
ネットワーク N 中のフロー
ネットワーク N 中のフロー (flow) とは, つぎの
(i),(ii) を満足する枝集合上の実数値関数
ϕ: A → R のことである.
(i) 容量制約: 各枝 a
∈ A に対して
0 ≤ ϕ(a) ≤ c(a).
(2.25)
(ii) 流量保存則 (キルヒホッフの法則): 各点
v ∈ V \ {s+, s−} に対して
ϕ(a) −
ϕ(a) = 0.
a∈δ + v
フローの例
2/2
1/1
s+
3/5
1/3
フローの流量
流量保存則によって,
1/2 b
g
e
v ∗(ϕ) =
1/2
2/2
s-
f
a∈δ + v
d
2/2
グラフとネットワーク (第 1 回) – p.21/31
ϕ(a) −
ϕ(a)
a∈δ − v
をフロー ϕ の流量 (value, flow value) という.
2/2
各枝 a に付された数は, ϕ(a)/c(a) を意味する.
(2.26)
a∈δ − v
グラフとネットワーク (第 1 回) – p.22/31
グラフとネットワーク (第 1 回) – p.23/31
グラフとネットワーク (第 1 回) – p.24/31
最大流問題
2/2
1/2
g
3/5
1/3
e
与えられたネットワーク
b
1/1
s+
N = (G = (V, A), s+, s−, c) に対して, N 上の
フロー ϕ でその流量 v ∗ (ϕ) が最大であるような
1/2
2/2
s-
d
2/2
f
最大マッチング問題
ものを最大フロー (最大流) (maximum flow) と
呼び, 最大フローを求める問題を最大フロー問
題 (maximum flow problem) と呼ぶ.
2/2
1
a
2
b
3
∗
v (ϕ) = 5.
c
4
グラフとネットワーク (第 1 回) – p.25/31
グラフとネットワーク (第 1 回) – p.26/31
2 部グラフ G
1
a
マッチング
最大マッチング問題
枝の部分集合 M は, M のどの 2 本の枝も点を
共有しないとき, G のマッチングと呼ばれる.
枝の本数 |M | が最大の G のマッチングを最大マッ
チングと呼び, 最大マッチングを求める問題を最
大マッチング問題と呼ぶ.
1
1
a
2
2
b
3
a
2
b
3
b
3
c
c
4
グラフとネットワーク (第 1 回) – p.27/31
4
c
4
M (青い枝たち) は G この M (青い枝たち)
は, G のマッチングで
のマッチング
はない
グラフとネットワーク (第 1 回) – p.28/31
グラフとネットワーク (第 1 回) – p.29/31
グラフとネットワーク (第 1 回) – p.30/31
テキスト
藤重悟: グラフ・ネットワーク・組合せ論. 共立
出版, 2002 年.
グラフとネットワーク (第 1 回) – p.31/31