グラフ理論 #3
第3回講義 5月7日--- いろいろなグラフの例とパズル --情報科学研究科 井上純一
http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/

演習問題2 (1)の解答例
数列(3,3,3,3,3,3,3,3,3,3)はグラフ的であり、右のようなグラフが描ける
これでも良い

演習問題2 (2)の解答例
12

34abh

K 4,4g
567G1

同型写像：

このとき

c8fdeG2

空グラフ
空グラフ (null graph) : 辺集合が空であるグラフ

辺が無い

N4n 点からなる空グラフを

N n と書く完全グラフ完全グラフ (complete graph) :相違なる2つの点が全て隣接しているグラフ

K5K4

K n の辺の本数n(n − 1)n C2 =2

正則グラフr-正則グラフ (regular graph) :どの点の次数も全て共通にrであるグラフ

次数2の正則グラフ=閉路グラフ
次数3の正則グラフ= 次数4の完全グラフ
3-regular graph2-regular graph閉路グラフと道グラフ
閉路グラフ (cycle graph) :次数2の正則連結グラフ

C6道グラフ (path graph) :閉路グラフから一つの辺を除いて得られるグラフ

P6C6車輪車輪 (wheel) :Cn −1 に新しい点v を加え、 vと他の全ての辺を結んでできるグラフv
C5W
6スポークで結ぶ

ピータースン・グラフ
前回の演習問題２ (1)全ての次数が3である10点からなるグラフ
次数列は(3,3,3,3,3,3,3,3,3,3)

ピータースン・グラフはハミルトン・グラフであろうか？

二部グラフ
二部グラフ (bipartite graph) :グラフGの点集合を素な2つの集合A、Bに分割し、Gの全ての辺はAの点とBの点を結ぶようにしてできあがるグラフ
Aこの2本の辺を加えことにより、Aの各点がBの各点とちょうど1本の辺で結ばれるようになるGB⇒ 完全二部グラフ

完全二部グラフ
完全二部グラフ (complete bipartite graph):
Aの各点がBの各点とちょうど１本の辺で結ばれた二部グラフ

黒r個、白ｓ個からなる完全二部グラフ
K 1,3K r ,sK 2,3と表記する

K 3,3

K 4,3

zQ3(0,0,1)k-立方体(0,1,1)(1,0,1)(1,1,1)y(0,0,0)k-立方体 (K-cube)(0,1,0)(1,0,0)ai = 0,1 であるような1つの列ベクトル(1,1,0)(a1 , a2 ,..., ak ) に一つの点を対応させ、

x100

101

Q3一つだけ異なる成分を持つ二つのベクトルに対応する二つの点が辺で結ばれるような正則二部グラフQk1101112001010000001

k 個の点とk2k −1本の辺を持つ食い違う位置を指定した
場合に一つだけ成分の異なるベクトルを選ぶ場合の数単純グラフの補グラフ
単純グラフGの補グラフ (complement) :単純グラフGの点集合を持ち、2点が隣接するのは、Gにおけるそれらの2点が隣接していないとき、かつ、そのときに限るグラフ
uuyyvvxwxw例）☆ 完全グラフの補グラフは空グラフ☆ 完全二部グラフの補グラフは2つの完全グラフの和である

8つの円の配置問題#3

問題: #1～#8にA～Hの8つの文字をアルファベットで隣り合う文字が隣接しないように置け

#4CE

#7

G

#1

#2

AH

#8

B
着眼点FD
#5

#6

☆ AとHの配置の仕方は易しい☆ #1、#2の円への配置が最も難しい

4つの立方体パズル
cube1

cube2

RBGRRY

B

GB
Y

R

GGGY

Y

Y

cube3BR

B

cube4BR

RY

解法のステップ #1
cube1
B

R

平行な面に塗られた色 R
どうしを結ぶ ⇒GRGR

B

cube2G

B

Y

R

GB

cube4cube3Y

B

R

Y

R

cube1

Y

G

Y

解法のステップ #2
33

G

R
2

B

1

1

4

1

4
2

42G

Y

3
ステップ #１で求めた4つのグラフを重ね合わせる

解法のステップ #3
各cubeの辺を1本ずつ含み、共通な辺が無く、次数2の正則グラフとしてGの部分グラフH1、H2を選ぶ

解法の最終ステップ
H1 ( FB), H 2 ( LR)
を用いて、cube1、cube2、cube3、cube4を積み上げる

例題3.1
点1に接続してる辺の=1+1=2(次数)112G⎛1 1 0 0 ⎞⎜⎟1111⎟M =⎜⎜0 0 1 0⎟⎜⎜⎟⎟⎝0 0 0 1⎠
332
4

辺1の両端の点の個数= 2 (握手補題より）
4

両辺は接続行列の成分の総和を表している∑ deg ( v ) = 2ε ( G )v∈V ( G ) グラフGの次数和

辺の数=接続行列の列の数

例題3.2

隣接行列12543⎛ 0 1 1 1 1⎞⎜⎟
⎜1 0 1 1 1 ⎟A = ⎜1 1 0 1 1 ⎟⎜⎟⎜1 1 1 0 1 ⎟⎜1 1 1 1 0 ⎟⎝⎠⎛ 4 3 3 3 3⎞
点1と点3を結ぶ長さ2の歩道の数⎜⎟
34333⎜⎟
2A = ⎜3 3 4 3 3⎟⎜⎟ 今週の 演習問題3 参照
これを一般化すると⎜3 3 3 4 3⎟
⎜3 3 3 3 4⎟⎝⎠⎡⎣ A K ⎤⎦ は点 i と点 j を結ぶ長さＫの歩道の数に等しいij例題3.3（完全三部グラフ）
AB

K 2,2,2

K r ,s ,t の辺数はC

rs + st + tr

例題3.4の1.
(iv) 11個の点を持つ正則グラフはあるか？
n=4, m=6

n=6, m=9数列 (3,3,3,3,3,3,3,3,3,3,3)はグラフ的か？
n=8, m=12

n=10, m=15

※ n=4,6,8,10,12の場合の３次グラフはある

握手補題より3nm=2

辺数n=12, m=18

辺数mは整数でなければならないのでn=11の場合には不可能

例題3.4の2.(1)問題となるグラフとその補グラフの和は完全グラフとなるべきである
問題のグラフの辺数は∴ n = 4k , 4k + 1n(n − 1)
m=4（辺数は整数でなくてはいけない）
k=1のとき, n=4L+2
M=6
次数１の点数 次数２の点数
L+M = 4
この解は( L, M ) = (2, 2)

破線と実線のグラフがそれぞれ自己補対例題3.4の2.(1) #2
k=1, n=4k+1=5の場合には

L + 2 M + 3 N = 10

次数３の点数L+M + N =5
その解は

( L, M , N ) = (1,3,1),(2,1, 2),(0,5,0)
対応する次数列は(3,2,2,2,1), (3,3,2,1,1), (2,2,2,2,2)
これは描けない例題3.4の2.(2)k=2, n = 4k=8 の自己補対グラフの例
1(1) ８個の点を時計回りに並べる
2(2) ８個の点のうち奇数番の点に関して完全グラフを作る

83(3) 奇数番目の点とその点の番号+1番目の点どうしを結ぶ(4) 偶数番目の点とその点+3番目の点を結ぶ

7自己補対グラフの探し方

465

演習問題31122

黒板でヒント＆簡単な解説を与えます。
34