グラフ理論 講義ノート #1
井上 純一
北海道大学 大学院情報科学研究科
URL : http://chaosweb.complex.eng.hokudai.ac.jp/˜j inoue/

平成 19 年 4 月 16 日

目次
1

イントロダクション — ウォーミングアップ —1.1 ここで扱う「グラフ」とはいったい何か ? . . . . . . . . . . . . . . . . . . . . . . . . . . .

121.1.1
1.1.2

点, 辺, 次数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

221.1.3

グラフの同形性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.21

グラフに意味を持たせる . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

様々なグラフとその例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

331.2.1
1.2.2

多重辺, ループ, 単純グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.3
1.2.4

連結グラフと非連結グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
オイラー・グラフとハミルトン・グラフ . . . . . . . . . . . . . . . . . . . . . . . .

451.2.5

木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5有向グラフ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

イントロダクション — ウォーミングアップ —まずは本講義で扱う「グラフ」の定義から始め, 本講義で習う事項を概観することにしょう. それぞれの概念の詳細および応用例は回を進めるごとに追々見て行くことになる.
講義を進めるうちに幾つかの定理, 系, 補題が出てくるが, 本講義ではそれらの中で比較的重要と思われるものに関しては, その証明を追ってみるが, それ以外のものに関しては, 具体的な例/応用例を取り上げ,諸定理の意味を直観的に理解し, 有用性を確認するにとどめる. 講義で取り上げなかった証明に関しては各
自が教科書を読み, 必ず一度はその流れを追ってみること.
各回の配布資料の最後には 演習問題 が付いている. 当講義の単位を必要とする受講者は次回までに, これらの問題を解き, レポートとして提出すること. 最終成績のうちの約 40 % はこのレポートの積み重ねで決まることになる. なお, 期日を過ぎたレポートは一応受け取りはするが, 他のレポートには見られない独自の視点で問題が解かれており, かつ, それが正解である場合を除いては「ゼロ点」として評価するのでレポートの〆切期日は厳守されたい.
また, 途中に現れる例題 *.* は過去 4 年間 (2002-2006 年度) にわたって当講義で 演習問題 として出題されたものに解答/解説をつけたもの (場合によっては補助問題/発展問題もついている) である. 時間の都合上, 講義時間内には取り上げることのできないものもあるが, 各回の 演習問題 はこの例題の類題を選ぶ
場合が多いので, 各自がこれらの例題とその解答を一度は追っておくこと. グラフ理論の理解にはできるだ
け多くの例題にあたり, 沢山のグラフを自分で実際に描きながら問題を解くことが重要であるように思う.

1

グラフ理論 2007 #1

1.1

北海道大学 大学院情報科学研究科 井上純一

ここで扱う「グラフ」とはいったい何か ?

グラフに関する詳しい説明を始める前に, ウォーミングアップとして基本的な概念を概観することにする. どの科目でもそうであるが, グラフ理論においても, はじめに覚えなければならない幾つかの用語や定義がある. 決して難しくはないが, これから教科書や講義ノート, あるいはより進んだ専門書, 論文等を読み進めるにあたり支障がでないように, この段階できちんと押さえておくことが慣用である.

1.1.1

点, 辺, 次数グラフというと我々のもつイメージとしては物理実験などでお馴染みの速度の時間的な変化を表す「グラフ」, 企業の年度別収益などを表す「棒グラフ」などが思い浮かぶが, グラフ理論で扱うグラフはこれらとは異なり, 点および辺からなる, より抽象的な幾何学図形である.
☆ グラフ ・・・点 (vertex) (図 1 の P,Q,R,S,T) , 及び, 辺 (edge) (図 1 の PQ, QR 等) からなる図形.
PQRTS

このグラフの点数は n = 5, 辺数は m = 8 であり, それぞれの点の次数は deg(P) =deg(T) = 3, deg(Q) = deg(S) = 4, deg(R) = 2 である.

図 1: この講義で扱う「グラフ」の一例.

☆ 次数 (degree) ・・・ ある点を端点とする辺の本数.
例 : 図 1 の点 P の次数は 3. 図 1 の点 Q の次数は 4.
これを式で表すと次のように書ける1 . グラフにおける次数とは, 下記のように P,Q のように点を指定して初めて定義される量であることに注意しよう.
deg(P)=deg(Q) =

1.1.2

34(1)

グラフに意味を持たせる

