講義資料

2/30
教育目的（シラバスより）
現実に直面する問題を解く際に、
1.事前に問題のモデル化を行い、
2.そのモデル上での最適解を求め、
3.その最適解を元にして現実の問題を解くの
に役立てる、
というステップをとることは、実際、頻繁に用い
られているアプローチである。この講義では、現
実問題をモデル化する際によく用いられる「グラ
フとネットワーク」について、その基本用語と性
質とについて解説する。
グラフとネットワーク（１）
～基礎概念と用語～
教育目的（シラバスより）
3/30
最短路問題
巡回セールスマン問題
最小木問題
最大フロー問題
など、グラフ理論での代表的な問題とその解法と
を取り上げるとともに、アルゴリズム的に易しい
問題と難しい問題についても触れる。この講義を
習得させることにより、現実問題に対しての洞察
力やモデル化の能力を備えた学生を育成する。
授業計画
（１）基礎概念と用語
（２）グラフの分類
（３）グラフの連結性
（４）アルゴリズムと計算量
（５）グラフの探索
（６）オイラーの一筆書き
（７）最小木問題
（８）最短経路問題
（９）中間試験
（１０）フローの定義と性質
（１１）最大フロー問題
（１２）最大マッチング
（１３）最大フローのアルゴリズム
（１４）層ネットワークによる最大フローアルゴリズム
（１５）まとめ
（１６）期末試験
5/30
4/30
教育目標
下記の項目を、教育目標とする。
a. グラフ理論で用いる用語を、正しく使うことができ
る。
b. 代表的な問題について、問題の難しさおよび解法の
アルゴリズムを理解した上で解くことができる。
c. グラフ理論をモデル化の一道具として、現実問題に
適用することができる。
この科目は、ディプロマポリシーに掲げる
「情報工学に必要な、数学及び情報科学の諸理論
を習得し、それらを応用できる力」
に対応します。
6/30
講義の進め方（1）
• 講義は、パワーポイント資料（板書を併用）
を使います（演習に時間をとりたいので）
– 第２回以降のパワーポイントの資料は、
http://www.cs.miyazaki-u.ac.jp/~bisu/Graph/
にあるので各自で印刷すること。
（重要）
7/30
講義の進め方（2）
8/30
講義の進め方（3）
• 成績について（シラバスより）
• 出席について
– 4回以上欠席すると、単位が付かない
– 講義の最後に課す課題を提出した人を出席者とする
• 「課題が終わっていない」または「遅れて出席」した場
合は、欠席1/3扱いにします。（3回貯まると1回欠席）
• 課題の解答は、講義資料と同じページに掲示します。
• 連絡先
グラフ理論の用語や定義は、文献によって異なることがあ
ります。本講義で使う定義や記号は、基本的にこの文献に
従います。
(質問は、随時受け付けています)
– E-mail : [email protected]
9/30
勉強の仕方
何がわからないのか？
講義中は、メモを取る程度で話を聞く
ことに集中し、演習問題を解いて提出
する（講義）
• 教科書
なし
• 文献
「グラフ理論」連結構造とその応用（朝倉書店）
「グラフ理論入門」基本とアルゴリズム（森北出版）
– 居室：A229教室
– オフィスアワー：毎週木曜16：30～17：30
講義資料を印刷し、資料を見ながら
内容を理解するように努める（予習）
– 中間50点＋期末50点
– 合計60点以上が合格
10/30
今日の講義で学ぶこと
• グラフ(graph)とは？
– グラフの定義
– 辺(edge)と頂点(vertex)
– 無向グラフと有向グラフ
– 基本概念（接続と隣接など）
疑問
• ネットワーク(network)とは？
– ネットワークの定義
演習問題の解答を読んで、確認する。
また、自習問題を解く（復習）
質問する
http://www.cs.miyazaki-u.ac.jp/~bisu/Graph/（重要）
グラフとは？
11/30
【定義】グラフは、点の有限集合
V = {v1 , v2 , , vn } n :グラフの位数 (order)
と点対 ek = {vi , vj } である辺の有限集合
k
k
12/30
【注】無向グラフの場合は、
e1 = {v1 , v2 }、e2 = {v2 , v3 }
と記すべきだが、慣習で無向辺を
e1 = (v1 , v2 )、e2 = (v2 , v3 )
などと記すことがある。
E = {e1 ,e2 , ,em } m :グラフのサイズ (size)
v2
v2
によって、G = (V,E) と定義される。
【注】ek = {vik , vjk } は無向辺を意味する。
有向辺は、ek = (vik , vjk ) と記す。
v1
e1
e2
無向グラフ
v3
v1
e1
e2
有向グラフ
v3
13/30
a
c
q
r
b
s
【練習問題】
（１）右のグラフの位数を答えなさい
a
解答：5
頂点集合：V = {a,b,c,d}
p
辺集合：E = {p,q,r,s}
(無向)グラフ：G = (V,E)
辺の長さや形は関係ない
d
14/30
【注】本質的に同じグラフは、同形であるいう
辺を頂点で表したいときには、
（２）右のグラフの
サイズを答えなさい
解答：5
（３）頂点 a と頂点 c を結ぶ辺を答えなさい
解答：{a,c}
などと記す
p = {c,a} と書いても同じこと
グラフの実例(無向グラフ)
15/30
グラフの実例（有向グラフ）
【例】JRの駅の集合をV と考え、隣同士の駅の対をE
とすると、路線図に対応するグラフが出来る。
有向辺を
千歳
（仙台、千歳）
などと記す
ANA719
ANK311
このとき、直線で結ばれた２つの駅の間には、
線路があり、そこを走る電車を使って互いに移動
できることを意味する。
宮崎
加納
小松
仙台
木花
u
清武
JAL143
JAL101
伊丹
e
v
e
v
u
無向グラフ：e={u,v} または {v,u}
有向グラフ：e=(u,v) ≠ (v,u)
17/30
接続と隣接
【定義】グラフ G においてある頂点 u と辺 e が
16/30
羽田
ANA733
宮崎空港
南方
南宮崎
d
c
e
p = {a,c}, q = {a,b}, ・・・
田吉
b
18/30
【注】有向グラフの場合
接続するとは、u が e の端点であることをいう。
また、同一の頂点と接続する 2 つの辺は、
v
f
互いに隣接するという。
e
同様に、同一の辺の端点になっている 2 つの
頂点は、互いに隣接するという。
 頂点 u と v は辺 e の端点
