SAS2006 第1回 グラフ理論 担当：IPUSIRON 2018/11/29

使用する資料 グラフ理論　配布資料　#1 （http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/graph2006/GraphTheory06_1.pdf） 2018/11/29

グラフ理論と関連すること ネットワーク理論 プログラミング 暗号理論 最適化問題 組合せ理論 ゲーム理論 化学 2018/11/29 ・ネットワークは、コンピュータを頂点、回線を辺とするグラフと考えられる。そして、その性能はグラフ理論の不変量を用いて計算できる。 ・データ構造とアルゴリズムを論ずる際の基本的道具になる。 ・ゼロ知識証明の知識として、グラフの3色問題の解を知っていることを使える。 ・化学の分野として高分子などがある。これをグラフ理論で考えるアプローチもある。 2018/11/29

今日やること グラフとは何か 様々なグラフとその例 点、辺、次数 グラフの意味 多重辺、ループ、単純グラフ 有効グラフ 連結グラフ、非連結グラフ オイラー・グラフ、ハミルトン・グラフ 木 今回はグラフ理論の一番最初の解説なので、言葉の定義が多い。 今後わからない言葉が出てきたら、再び戻って意味を確かめてから読むようにするとよい。 2018/11/29

1.1　グラフとは何か 2018/11/29

グラフとは？ 点と辺から成り立つ図形のこと 棒グラフや円グラフとはまったく関係ない 2018/11/29

点と辺 点（vertex） 辺（edge） P,Q,R,S,T 点Pを含む辺 点Rを含む辺 2018/11/29 黒丸（点）のところだけが繋がっているのであり、PSとQTが交わっているように見えるところは実際には交わっていない。 2018/11/29

次数 次数（degree） ある点を端点とする辺の本数 例：点Pの次数は3 例：点Rの次数は2 deg(P)=3 deg(R)=2 2018/11/29

グラフに意味を持たせる 例えば、点P,Q,R,T,Sをフットボールのチーム名とする。 このとき、deg(P)=3といえば、チーム名Pは3回試合を行うと意味を持たせることができる。 同様にして、電気回路、ネットワーク経路などをグラフで意味を持たせることができる。 2018/11/29

グラフの同形性 同形とは同じグラフであることを意味する。 グラフとは点とその結び方（辺）の表現であり、辺の距離などは関係がない。 不変量 同形な2つのグラフにそれぞれ同じ値が与えられるもののこと。 例：点の数、辺の数などが不変量のひとつである。 2018/11/29

様々なグラフとその例 2018/11/29

多重辺、ループ 多重辺（multiple edges） ループ（loop） 単純グラフ（simple graph） 2点間で、2本以上の辺が結んでいる場合、それを多重辺と呼ぶ。 例：点Qと点Sの間の辺であるQSは2本ある。これは多重辺である。 ループ（loop） 同じ点に戻る辺のこと。 例：点Rにはひとつループがある。 単純グラフ（simple graph） 多重辺やループを含まないグラフのこと。 2018/11/29

有向グラフ 有向グラフ（directed graph,digraph） 歩道（walk） 道（path） 閉路（cycle） 辺に向きがあるグラフ。 歩道（walk） 連結した辺の列。 上の例：P→S→Rというように連結された辺の列が歩道。 道（path） どの点も高々一度しか現れない歩道。 下の例：P→R→Q→R→Sという歩道はRが2回現れているから、道ではない。 閉路（cycle） 矢印に従って最終的に戻ってくる道順。 上の例：P→R→T→U→Q→Pという道順は閉路になっている。 別に普通のグラフでも閉路は存在する。 2018/11/29

有効グラフの例（じゃんけん） じゃんけんは有効グラフで現すことができる。 まず、点にそれぞれの登場するものを与える。ここでは、グー、チョキ、パーの3点。 次に、矢印の向きに意味を与える。矢印の先は矢印の元より強いとここでは決めた。 そうすると、右のような有効グラフに表現できる。 2018/11/29

連結グラフと非連結グラフ 連結グラフ（connected graph） 非連結グラフ（disconnected graph） どの2点も道で結ばれているグラフ。 非連結グラフ（disconnected graph） 連結グラフでないグラフ。 成分（component） 非連結グラフを構成する各グラフのこと。 例：右の非連結グラフの成分の数は3である。 2018/11/29

オイラーグラフとハミルトングラフ オイラーグラフ（Eulerian graph） ハミルトングラフ（Hamiltonian graph） すべての辺をちょうど一回ずつ通って出発点に戻る歩道を含むグラフ。 一般の一筆書きの問題は、オイラーグラフの歩道を見つける問題と同じである。 ハミルトングラフ（Hamiltonian graph） すべての点をちょうど一回ずつ通って出発点に戻る歩道を含むグラフ。 例：上はオイラーグラフになっている（P→R→Q→R→S→Q→P）。 また、同時にハミルトングラフにもなっている（P→R→S→Q→P）。 含むというところに注目。 うまく辺あるいは点を一回ずつ通って、出発点に戻って来れる道順（歩道＝道の列）が、ひとつでもあればよいということである。 連結グラフの点の数が少ないときは、すぐにオイラーグラフの歩道やハミルトングラフの歩道をあるかどうか、あるならばどのような道順かということはわかる。 しかしながら、点の数が多いときは、ぱっと見ただけではわからない。グラフ理論では与えられた連結グラフがオイラーグラフである条件やハミルトングラフである条件についての定理がすでに発見されている。これは後で紹介されるはず。 2018/11/29

木 木（tree） どの2点の間にも道が1本しかない連結グラフのこと。 例1：ワークステーションのファイルシステム 例2：生物の進化の系統図 例3：データ構造 2018/11/29

