分枝限定法データ構造
• 初期値G=∞，Z＝∞
– A｛P0｝，N｛P0｝，O＝φ – X[0]={#,#,#,#, G, Z}• 節点０
– Aリスト｛P0｝ – Nリスト｛P0｝ – P0＝S・・・アクセス済み – O ＝φ – X[0]={#,#,#,#, -10, Z} – P0を分枝節点１
s # #
– Aリスト｛P0, P1, P2｝ – Nリスト｛P0, P1, P2｝ – O ＝φ – X[0]={#,#,#,#, -10, Z} – X[1]=｛1,0,#,#, G, Z} – X[2]=｛1,1,#,#, G, Z}最適解が一個の場合
A:既に生成されているがまだ分解も終端もされていない部分問題の集合 N:既に生成されている部分問題の集合．
ｚ：最適値の暫定値 O:最適解の集合
Step1初期設定： A={P0}, N={P0}, z=∞, および，O=∅（空集合）． Step2探索処理： A=∅ならStep9へ，A≠∅ならPi=s(A)としてStep3へ． Step3暫定値更新：ｘ∈Sかつｆ（ｘ）＜ｚの解ｘがあれば，ｚ＝ｆ（ｘ），O={x}としStep4へ． Step4緩和問題によるテスト：次のいづれかが成り立てば，Step8へ，それ以外はStep5へ ． （１）Piの緩和問題P~iが許容解を持たない． （２）ｇ（Pi）=f(Pi)，すなわち，P~iの最適値がPiの最適値に一致する． Step5下界値テスト：ｇ（ｘ）≧ｚが成立すれば，Step8へ，それ以外はStep6へ． Step6優越テスト：Piより優越するPjが既にあれば，Step8へ，それ以外はStep７へ Step7分枝処理：Piの子節点Pi1,Pi2,....Pinを作り， A = A∪｛Pi1,Pi2,....Pin｝－｛Pi｝，N = N∪｛Pi1,Pi2,....Pin｝としてStep2へ． Step8部分問題Piの終端処理： A = A-{Pi} としてStep2へ
Step9停止
ｚ = ∞のとき，与えられた問題P0は許容解を持たない． ｚ < ∞のとき，最適値＝ｚ，最適解は，Oに記憶されている．
グラフとネットワークの基礎
（組み合わせ最適化問題の数学的バックグラウンド）• 1736年に数学者オイラーが解法を示し
たのが学問の始まり．
• 参考書：グラフ理論入門，R.J.ウィル
ソン著，齋藤・西関訳，近代科学社
• グラフ
–
頂点，節点
(Vertex) V
–
辺，枝
(Edge) E
–
グラフ
G = (V, E)
グラフとは？
定義 辺eが点対(u,v)のとき 辺eはuとvを結ぶ(joint) 辺eはuおよびvに接続する(incident) uおよびvは辺eの端点(end)と呼ばれる u=vなる辺はループ(loop)と呼ばれる 同じ点対の辺は多重辺(multiple edge)と 呼ばれる 辺に向きがないグラフを無向グラフ (undirected graph) 辺に向きがあるグラフを有向グラフ (directed graph) 単純グラフ 多重グラフ 有向グラフ 無向グラフhttp://coolee.at.infoseek.co.jp/graphtheory.html#1
グラフの例
グラフの種類と応用例
• ネットワーク
– 最大流量問題（ネットワークフロー）• ツリー（根付き木）
– 巡回セールスマン問題 – 最短路問題 – 最大流量問題• 2部グラフ
– 分類問題グラフの定義
• 互いに素（ = 交わらない ）な有限集合 V ，E と写像 μ：E → P(V) に 対して， ペア G = (V, E) = (V, E; μ) を グラフ Gと定義する．ここで P(V) は V のベキ集合である．
•V={v1, v2, v3, v4}
•E={e1, e2, e3, e4, e5, e6} •μ(e1)={v1, v2} •μ(e2)={v1, v2} •μ(e3)={v2, v3} •μ(e4)={v3, v4} •μ(e5)={v4, v1} •μ(e6)={v2, v2} •V の要素: 頂点（vertex） もしくは 点、 •E の要素: 辺（edge） •V (G): G の 頂点集合 •E (G): G の 辺集合 •μ : 接合写像 •|V(G)| = p ，|E(G)| = q のとき (p, q) グラフ e1 e3 e4 e5 v4 v2 v3 v1 e2 e6 Vのべき集合
グラフの用語１（単純グラフ）
• 端点：辺 e の両端の点といい，端点は e に接合している • 隣接：辺と辺がある頂点を共有している とき、その辺同士 • ループ（自己ループ）：ある辺の両端点 が等しいとき • 多重辺：2 頂点間に複数の辺があるとき • 単純グラフ：ループも多重辺も含まない グラフ • 重み付きグラフ：辺に重み（コスト）を付 与したグラフ 出典: フリー百科事典『ウィキペディア (Wikipedia)』 10 5 5 20 μ(e6)={v2, v2} μ(e1)={v1, v2} •μ(e1)={v1, v2} •μ(e2)={v1, v2} W(e1)={v1, v2, w} ループ|μ(e)| = 1 リンク|μ(e)| = 2グラフの用語２（部分グラフ）
• G‘ は G の部分グラフ： G’ の頂点集合と辺集合が共に G の頂点集 合と辺集合の部分集合になっているとき（逆：拡大グラフ） • 全域部分グラフ（生成部分グラフ・因子）：頂点集合が等しい部分グラ フ • 誘導部分グラフ： G の頂点集合 V の部分集合 S を取り出して、両端 点が S に属する全ての辺を辺集合とする G の部分グラフ • 縮約グラフ（商グラフ）： グラフ G からある辺を取り除き、その辺の両 端点を一つの頂点に縮約したときG ⊂ G’
部分グラフ 拡大グラフ 縮約グラフ 誘導部分グラフ 辺の除去グラフの用語３（正則グラフ）
• 次数： 頂点 v に接続する枝
の数
d(v) （入次数，出次数）
• k-正則： すべての v について、
d(v) = k が成り立つとき
• 正則グラフ： ある k について
k-正則なグラフ
• δ(G)： グラフ G 中の最小次
数の頂点の次数
• Δ(G)最大次数の頂点の次数
• 孤立点： 次数 0 の頂点
{d(v)}
d(v) = 3
∀v ∈V
正則グラフ
グラフの用語４（閉路）
• 歩道（鎖）： 隣接している頂点同士をたどった v
1, e
1, v
2,
e
2, ..., e
n-1, v
nの系列
• 路（小径）： 辺の重複を許さない場合
• 道： 頂点の重複も許さない場合
• 閉路（回路・サイクル）： 始点と終点が同じ路
• 完全グラフ（完備グラフ）： 任意の 2 頂点間に枝がある
グラフ
• クリーク： 完全グラフになる誘導部分グラフ
• サイズ n のクリークを含むグラフは「n-クリークである」と言う。辺を持つグラ フは必ず 2 頂点の完全グラフを含むので 2-クリークである。また n-クリーク であって、直径が n 未満となるグラフを n-クランと言う。木の性質
• グラフにおいて，単連結で閉路を持たないグラフ （単連結とは，辺を削除すると2つに分かれてしまうグラフ） 4つの主な性質（定理）がある。 • １．（T の辺の個数）=（T の節点の個数）- 1 ||T|| = |T| - 1 • ２．任意の2点 x,y に対して、x,y を結ぶただ一つの道がある。 • ３．T の2点を結ぶ T に含まれない辺 e に対して、T+e には e を通るた だ一つの閉路があり、この閉路上の任意の辺 f に対して T+e-f は木と なる。 • ４．少なくとも2個の端末点がある。また、端末点とは次数1の点である。2部グラフ（分類，クラスタリング）
• ２部グラフ： グラフGのうち、V(G)を二つの頂点集合に分割して各集合 内の頂点同士に枝が無いように分割できるグラフ • n部グラフ： n個の頂点集合に分割可能なグラフ • 完全2部グラフ： 二つの頂点集合V1, V2に分割したとき、V1同士・V2同 士の頂点間には辺が存在しないが、V1とV2間の任意の2点間に辺が存 在するグラフのことである。m頂点の頂点集合とn頂点の頂点集合でで きているとき、 Km, nとかく。 n部グラフ直径の定義
• 径（けい、diameter）あるいは直径（ちょっけい）とは、図形の差し渡し の長さのことである。 • グラフ理論でいう直径とは、グラフ上の任意の 2 頂点間の距離の最 大値 • 一般に、任意の距離空間の部分集合（つまり図形）に対して、その集 合に含まれる二点の距離の上限として直径を考えることができる（上 限が存在しないときには直径は無限大とする）。つまり、d(x, y) で二 点 x, y の距離を表すとき、集合 S の直径 diam S は • で与えられる。直径が有限な値を持つとき、その集合は有界であると いわれる。ユークリッド空間の部分集合の場合、有界の定義は原点 を中心とする十分大きな球にその集合が含まれることであるとしても 同じことになる。同型グラフ
• GとG'が同一の頂点を持ち、同一の辺のつながりかたをしているとき、 「同型」という • ２つのグラフ G と H が 等しい G = H とは V(G) = V(H)，E(G) = E(H)，μG = μH のときで、 • 同型 G ～ H の定義 全単射 θ：V(G)→V(H)， χ ：E(G)→E(H) が 存在して，μG(e) = {u , v} ⇔ μH(χ(e)) = {θ(u) , θ(v)} となるとき，連結グラフ
• 連結グラフ： グラフ上の任意の2頂点間に路が存在するグラフ （極大で連結な部分グラフは、連結成分） • 有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路 が存在すること（極大で強連結な部分グラフは、強連結成分） • 切断点または関節点：連結なグラフGから、ある頂点を取り除くと、G が非連結になるとき、その頂点 • 切断辺または 橋：Gから、ある辺を取り除くと、Gが非連結になるとき、 その辺 • グラフがどの程度、かたく結びついているかを示す尺度として、点連 結度（あるいは単に連結度）と辺連結度がある。k連結グラフは、点 連結度がk以上のグラフのことを指す。 連結グラフ 非連結グラフ平面グラフ
• 平面グラフ (plane graph) ： 平面上の頂点集合とそれを
交差なく結ぶ辺集合からなるグラフ
グ ラ フ 理 論
• グラフの基本的性質
• グラフの探索
• ダイクストラ法
グラフの基本的な性質（復習）
• グラフの全ての点の次数を合計すると偶数に
なる（握手問題，オイラー）
• 奇数次の点は偶数個ある
例題：パズル問題
グラフ理論を用いた問題解決（急性精神病）
• 4個の立方体の積み木問
題
• 立方体は4色に塗り分けら
れている．
• これらの立方体を積み上
げて四角柱を作る
• 四角柱の側面それぞれに
4色全部が現れるような積
み方を求める問題
➀ ➁ ➂ ➃表裏の色の関係をグラフ化する
➀ ➁
グラフを重ね合わせる
部分グラフ をとると 前後 左右 前後・左右 それぞれす べての色を 持つことが できる演習問題
１．グラフ
G(V, E) について。次の問に答えよ。ただし，V
= {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F},
{C,F}, {D,E}} である。
(1) 頂点 A と C の距離 d(A, C) はいくらか。
(2) このグラフの直径を求めよ。
(3) このグラフに切断点はあるか。もしあればすべての切
断点を列挙せよ。なければ『なし』と答えよ。
北海道大学 複雑系工学 講座（井上純一先生作成）解答
１．グラフ G(V, E) について。次の問に答えよ。ただし，V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} である。
(1) 頂点 A と C の距離 d(A, C) はいくらか。 【解答】 d(A, C) は，頂点 A から C への最短の道の長さである。そのような最短道は，頂点 の列 (A, B, F, C) で表され，この道には３つの辺が含まれているので，d(A, C) = 3 で ある。 (2) このグラフの直径を求めよ。 【解答】 直径は，このグラフ上の任意の２頂点間の距離の最大値である。最も距離が大きく なる２頂点の片方は頂点 C となることは分かる。頂点 C から他の頂点への距離を調 べると，d(C, D) = 4 が最大となる。よって，このグラフの直径は 4 である。 (3) このグラフに切断点はあるか。もしあればすべての切断点を列挙せよ。なければ 『なし』と答えよ。 【解答】 切断点はB と F の２つ。C は切断点ではないことに注意せよ。 A B E C D F
オイラー路
（数学者レオンハルト・オイラー（スイス・バーゼル）） • オイラー路：グラフの全ての辺を1度だけ通る路 • オイラー閉路：全ての辺を1度だけ通る閉路 • オイラーグラフ：オイラー閉路を含むグラフ • 準オイラーグラフ：オイラー閉路は持たないがオ イラー路を持つグラフ 性質 • オイラーグラフと準オイラーグラフは、一筆書き 可能である。 • オイラーグラフ⇔全ての頂点の次数が偶数のグ ラフ • 準オイラーグラフ⇔奇数の次数の頂点を二つだ け含むグラフ • 参考：オイラーの等式，オイラーマクローリン展開，変分法，一巡閉路 オイラーグラフ 準オイラーグラフオイラー路の判定法
条件
1）有限グラフ(辺の数も頂点の数も）で連結(connected)なグ
ラフに限定．
において，
１）始点終点以外の全ての頂点において，入ってくる辺の数と出
て行く辺の数が同じはずなので，その頂点の次数は偶数
２）始点と終点は次数が奇数である
(出発のときの出るだけの辺
が一つ半端だから．終点についても同様）
オイラー路の存在条件： １），２）
オイラー閉路の存在条件：全ての頂点が偶数の次数をもつこと．
オイラー路（例題）
例題
V={A,B,C,D,E,F,G}, E={s,t,u,v,w,x,y,r}, T(s)={A,E}, T(t)={E,B}, T(u)={B,C}, T(v)={C,F}, T(w)={F,D}, T(x)={A,D}, T(y)={E,F}, T(z)={E,G}, T(r)={G,F},のときオイラー回路は存在するか。 答え ： E,F の次数は４，他は２。全て偶数 なのでオイラー回路が存在する． アルゴリズム1 （枚挙法） Step1 始点を選ぶ Step2 Sからｔまでを並べ替える （M！通り） Step3 閉路になるかどうか調べる アルゴリズム２ （グラフ理論の応用） Step1 点の次数が偶数か奇数か？ Step2 調べていない点があればS1へ （M通り）
ハミルトン路
（ウィリアム・ローワン・ハミルトン（英国））• ハミルトン路：グラフ上の全ての
頂点
を
1 度だけずつ通る
路
• ハミルトン閉路：グラフ上の全ての頂点を 1 度だけずつ通
る閉路
• ハミルトングラフ：ハミルトン閉路を含むグラフ
• 準ハミルトングラフ：ハミルトングラフではないがハミルトン
路を含むグラフ
• 与えられたグラフがハミルトン路を含むかどうか判定する
問題は、
NP困難。
ハミルトングラフの性質１
1.
|V(G)| ≥ 3、δ(G) ≥ |V(G)|/2 を満たす単純グラフ G は、
ハミルトングラフ
(Dirac, 1952年)
最低次数 δ
(G)
頂点の数
|V(G)|
単純グラフ
G
ハミルトングラフの性質２
1.
グラフ
G (|V(G)| ≥ 3) がハミルトングラフ ⇔ d(u) + d(v)
≥
V(G) を満たす隣接していない頂点 u, v について、G
+ (u, v) がハミルトングラフ
2.
グラフ
G (|V(G)| ≥ 3) がハミルトングラフで、(u, v) ∈
E(G) かつ d(u) + d(v) ≥ n + 2 ならば、G - e もハミルトン
グラフ。
G
d(u) + d(v)
(u, v)
ハミルトングラフの性質３
1.
完全グラフ
K
2n+1は、
n 個のハミルトン閉路に分解でき
る。
2.
完全グラフ
K
2nは、
n-1 個のハミルトン閉路と 1 個の
1-正則な全域部分グラフに分解できる。
K
５K
６ 1-正則な全域部分グラフ演習問題（つづき１）
グラフ
V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E},
{B,F}, {C,F}, {D,E}}
(4) このグラフはオイラーグラフか？ また，ハミルトングラフ
か？
(5) このグラフは２部グラフか？
(6) このグラフから何本かの辺を除去して木にするには，何本
を除去すればよいか。
解答
グラフ V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} (4) このグラフはオイラーグラフか？ また，ハミルトングラフか？ 次数が奇数である頂点（奇頂点という）が B と C の２個あるので，オイラーグラフでは ない。（周回可能小道はあるが，閉じていないのでオイラー小道ではない。） また，頂点 C は次数が１であるので C を通るような閉路（閉じた道なので，その通り 道の次数は２以上でないといけない）は存在しない。従って，ハミルトン閉路は存在し ない。つまりハミルトングラフでもない。 ［頂点 C を通る閉路がないのだから，もちろんオイラー小道がないということもでき る。］ (5) このグラフは２部グラフか？ 【解答】 ２部グラフである。頂点 A，E および F を左側に書き，残りの頂点を右側に書けば， すべての辺は左側の頂点と右側の頂点を結ぶことになる。 (6) このグラフから何本かの辺を除去して木にするには，何本を除去すればよいか。 【解答】 １本を除去すれば木になる。ただし，辺 {A,B}，{B,C}，{C,D} または {D,A} のいず れかを除去すると木になるが，これ以外の辺を除去しても木にはならない。つまり，こ のグラフに閉路がなくなるように辺を除去しなくてはならない。 A B E C D F
隣 接 行 列
• 隣接行列
：隣接関係を表す行列
• n 頂点のグラフGに対して，
A(G) = a
11a
12・ ・ ・
a
1na
21a
22・ ・ ・
a
2n...
a
n1a
n2・ ・ ・
a
nn• 頂点vi から頂点vj への辺が
ある
⇒
a
ij= 1
• 頂点vi から頂点vj への辺が
ない
⇒
a
ij= 0
• 無向グラフ
⇒
a
ij= a
ji行の和
= 次数
根つき木の探索法
• 節点vから枝分かれする点の集合T(v)
• 0) A = {v
0，v
１，v
2・・・
v
ｎ}, B = {v
0}
• 1) ※Aから一つの成分vを取り出し，T(v)の中でBに入っ
ていないものを
AとBに入れる．
• 2) Aが空なら終了
• そうでなければ1)へ
– ※ 先にいれたものを先に取り出す … キュー（queue） – 後にいれたものを先に取り出す … スタック（stack） 幅優先探索 キュー 深さ優先探索 スタック 評価値優先v
0最短路問題
• 長さつきネットワークG=(E,V,W)
1 2 3 4 5 s 50 80 20 15 15 30 s → t への最短路 例 •自宅の最寄り駅から四ッ谷駅ま での鉄道の最短時間(もしくは最 安)ルートを求める(駅ナビなど） •カーナビを使って現在地から目的 地までの最短経路を調べる •一般的な解法 •動的計画法DP •分枝限定法 •ダイクストラ法ダイクストラ法
（Dijkstra Method）
最短経路問題は，やさしい部類の問題であり，全経路を調
べることなく効率的に最短経路が求められるアルゴリズム
が存在する．
ダイクストラ法の特徴
• 出発点を１つに固定して、そこから他のすべての頂点
への最短路を求める方法
• 出発点に近い頂点への最短経路を次々に求める方法
ダイクストラ法の手順
1. 出発点に隣接する頂点の、出 発点-頂点間の距離を求め、最 小の値をもつ頂点にマークを付 けて確定する 2. マークのついた頂点に隣接する 頂点までの距離を求め、この時 点で計算されている頂点（マー クの付いていない）の距離の中 で最小の値をもつ頂点をマーク して確定する 3. 以上の操作をすべての頂点に マークがつくまで繰り返すと、各 頂点に得られる値が出発点か らの最短路となる 1 2 3 4 5 s 50 80 20 15 15 30 ∞→50 ∞→80→70 ∞→65 ∞→95 →85 V={1, 2, 3, 4, 5} : 頂点集合 N={∞, 50, ∞, 80 , ∞ | ：隣接行列 ∞, ∞, 15, 20, ∞ | ∞, ∞, ∞ , 30, 15| ∞, ∞, ∞, ∞, 50| ∞, ∞, ∞, ∞, ∞}ダイクストラ法のアルゴリズム
0) d(s) = 0, d(i) = ∞ （i ≠ s） 1) A = Vならば終了 そうでなければ,
A
=
φ
A V
=
{
}
( ) min
( ) |
d v
=
d i i A
∈
{ }
{ }
A A
v
A A
v
=
= −
∪
( )
T v
∩
A
2) の節点jに対し d(j) > d(v) + avjならば d(j) = d(v) + avj p(j) = v 1) へ iからjへの長さ aij≧0 d(i)：sからiへの最短長さの上限 p(i)：iへの最短路へのポインタ T(v)：vから出る節点の集合手続き
(Procedure)
http://www.me.sophia.ac.jp/or/lab/ishizuka/OC/spath_00.html演習問題（つづき２）
２．グラフ G が与えられているとする。G の補グラフ G‘ は，G と同じ頂点 集合をもち，G において２頂点 u と v の間に辺が存在しないとき， かつそのときに限り，G’ において u と v の間に辺が存在するように してできるグラフである。次の問に答えよ。 (1) グラフ G(V, E) の補グラフ G‘ を書け。ただし，V = {A, B, C, D, E}, E = {{A,C}, {B,D}, {B,E}, {C,D}, {D,E}} である。（このグラフを図 に描いてから考えてください。） (2) 上のグラフ G の隣接行列 A およびその補グラフ G' の隣接行列 A' を完成せよ。 (3) 頂点数４のグラフ G で，G と G‘ が同形であるようなグラフを書け。 (4) 頂点数８のグラフ G で，G と G' が同形であるとすれば，このグラフ G には辺が何本あるか。解答
２．グラフ G が与えられているとする。G の補グラフ G‘ は，G と同じ頂点集合をもち，G において２頂点 u と v の間に辺が存在しないとき，かつそのときに限り，G’ において u と v の間に辺が存在す るようにしてできるグラフである。次の問に答えよ。
(1) グラフG(V, E) の補グラフ G‘ を書け。ただし，V = {A, B, C, D, E}, E = {{A,C}, {B,D}, {B,E}, {C,D}, {D,E}} である。（このグラフを図に描いてから考えてください。）
【解答】
補グラフ G’ の辺集合 E‘ は E’ = {{A,B}, {A,D}, {A,E}, {B,C}, {C,E}} となる。 (2) 上のグラフG の隣接行列 A およびその補グラフ G' の隣接行列 A' を完成せよ。 【解答】... 行列は，いつものように書く。 A = [ 0 0 1 0 0 | 0 0 0 1 1 | 1 0 0 1 0 | 0 1 1 0 1 | 0 1 0 1 0 ] A' = [ 0 1 0 1 1 | 1 0 1 0 0 | 0 1 0 0 1 | 1 0 0 0 0 | 1 0 1 0 0 ] (3) 頂点数４のグラフ G で，G と G‘ が同形であるようなグラフを書け。 【解答】 長さ３の道。（図5-26 の (d) のグラフ） 『練習問題：頂点数５のグラフ G で，G と G’ が同形であるようなグラフは２種類ある。考えてみ よ。また，頂点数６や７の場合はどうかも考えよ。』 (4) 頂点数８のグラフ G で，G と G' が同形であるとすれば，このグラフ G には辺が何本あるか。 【解答】 辺が n 本あるとすると，G' にも n 本ある。これらの和 2n は頂点数８の完全グラフの辺の本数 8×(8－1)／2 = 28 に等しい。すなわち，2n = 28 であるから，n = 14 である。