我々は今までにも無意識のうちに上記のようなグラフを用いて実問題を表してきた. 例えば, 図 1 のP,Q,R,R,T ・・・フットボールチーム ⇒ 各点の次数がそのチームが行う試合数となる. こうすることによって, 格段に対象に対する見通しが良くなるからであるが, 例えば, このグラフから点 P の次数を確認することで「deg(P) = 3 ⇒ チーム P が行う試合数は 3 である」のように有益な情報を得ることができる. グ
ラフ理論ではこうした見方を体系立てて学んでいく.
※ この他にも, 電気回路, 道路等, 様々な形でグラフに意味を持たせ, その対象をグラフ理論的な考察に基づき調べることができる. ⇒ 例題 1.1 2,3 参照.

1 点 (頂点) の個数をこの講義ノートでは「点数」と呼び, 例えば, 5 個の数からなる持つグラフの点数を n = 5 と表記するが, 教科書によっては, この数を位数と呼び, グラフ G の位数を |G| と表すものも多い (また, 辺数は ||G|| と表す場合もある). このように, 同じグラフ理論の記号でも教科書や文献によっては異なる記号, 呼び方をする場合があり, それが初学時の悩みの種となっている. 本講義では一貫した呼び方, 記号を使うので問題はないが, 近い将来, より進んだ学習をする際には注意が必要である.

ここは 2 ページ目

グラフ理論 2007 #1

1.1.3

北海道大学 大学院情報科学研究科 井上純一

グラフの同形性グラフとは点の集合とそれらの結び方 (辺の集合) の表現であり, 距離的な性質とは無関係である. 例えば, 下記の 2 つの図形はグラフ理論においては同じものとして扱われる. 従って, 実問題をグラフで表現す

PQQR

PT=RTSS

図 2: 同形な 2 つのグラフの一例. 辺を適切に移動することにより, 左図から右図が得られることを各自が確認してみるとよい.
る際には扱いやすいもの (調べたい関係性が見やすいもの) を選ぶことが肝要である. 後にみるが, より数学的には 2 つのグラフ A, B が同形か否かは, 同形写像と呼ばれる A の点と B の点の間の一対一対応が存在するか否かで判定される2 .
※グラフの表現には図 2 のような点と線による描画の他に, 隣接行列, 接続行列等の行列を用いることもできる. この表現法は計算機上でグラフを扱うためには有用である. これらの行列に関する詳細は次回以降に見て行くことになる.

1.2

様々なグラフとその例

全てのグラフはその幾何学的な性質の違いからグループに分類され, それぞれのグループには名前が付けられている. ここでは, その中のいくつかを概観する.

1.2.1

多重辺, ループ, 単純グラフ・・任意の 2 点 P,Q を 2 本以上の辺 が結んでいる場合, それを多重辺と☆ 多重辺 (multiple edges) ・QPTRS

図 3: この図において, 辺 TS, QS は多重辺であり, 点 P には一つのループがある.
呼ぶ.
☆ ループ (loop) ・・・任意の点 P から P 自身へ戻る辺
2 同形な 2 つのグラフに同じ値が与えられるものをグラフの不変量と呼び, 点数や変数はこの不変量の一つである.

ここは 3 ページ目

グラフ理論 2007 #1

北海道大学 大学院情報科学研究科 井上純一

⇒ 単純グラフ (simple graph) ・・・多重辺やループを含まないグラフ

1.2.2

有向グラフ

・・辺に向きが与えられたグラフ☆ 有向グラフ (directed graph : digraph と呼ばれることが多い) ・QPTRS

図 4: 有向グラフの一例. 各辺に向きを持たせることにより, 任意の 2 点間の関係性 (例えば, P は Q に好意を持っている等) を明示させることができる.
☆ 歩道 (walk) ・・・連結した辺の列.
☆ 道 (path) ・・・どの点も高々一度しか現れない歩道.
☆ 閉路 (cycle) ・・・図 2 の右側の Q → S → T → Q のような道.
※ 有向グラフを用いた例としては例題 1.1 の 2 を参照.

1.2.3

連結グラフと非連結グラフ「全部つながっているか」「つながってないか」でグラフを分類することもできる.

PQTUSRV

図 5: 非連結グラフの一例. 成分数は 2 である.
☆ 連結グラフ (connected graph) ・・・どの 2 つの点も道で結ばれているグラフ.
☆ 非連結グラフ (disconnected graph) ・・・連結グラフではないグラフ (図 5 参照).
※ 非連結グラフを構成する各連結グラフを成分 (component) と呼ぶ. 図 5 の例でみるならば, 「この非連結グラフは 2 つの成分を持つ」ということになる.

ここは 4 ページ目

グラフ理論 2007 #1

1.2.4

北海道大学 大学院情報科学研究科 井上純一

オイラー・グラフとハミルトン・グラフ

グラフにはその考案者の名前が付けられたものも多い. ここに出てくる 2 つのグラフ : オイラー・グラフ, ハミルトン・グラフはそれらの中で最も有名なものである.
P

