SAS2006 第1回グラフ理論

SAS2006 第1回
グラフ理論
担当：IPUSIRON
1
2015/9/30
使用する資料

2
グラフ理論配布資料 #1
（http://chaosweb.complex.eng.hokudai.ac.jp/~j
_inoue/graph2006/GraphTheory06_1.pdf）
2015/9/30
グラフ理論と関連すること







3
ネットワーク理論
プログラミング
暗号理論
最適化問題
組合せ理論
ゲーム理論
化学
2015/9/30
今日やること

グラフとは何か
–
–

様々なグラフとその例
–
–
–
–
–
4
点、辺、次数
グラフの意味
多重辺、ループ、単純グラフ
有効グラフ
連結グラフ、非連結グラフ
オイラー・グラフ、ハミルトン・グラフ
木
2015/9/30
1.1 グラフとは何か
5
2015/9/30
グラフとは？


6
点と辺から成り立つ図形のこと
棒グラフや円グラフとはまったく関係ない
2015/9/30
点と辺

点（vertex）
–

P,Q,R,S,T
辺（edge）
–
P
Q
点Pを含む辺
PQ, PT, PS
–
点Rを含む辺
QR, RS
7
R
T
S
2015/9/30
次数

次数（degree）
–
–
ある点を端点とする辺の本
数
例：点Pの次数は3

–
deg(P)=3
点Pを基準
P1
Q
2
3
R
例：点Rの次数は2

deg(R)=2
T
S
よって、deg(P)=3
8
2015/9/30
グラフに意味を持たせる



9
例えば、点P,Q,R,T,Sをフッ
トボールのチーム名とする。
このとき、deg(P)=3といえ
ば、チーム名Pは3回試合を
行うと意味を持たせることが
できる。
同様にして、電気回路、ネッ
トワーク経路などをグラフで
意味を持たせることができ
る。
P
Q
R
T
S
2015/9/30
グラフの同形性



同形とは同じグラフである
ことを意味する。
グラフとは点とその結び方
（辺）の表現であり、辺の
距離などは関係がない。
不変量
–
–
10
同形な2つのグラフにそれぞ
れ同じ値が与えられるもの
のこと。
例：点の数、辺の数などが
不変量のひとつである。
P
Q
R
T
S
同じ
P
Q
R
T
S
2015/9/30
様々なグラフとその例
11
2015/9/30
多重辺、ループ

多重辺（multiple edges）
–
–

–
12
Q
R
S
ループ（loop）
–

2点間で、2本以上の辺が結ん
でいる場合、それを多重辺と呼
ぶ。
例：点Qと点Sの間の辺である
QSは2本ある。これは多重辺
である。
P
同じ点に戻る辺のこと。
例：点Rにはひとつループがあ
る。
単純グラフ（simple
graph）
多重辺やループを含まないグ
ラフのこと。
2015/9/30
有向グラフ

有向グラフ（directed
graph,digraph）
–

–

–

T
U
S
連結した辺の列。
上の例：P→S→Rというように連結され
た辺の列が歩道。
どの点も高々一度しか現れない歩道。
下の例：P→R→Q→R→Sという歩道
はRが2回現れているから、道ではない。
P
Q
R
S
2015/9/30
閉路（cycle）
–
–
13
R
道（path）
–
Q
辺に向きがあるグラフ。
歩道（walk）
–
P
矢印に従って最終的に戻ってくる道順。
上の例：P→R→T→U→Q→Pという道
順は閉路になっている。
有効グラフの例（じゃんけん）




14
じゃんけんは有効グラフで
現すことができる。
まず、点にそれぞれの登
場するものを与える。ここ
では、グー、チョキ、パー
の3点。
次に、矢印の向きに意味
を与える。矢印の先は矢
印の元より強いとここでは
決めた。
そうすると、右のような有
効グラフに表現できる。
グー
チョキ
パー
2015/9/30
連結グラフと非連結グラフ

連結グラフ（connected
graph）
–

非連結グラフ
（disconnected graph）
–

–
2
1
連結グラフでないグラフ。
成分（component）
–
15
どの2点も道で結ばれているグ
ラフ。
3
非連結グラフを構成する各グラ
フのこと。
例：右の非連結グラフの成分の
数は3である。
2015/9/30
オイラーグラフとハミルトングラフ