木の例（データ構造1） データ構造の一種である「2分探索木」は木構造になっている。 点を色分けして改良したものも存在する。 詳細 http://sunak2.cs.shinshu-u.ac.jp/~miyao/AL/Class/binary_search_tree.pdf 2018/11/29

木の例（データ構造2） 2018/11/29

例題1.1　問1 問：化学式C5H12を持つ分子はいくつかの構造の異なる分子が存在する（構造異性体）。これらの分子をすべて挙げ、それぞれに対応するグラフを描け。 2018/11/29

問1 解答1 化学の知識（外殻）がなくても、簡単に解ける。 まず、Cという点が5つあるすべてのパターンを考える。すると、次の3パターンしか存在しない。 ただし、点をCと置いた。 2018/11/29

問1 解答2 後は、C（炭素）の周りにH（水素）を配置すればよい。 2018/11/29 問1　解答2 後は、C（炭素）の周りにH（水素）を配置すればよい。 なぜ、こうした配置が可能かどうかは高校化学で習うはず。 2018/11/29

例題1.1　問2 問：JohnはJoanが好きで、JeanはJaneが好きで、JoeはJeanとJoanが好きで、JeanとJoanは互いに好きである。 John,Joan,JeanおよびJoeの間の関係を説明する有効グラフを描け。 2018/11/29

問2 解答1 解：最初から完璧なグラフを書くのは難しいので、ひとつずつ見ていく。 矢印の先端を好きな相手を向くようにする。 ①JohnはJoanが好き。 ②JeanはJaneが好き。 ③JoeはJeanとJoanが好き。 ④JeanとJoanは互いに好き。 2018/11/29

問2 解答2 後はこれらを組み合わせればよい。 2018/11/29

例題1.1　問3 a,b,c,d,e,fの6チームでホッケーの試合をすることになった。 各チームの行った試合数は右の表の通りである。 このとき、考え得る試合の組み合わせをグラフで表し、それらをすべて描け。 ただし、同一カードは2試合以上行わないとする。 チーム名 試合数 a 2 b c 4 d e 3 f 1 2018/11/29

問3 解答1 まず対戦数の多いものから考えるとわかりやすい。 そこで、まずcは4回試合するので、その全パターンを考える。 2018/11/29

問3 解答2 次に、dを考える。これも4回試合する。さきほど示した5パターンに書き加えてみる。 ここで、fは1試合しかしないことを考えると、8パターンになる。 これでc,d,fはクリアした。 2018/11/29

問3 解答3 そして、aを考える。ただし、もうc,dには連結してはならない。 ただし、bは2試合、fは1試合しかしないことを考慮しておく。 2018/11/29

問3 解答4 bを考える。 もうa,c,dには連結はできないとする。 2018/11/29

問3 解答5 fを考える。ピンク色の線。 2018/11/29

問3 解答6 最後にeを考える。 もうe以外のすべてを決定しているので、もう線を繋ぐことはできないので、eが3本でないものパターンは除外する。 2018/11/29

問3 解答7 ゆえに次のパターンが答えになる。 2018/11/29

例題1.2　問1 点の集合が 与えられ、かつ辺の集合が からなるグラフを描け。 2018/11/29

問1 解答1 6つの線を書く。ただし点のvは略する。 2018/11/29

問1 解答2 後はこの線たちを組み合わせて、グラフを描けばよい。 2018/11/29

例題1.2 問2 ヘビはカエルを食べ、トリはクモを食べる。 トリとクモはどちらも虫を食べる。 カエルはカタツムリ、クモ、および虫を食べる。 例題1.2　問2 ヘビはカエルを食べ、トリはクモを食べる。 トリとクモはどちらも虫を食べる。 カエルはカタツムリ、クモ、および虫を食べる。 この捕食行動を表す有向グラフを描け。 2018/11/29

問2 解答1 登場人物は、ヘビ、カエル、トリ、クモ、虫、カタツムリの6種類である。 矢印の先は食べられる側とする。 2018/11/29

問2 解答2 7種類の矢印を組み合わせればよい。 2018/11/29

演習問題1(1) 身の回りの事柄で、それが「木」のグラフで表現できるものをひとつ挙げよ。 ただし、ワークステーションのファイルシステム、生物進化の系統図、有機化学物の構造以外を選ぶこと。 2018/11/29

演習問題1(1)　解答1 DNS（ドメイン名からIPアドレスを探索する仕組み）は木構造である。 2018/11/29

演習問題1(1) 解答2 文の構造は、木構造である。 「Time flies like an arrow.」の木。 2018/11/29 演習問題1(1)　解答2 文の構造は、木構造である。 「Time flies like an arrow.」の木。 文の最後のピリオドはいらない。 2018/11/29

演習問題1(2) どの辺の2つの端点も異なる集合（グループ）に属するようにn個の点を2分割するようなグラフを2部グラフと呼んでいる。 2018/11/29

演習問題1(2) 解答1 2部グラフとは次のように2つの集合にわけられたグラフのことである。 演習問題1(2)　解答1 2部グラフとは次のように2つの集合にわけられたグラフのことである。 ここでは点の数は7個なので、上の7個と下の7個しかない。 ただし、線は下と上しか結びつかない。横（同じグループに属するもの同士）はダメ。 2018/11/29

演習問題1(2) 解答2 閉路を作るように線を結ぶ。 下の点→上の点→下の点→上の点という4つの線が必要。つまり、線の本数は偶数である。 演習問題1(2)　解答2 閉路を作るように線を結ぶ。 下の点→上の点→下の点→上の点という4つの線が必要。つまり、線の本数は偶数である。 奇数にはなることはない。 2018/11/29