(1)

Q

P

Q

(1)

(2)
(2)
(6)
(5)

R

(5)

(7)

R

(3)

T

(4)

S

(3)

T

(4)

S

図 6: この図はハミルトン・グラフではあるが (左図), オイラー・グラフではない (右図).
☆ オイラー・グラフ (Eulerian graph)・・・全ての辺をちょうど 1 回ずつ通って出発点に戻る歩道を含むグラフ.
☆ ハミルトン・グラフ (Hamiltonian graph)・・・全ての点をちょうど 1 回ずつ通って出発点に戻る歩道を含むグラフ.
※ 連結グラフの点の数が多い場合, そのグラフがオイラー・グラフか, ハミルトン・グラフであるか, を実際に該当する歩道を見つけることによって判定するのは容易なことではない. このようなとき, 与えられた連結グラフがオイラー・グラフであるための条件, ハミルトン・グラフであるための条件 (これは十分条件)が知られており, それぞれ Euler (オイラー) の定理, Ore (オーレ) の定理としてまとめられている. これらを用いることにより, 与えられた連結グラフのオイラー性, ハミルトン性を判定することができるようになる. これらは後に詳しく学ぶ3 .

1.2.5

木

図 7: 木の一例.
☆ 木 (tree) ・・・どの 2 点の間にも道が 1 本しかない連結グラフ (図 7 参照).
※ ワークステーションのファイルシステム, 生物進化の系統図などは木構造を持つ.

3 オイラー閉路の問題はケーニヒスベルグ (現カーニングラード) の街にある橋を 1 回ずつ通ってもとにもどる問題を数学者オイラーが考えたことに由来するらしい. カーニングラードはポーランドに近い東欧のロシア領らしいが, せっかくグラフ理論で学んだわけだから, 実際にどのような橋の配置だったのかを確かめに現地を一度訪れてみたいような気もしてくる.

ここは 5 ページ目

グラフ理論 2007 #1

北海道大学 大学院情報科学研究科 井上純一'$

例題 1.1(2004 年度 演習問題 1 )1. 化学式 C5 H12 を持つ分子にはいくつかの構造の異なる分子が存在する (「構造異性体」). これらの分子を全て挙げ, 図 (CH4 ) に従って, それぞれに対応するグラフを描け.
HHHCH

2. John は Joan が好きで, Jean は Jane が好きで, Joe は Jean と Joan が好きで, Jean と Joan は互いに好きである. John, Joan, Jean, Jane 及び Joe の間の関係を説明する有向グラフを描け.
3. a,b,c,d,e,f の 6 チームでホッケーの試合をすることになった. 各チームの行った試合数は
チーム名

abcdef

試合数224431であった. このとき, 考え得る試合の組み合わせをグラフで表し, それらを全て描け. ただし,同一カードは 2 試合以上行わないものとする.
&%(解答例) :
1. グラフ理論的にこの問題を言い換えてみると, 問題である『Cn H2n+2 の構造異性体の数を数える』ことは, 『n 個の点の次数が 4 であり, 残りの 2n + 2 個の点の次数が 1 である「ラベルなし木」の総数を数える』ということになる.
炭素原子同士のつなげ方を決めれば, 水素原子の配置の仕方は自動的に決まるので, 可能な炭素原子の配置を数えあげて行けばよい. 図 8(左) にその結果を載せる.

AAHHccccc

H

H

H

HcccccH

H

H

H

HHCCBc

Bccc

H

Hccc

Hcccc

H

H

Hc

HcHc

H

Hcccc

H

H

H
H

Hc
H

H

Hc

H
H

H

H

H

H

図 8: n = 5 の場合に可能な炭素原子配列 (左). なお, A は「ペンタン」, B は「2-2-ジメチルプロパン」, C は「2-メチルブタン」と呼ばれる有機化合物である. また, 右図は C5 H12 の構造異性体.
従って, 求める構造異性体は上記の炭素原子の残りの手に水素原子を付加すればよく, 答えは下の図

ここは 6 ページ目

グラフ理論 2007 #1

北海道大学 大学院情報科学研究科 井上純一

8(右) のようになる.
※ 注 : 求めるグラフは「木」でなければならない (つまり, どの 2 点間にも道が 2 本以上存在してはならない) ので, 図 9 のような配置は許されず, 実際, この炭素配列で水素原子も並べてみると C5 H10となり, C5 H12 とは異なるものが出来上がってしまう. 4HHHcHccHHcHcHHH

図 9: C5 H10 .

2. 求める有向グラフは (好意を持っている人物) → (好意を持たれている人物) のように矢印をつける約束にすると図 10(左) のようになる.
bafecbbJaneJeanedacfcdJohnafbeafecddJoanbacJoefed