オイラーグラフ（Eulerian graph）
–
–

16
P
Q
R
S
ハミルトングラフ（Hamiltonian
graph）
–

すべての辺をちょうど一回ずつ通って
出発点に戻る歩道を含むグラフ。
一般の一筆書きの問題は、オイラー
グラフの歩道を見つける問題と同じで
ある。
すべての点をちょうど一回ずつ通って
出発点に戻る歩道を含むグラフ。
例：上はオイラーグラフになっている
（P→R→Q→R→S→Q→P）。
また、同時にハミルトングラフにもなっ
ている（P→R→S→Q→P）。
2015/9/30
木

木（tree）
–
–
–
–
17
どの2点の間にも道が1本し
かない連結グラフのこと。
例1：ワークステーションの
ファイルシステム
例2：生物の進化の系統図
例3：データ構造
2015/9/30
木の例（データ構造1）



18
データ構造の一種である「2分探索木」は木構造になって
いる。
点を色分けして改良したものも存在する。
詳細
http://sunak2.cs.shinshuu.ac.jp/~miyao/AL/Class/binary_search_tree.pdf
2015/9/30
木の例（データ構造2）
19
2015/9/30
例題1.1 問1

20
問：化学式C5H12を持つ分子はいくつかの構造の
異なる分子が存在する（構造異性体）。これらの分
子をすべて挙げ、それぞれに対応するグラフを描
け。
2015/9/30
問1 解答1



化学の知識（外殻）がなくても、簡単に解ける。
まず、Cという点が5つあるすべてのパターンを考
える。すると、次の3パターンしか存在しない。
ただし、点をCと置いた。
C
C
C
C
C
C
C
C
C
C
C
C
21
C
C
C
2015/9/30
問1 解答2

後は、C（炭素）の周りにH（水素）を配置すればよ
H
い。
H
H
ペンタン
H
H
H
H
C
C
C
C
C
H
H
H
H
H
H
H
H
H
C
H
22
H C
H
H
H
C
C
C
C
H
H
H
H
H
H
H C
H
H
C
C
H C H
H
2-メチルブタン
H
H
H
2-2-ジメチルプロパン
2015/9/30
例題1.1 問2

23
問：JohnはJoanが好きで、JeanはJaneが好きで、
JoeはJeanとJoanが好きで、JeanとJoanは互い
に好きである。
John,Joan,JeanおよびJoeの間の関係を説明す
る有効グラフを描け。
2015/9/30
問2 解答1






24
解：最初から完璧なグラフを
書くのは難しいので、ひとつ ①
ずつ見ていく。
矢印の先端を好きな相手を ②
向くようにする。
①JohnはJoanが好き。
②JeanはJaneが好き。
③
③JoeはJeanとJoanが好き。
④JeanとJoanは互いに好き。
John
Joan
Jean
Jane
Joe
Jean
Joe
Joan
④ Jean
Joan
2015/9/30
問2 解答2

後はこれらを組み合わ
せればよい。
Jane
John
Jean
Joan
Joe
25
2015/9/30
例題1.1 問3

26
a,b,c,d,e,fの6チームで
ホッケーの試合をすること
になった。
各チームの行った試合数
は右の表の通りである。
このとき、考え得る試合の
組み合わせをグラフで表し、
それらをすべて描け。
ただし、同一カードは2試
合以上行わないとする。
チーム名
試合数
a
2
b
2
c
4
d
4
e
3
f
1
2015/9/30
問3 解答1


まず対戦数の多いものから考えるとわかりやすい。
そこで、まずcは4回試合するので、その全パターンを考える。
a
a
a
f
b
f
e b
c
d
e b
c
a
d
b
c
d
f
eb
c
e
a
f
27
f
d
e
c
d
2015/9/30
問3 解答2



次に、dを考える。これも4回試合する。さきほど示した5パターンに書き加えて
みる。
ここで、fは1試合しかしないことを考えると、8パターンになる。
これでc,d,fはクリアした。
a
a
a
f
b
f
e b
c
d
d
d
d
c
f
e
d
e
b
f
e
c
d
a
f
c
b
a
eb
c
f
e
c
a
f
28
f
e b
c
a
b
a
d
b
e
c
d
2015/9/30
問3 解答3


