グラフとネットワーク（2）今日の講義で学ぶこと部分グラフ（subgraph）

2/30
今日の講義で学ぶこと
• 基礎概念と用語
– 多重グラフ（multi-graph）と単純グラフ
（simple graph）
– 部分グラフ（subgraph）
– 補グラフ（complement graph）
– 平面グラフ（planar graph）
– パス（path）と閉路（cycle, circuit）
– 連結性（第3回に詳しくやります）
– 点と辺の除去
グラフとネットワーク（2）
～基礎概念と用語、グラフの分類～
• 特殊なグラフ
–
–
–
–
多重グラフと単純グラフ（復習）
3/30
【定義】一般のグラフ（多重辺や自己ループ
を持つグラフ）を多重グラフ（multigraph）、
多重辺や自己ループを含まないグラフを、
単純グラフ（simple graph）と呼ぶ。
A
町
完全グラフ（complete graph）
正規グラフ（regular graph）
2部グラフ（bipartite graph）
木グラフ（tree graph） ← 次週にやります
部分グラフ（subgraph）
【定義】
G = (V,E) とする。V と E の部分集合
X ⊆V, F ⊆E
によって定まる G = (X,F) がグラフである
とき G は G の部分グラフであるという。
B
B
町
G の部分グラフの例
モデル化
C
町
地図情報
4/30
G
A
C
グラフ
5/30
【注】G = (X,F) がグラフ
⇔ e = (u,v)∈F ならば u,v∈X
【練習問題】次の H と S は、グラフである
かどうか答えなさい。
6/30
【定義】G = (V,E) をグラフとする。
V の部分集合 X が与えられ、
u,v ∈ X かつ e = (u,v) ∈ E
⇒ e = (u,v) ∈ F
ならば、G = (X,F) を G の X による誘導部分
グラフ（induced subgraph）と呼び G = G[X]
と記す。
【注】生成部分グラフと記すこともある
H=(A,B)
S=(C,D)
A={p,q,r,s}
C={p,q,r,s}
B={{q,p},{r,q},{s,s}} D={{p,r},{r,w},{q,s}}
v1
e3
e1 v
2
e4
e5
G v3 e v4
6
e2
X = {v1,v3,v4}
v1
e4
e3
v3
e6
v4
誘導部分グラフ G[X]
7/30
【練習問題】次のグラフ G において、X={v1,v3,v4,v5}
の誘導部分グラフ G[X] を求めなさい
8/30
補グラフ（complement graph）
【定義】単純グラフ G=(V,E) に対して、
同じ点集合 V を持ち、辺の存在と非存在を
逆転して得られるグラフ
v6
G = (V , E ), E = {(u , v ) ∈ V 2 | (u , v ) ∉ E }
v4
v1
を G の補グラフという。
v5
v2
v3
G の補グラフ
G
G
9/30
平面グラフ（planar graph）
10/30
【練習問題】次のグラフは平面グラフであ
るかどうか答えよ。
【定義】グラフを図に描いたとき、辺の間に交わり
が無いグラフを平面描画という。
また、平面描画可能なグラフを平面グラフと呼ぶ
このグラフは平面グラフか？
a
b
しかし
d
c
辺に交わりがあるので
平面描画ではない
オイラーの公式
a
c
d
b
平面描画可能なので
平面グラフである
資料
11/30
【定理】連結な平面グラフ G=(V,E) において、
|V | + 面数 = |m| + 2
が成り立つ。
【注】ただし、面とは平面描画したとき辺で囲まれ
た領域のことである。無限遠点を含むグラフの外側
も１つの面と数える。
パス（路、道、経路、path）
【定義】グラフ G 上のパスとは、始点と呼ば
れる頂点から始まり、終点と呼ばれる頂点で
終わる頂点と辺が交互に現れる列であり、列
中で隣り合った辺と頂点が接続しているもの
である。
パスの例としては、
a
p1=aqbrc
p
c
q
|V | = 4
|m| = 5
面数 = 3
|V | = 5
|m| = 6
面数 = 3
12/30
r
b
s
p2=apcrbrc
などがある。
どちらも、a を始点、c を
d
終点にもつパスである。
p1 = a,q,b,r,c
abc (a,b,c)
などと記すこと
もある
パスの長さ（length）
13/30
【定義】無向グラフ G = (V,E) の各辺 e∈E に
d(e) の重みが与えられているネットワークを考
える。このとき、パス
P = v1v2 … vk
(P = v1e1v2e2 … ek-1vk)
において ej = {vj,vj+1} とするとパス P の長さを
閉路（cycle, circuit, closed path）
【定義】始点と終点が等しいパスを閉路という
【注】単純グラフにおいて、1 つの点は長さ 0
の閉路、自己ループは長さ 1 の閉路と見なす
ことがある
a
k −1
 d (e )