図 10: John, Joan, Jean, Jane 及び Joe の関係図 (左). 考え得る対戦カードを表す 5 種類のグラフ (右).

3. 考え得る組み合わせのグラフは図 10(右) のように 5 通りある.
'

例題 1.2$(2005 年度 演習問題 1 )(1) 点 の 集 合 が V={v1 , v2 , v3 , v4 , v5 , v6 } で 与 え ら れ,か つ,辺の集合が E={v1 v3 , v2 v3 , v3 v4 , v4 v1 , v4 v3 , v5 v6 } からなるグラフを描け.
(2) ヘビはカエルを食べ, トリはクモを食べる. トリとクモはどちらも虫を食べる. カエルはカタツムリ, クモ, および, 虫を食べる. この捕食行動を表す有向グラフを描け.
&%

(解答例)
簡単なので結果だけ描く.
(1) 単純グラフとは明示されていないので, 図 11 (左) のような多重辺を含む非連結なグラフとなる.
4 系統的な木の数え上げに関しては第 4 章 p. 67 Cayley (ケイリー) の定理で学ぶことになります.

ここは 7 ページ目グラフ理論 2007 #1

北海道大学 大学院情報科学研究科 井上純一

v1v3v2sv4fisnv5spv6b

図 11: 多重辺のある成分を含む, 非連結グラフ (左). 捕食関係を表す有向グラフ (右).

(2) 名前を s(へび), f(カエル), sn(カタツムリ), sp(クモ), b(トリ), i(虫) とし, (食べるもの) → (食べられるもの) のように矢印を描く約束にすれば, 図 11 (右) のようになる.

'

例題 1.3$(2006 年度 演習問題 1 )以下の問いに答えよ.

(1) 身の回りの事柄で, それが「木」のグラフで表現できるものを一つ挙げよ.
(※ ただし, 講義で取り上げたワークステーションのファイルシステム, 生物進化の系統図, 有機化合物の構造以外を選ぶこと)(2) どの辺の 2 つの端点も異なる集合 (グループ) に属するように n 個の点を 2 分割するようなグラフを 2 部グラフと呼んでいる. このとき, n = 7 である 2 部グラフを描き, そのグラフが奇数本の辺からなる閉路を含まないことを示せ.

(※実はグラフに奇数本の辺からなる閉路が含まれないことが 2 部グラフであるための必要十分条件となっているのであるが, この証明は後に詳しく見て行くことにする. ここでは, 具体的に上記の事実を n = 7 の 2 部グラフに対して示すだけでよい.)
&%

(解答例)
(1) 木の構造を持つものであれば何でも良いが, 例えばトーナメント形式の対戦カードの表などは木である.
(2) 例えば n = 7 の二部グラフは図 12 のようになる. 従って, このグラフの中に現れる閉路 : 3 → 5 → 4→ 6 → 3 を見ると確かに偶数本の辺からなり, 奇数本の辺ではない. 一般的に言って, 二部グラフはその定義より, 一つの点から出発し (これを group A としょう), 様々な経路を経て自分自身に戻ってくることができ, 閉路ができたとするならば, 必ず A → B → · · · B → A のような経路をたどるはずであり, 従って, この中に含まれる辺の個数 (ここで書いたところの → の個数) は必ず偶数本であり, 奇数本であることはありえない.

演習問題 1(1) 身の回りでオイラー・グラフ, ハミルトン・グラフの性質をうまく使っている実例をそれぞれ挙げよ.
(2) 点集合 V と辺集合 E がそれぞれ,V={v1 , v2 , v3 , v4 , v5 }ここは 8 ページ目

グラフ理論 2007 #1

北海道大学 大学院情報科学研究科 井上純一

A group
4123B group657

図 12: 7 個の点からなる二部グラフの例. 全ての点は group A か group B のいずれかに所属し, お互い異なるグループに属する点どうしがが辺で結ばれる. .

E={v1 v2 , v2 v3 , v3 v4 , v4 v5 , v5 v1 , v1 v3 , v3 v5 , v5 v2 , v2 v4 , v4 v1 }で与えられるグラフの概形を描け. また, このグラフの持つ特徴を考察し, それらのうち 2 つを挙げよ.

(注 1) 締め切りは次回の講義開始前. レポート用紙には氏名, 学籍番号を必ず書くこと.
(注 2) レポートは次回に返却できない場合があります. 自分の作成したレポートをそれ以後 (レポートが返却されるまで) の自習に使う者は, 必ずレポートのコピーをとってから提出してください.
各回のレポートの提出状況は

http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/graph2007/report2007.html
から確認できる.

ここは 9 ページ目