そして、aを考える。ただし、もうc,dには連結してはならない。
ただし、bは2試合、fは1試合しかしないことを考慮しておく。
a
a
a
f
b
f
e b
c
d
d
29
d
c
d
f
e
d
e
a
f
c
b
a
eb
d
f
e
c
a
f
c
f
e b
c
a
b
a
b
f
e
c
d
b
e
c
d
2015/9/30
問3 解答4


bを考える。
もうa,c,dには連結はできないとする。
a
a
a
f
b
f
e b
c
d
d
d
d
c
d
f
e
d
e
a
f
c
b
a
eb
c
f
e
c
a
f
30
f
e b
c
a
b
a
b
f
e
c
d
b
e
c
d
2015/9/30
問3 解答5

fを考える。ピンク色の線。
a
a
a
f
b
f
e b
c
d
d
31
d
c
d
f
e
d
e
a
f
c
b
a
eb
d
f
e
c
a
f
c
f
e b
c
a
b
a
b
f
e
c
d
b
e
c
d
2015/9/30
問3 解答6


最後にeを考える。
もうe以外のすべてを決定しているので、もう線を繋ぐことはできないの
で、eが3本でないものパターンは除外する。
a
a
a
f
b
f
e b
c
d
d
32
d
c
d
f
e
d
e
a
f
c
b
a
eb
d
f
e
c
a
f
c
f
e b
c
a
b
a
b
f
e
c
d
b
e
c
d
2015/9/30
問3 解答7

ゆえに次のパターンが答えになる。
a
a
f
b
e
c
a
b
33
b
d
d
a
f
eb
d
e
c
a
f
c
f
f
e
c
d
b
e
c
d
2015/9/30
例題1.2 問1

点の集合が V  {v1 , v2 , v3 , v4 , v5 , v6}
与えられ、かつ辺の集合が
E  {v1v3 , v2v3 , v3v4 , v4v1, v4v3 , v5v6}
からなるグラフを描け。
34
2015/9/30
問1 解答1

35
6つの線を書く。ただし点のvは略する。
1
3
2
3
3
4
4
1
4
3
5
6
2015/9/30
問1 解答2

後はこの線たちを組み合わせて、グラフを描けば
よい。
1
3
2
5
6
4
36
2015/9/30
例題1.2 問2




37
ヘビはカエルを食べ、トリはクモを食べる。
トリとクモはどちらも虫を食べる。
カエルはカタツムリ、クモ、および虫を食べる。
この捕食行動を表す有向グラフを描け。
2015/9/30
問2 解答1


38
登場人物は、ヘビ、カエル、トリ、クモ、虫、カタツ
ムリの6種類である。
矢印の先は食べられる側とする。
ヘビ
カエル
カエル
カタツムリ
トリ
クモ
カエル
クモ
トリ
虫
カエル
虫
クモ
虫
2015/9/30
問2 解答2

7種類の矢印を組み合わせればよい。
ヘビ
クモ
トリ
カエル
カタツムリ
39
虫
2015/9/30
演習問題1(1)


40
身の回りの事柄で、それが「木」のグラフで表現で
きるものをひとつ挙げよ。
ただし、ワークステーションのファイルシステム、生
物進化の系統図、有機化学物の構造以外を選ぶ
こと。
2015/9/30
演習問題1(1) 解答1

41
DNS（ドメイン名からIPアドレスを探索する仕組み）は木構造である。
2015/9/30
演習問題1(1) 解答2


42
文の構造は、木構造で
ある。
「Time flies like an
arrow.」の木。
2015/9/30
演習問題1(2)


43
どの辺の2つの端点も異なる集合（グループ）に属
するようにn個の点を2分割するようなグラフを2部
グラフと呼んでいる。
このとき、n=7である2部グラフを描き、そのグラフ
が奇数本の辺からなる閉路を含まないことを示せ。
2015/9/30
演習問題1(2) 解答1



2部グラフとは次のように2つの集合にわけられたグラフのことである。
ここでは点の数は7個なので、上の7個と下の7個しかない。
ただし、線は下と上しか結びつかない。横（同じグループに属するもの
同士）はダメ。
上のグループ
下のグループ
44
2015/9/30
演習問題1(2) 解答2



45
閉路を作るように線を結ぶ。
下の点→上の点→下の点→上の点という4つの線
が必要。つまり、線の本数は偶数である。
奇数にはなることはない。
2015/9/30

Download Report