【閉路の例】
j
c
j =1
と定める。
d
15/30
【定義】パス[閉路] P が同じ辺を 2 度以上
用いていないとき初等路[res. 初等閉路]、
2 度以上同じ点を通っていなければ単純路
[res. 単純閉路]という。ただし、単純閉路の
場合、始点と終点は例外とする。
a
b
p1=abca
閉路 p1 の長さは 3
b
【注】辺に重みがない場合は、k-1 と定める
初等路（elementary path）と
単純路（simple path）
14/30
16/30
【練習問題】下記の図を使って単純閉路で
はない初等閉路の例をひとつ挙げよ
a
d
解答例
e
b
c
c【初等閉路かつ単純閉路の例】
p1=abca
d
17/30
【注】グラフ G が有向グラフの場合も、
パスと閉路の定義を自然に拡張すること
ができる。
ただし、有効グラフのパスは全て有向
辺の方向に進むので、有向路（directed
path）、有向閉路（directed circuit）と呼
ぶこともある。
初等路[閉路]、単純路[閉路]についても
同様である。
参考
18/30
【注】パスや閉路に関する用語の定義は、
全体として定まっておらず混沌としている。
文献を読む際は、定義を確認すること
【例】
「パス」はウォーク(walk)と呼ばれることもある。
このときは、「パス」は単純路を意味する。また、
初等路はトレイル（小道、Trail）などと呼ばれる
この講義では、このような定義は使いません！
19/30
連結性（connected）
20/30
辺の除去
【定義】グラフ G の任意の 2 つの頂点の間
にパスが存在するときグラフ G は連結であ
るという。
a
b
c
a
a
c
G1
q
c
G2
r
G1 は連結だが、 b
b
d
d
d
G2 は連結でない
辺 {a,d}を除去する
21/30
点の除去
a
22/30
【練習問題】次のグラフについて答えなさい
a
b
c
b
c
d
d
e
e
（1）辺 {a,c} を除いた
グラフを描きなさい
（２）頂点 c を除いた
グラフを描きなさい
e
点 a を除去する
完全グラフ（complete graph）
23/30
【定義】すべての点対 {u,v} を辺とする
無向グラフ G = (V,E) を、完全グラフと
いい、Knと記す。
K3
K4
【練習問題】
24/30
(1) 頂点数 5 の完全グラフ K5 を描きなさい
(2) K5 の補グラフ K5 を描きなさい
(3) K5 の辺の数を答えなさい
25/30
レギュラーグラフ（regular graph）
【定義】各頂点の次数が等しいグラフを、
正則グラフ、またはレギュラーグラフという。
また、この次数が k の正則グラフは、k-正則
グラフ（k-regular graph）という。
26/30
2部グラフ（bipartite graph）
【定義】グラフ G = (V , E ) の点集合 V が空で
ない 2 つの集合 V 1 と V 2 に分割され、全ての
辺 e ∈ E において、端点の一方が V 1、他方が
V 2 に属しているとき、G を 2 部グラフと呼び、
G = (V 1 , V 2 , E ) と記す。
全ての u ∈ V 1 と v ∈ V 2 の間に辺が存在する
とき、G を完全 2 部グラフ(complete bipartite
（K3）
graph ) と呼び、| V 1 |= m , | V 2 |= n のとき、
3-正則グラフ
2-正則グラフ
【注】完全グラフは、正則グラフ
27/30
2部グラフの例
V1
2 部グラフ
V2
完全 2 部グラフK3,2
【練習問題】次のグラフは、2部グラフか
どうかを判定しなさい。
b
a
2部グラフの具体例
29/30
A
データ集計
B
ワープロ
C
窓口業務
D
簿記
E
受付
誰にどの仕事を割り
当てたら良いか？
マッチング問題
（組合せの問題）
スターグラフ（star graph）
30/30
【定義】K1,n なる完全 2 部グラフは、
スターグラフと呼ばれる
【注】スターグラフは、特殊な完全 2 部グラフ
c
e
28/30
人にはそれぞれ適性がある。適性のある仕事
に線を引くと2部グラフが出来る。
V1
V2
Km ,n と記す。
d
スターグラフ K1,5

Download Report