v
f
 頂点 u と辺 e は接続する
e
w
u

辺 e と f は隣接する

頂点 u と v は隣接する
u
w

頂点 u を辺 e の始点

頂点 v を辺 e の終点

辺 e と f は隣接

辺 e は u から v へ接続
19/30
【練習問題】
（１）頂点 b に隣接する頂点を全て答えなさい
解答：a, c
a
（２）辺 {a,c}に隣接する
辺を全て答えなさい
解答： {a,b}, {b,c},
{c,d}, {c,e}
多重辺と多重度
b
無向グラフの多重辺
多重度３
有向グラフの多重辺
多重度2
d
c
e
（３）頂点 a に接続する辺を全て答えなさい
解答：{a,c}, {a,b}
21/30
多重グラフと単純グラフ
【定義】一般のグラフ（多重辺や自己ループ
を持つグラフ）を多重グラフ（multigraph）、
無向グラフの自己ループ
有向グラフの自己ループ
【練習問題】宮崎市、都城市、小林市の
３市とそれらを結ぶ一般道を無向グラフを
使って表現しなさい
22/30
小林
高岡
多重辺や自己ループを含まないグラフを、
宮崎
単純グラフ（simple graph）と呼ぶ。
A
町
20/30
B
B
町
モデル化
C
町
地図情報
A
C
都城
グラフ
23/30
【解答例】
山手線の路線図
24/30
「学生会館の総合情報サイト」より
http://www.gakuseikaikan-tokyo.com/
25/30
グラフの次数(degree)
【定義】グラフ G = (V , E ) のある頂点 v ∈ V に対し、
v に接続する辺の数を v の次数といい deg(v ) と記す。
b
deg(c) = 4
deg(d) = deg(e) = 1
G
d
c
e
【練習問題】
（１）頂点 a の次数を答えなさい
解答：deg(a)=2
a
b
（２）最大次数の頂点を
答えなさい
c
解答：c
deg(a) = deg(b) = 2
a
26/30
【注】次数の表し方には、
d
e
degG(v) d(v) d+(v) d-(v)
( d(v) = d+(v) + d-(v) )
（３）全ての頂点の次数の和を答えなさい
解答：10
など、多数あります。
27/30
【練習問題】グラフ G=(V,E) の辺の数は、
頂点の次数の和の半分である。すなわち、
 deg(u ) = 2 | E |
u∈V
28/30
【注】
• （無向グラフでは）自己ループの次数への
貢献は 2
• 有向グラフでは、
– 入る辺の数を入次数（indegree）
– 出る辺の数を出次数（outdegree）
であることを示しなさい。
v
indegree(v) = 1
outdegee(v) = 1
degree(v) = indegee(v) + outdegee(v) = 2
• 次数 0 の点は孤立点（isolated vertex）
ネットワーク（network）
29/30
【定義】与えられたグラフ G の辺や頂点に、
様々な量を付与したものをネットワークとい
う。
【注】重み付きグラフ（weighted graph）とも呼ばれる
5
【ネットワークの例】
5Ω
2
1.5V 1.5V
1.5V
3Ω
1.5
3
2Ω
3
ネットワークの表現
30/30
【定義】G = (V,E) をグラフとする。各辺の
重みを表す関数が
d : E → R + ≡ {x ∈ R | x > 0}
であるとき、この重み付きグラフを
N = [G;d]
と表現する。
【注】 有向グラフにおいては、一般に、d (u , v ) ≠ d (v , u )
 重みは頂点に与えられることもある
d : V → R + ≡ {x ∈ R | x > 0}

Download Report