内容 • グラフの定義と最大安定集合問題 Section 1.1 pp.2-4 • Euler閉路・Eulerの定理・アルゴリ ズム Section 1.2 pp.4-7 • 最小木問題 Section 1.4 pp.13-18 最大安定集合問題 あなたは日本の首相に任命された。 初仕事として世界の平和のため6人の お友達から何人か選んで一緒に ピクニックに行こうと思っている。 しかし、線で結んである人同士は仲が悪く、彼らが一緒 にピクニックに行くと せっかくの楽しいピクニックが 台無しになってしまう。 なるべくたくさんの仲間でピクニックに行くには誰を誘え ばいいんだろう？ ミッテラン クリントン ゴルビー レーガン カダフィ ベス グラフによる表現 点 クリントン ミッテラン 枝 ゴルビー カダフィ レーガン グラフ ベス 点 （vertex;vertices) ミッテラン ゴルビー カダフィ クリントン 点集合 レーガン ベス 枝(edge) 枝集合 隣接(adjacent) ミッテラン クリントン レーガン ゴルビー カダフィ ベス カダフィとベスは隣接 接続(incident) ミッテラン クリントン レーガン ゴルビー カダフィ ベス それぞれの枝はカダフィに接続 次数(degree) ミッテラン クリントン レーガン ゴルビー カダフィ 次数=4 ベス 安定集合(stable set) ミッテラン クリントン 安定集合（独立集合） ゴルビー カダフィ レーガン ベス ゴルビー，ミッテラン，クリントン，レーガンの４人で ピクニックに行けば喧嘩しない！ 組合せ最適化問題 なるべく大人数 目的関数(objective function) で 仲の悪い人がいないメンバー 解(solution) を探す 有限の組み合わせの中から 目的関数を最大にする解を求める 組合せ最適化問題 (combinatorial optimization problem) 最適解と最適（目的関数）値 人数が最大となるメンバー ゴルビー 最適解 ミッテラン (optimal solution) クリントン レーガン 人数 ４人 最適目的関数値 （最適値） (optimal value) Euler閉路（除雪車の問題） 除雪車問題のグラフ表現 パス(path) 始点 (source) パス 終点 (sink) 閉路(circuit) 閉路 オイラー閉路(Euler circuit) オイラー（Euler）閉路 ＝ すべての枝をちょうど１回ずつ経由する閉路 連結グラフ・非連結グラフ 連結(connected)グラフ より正確には．．． グラフの各点から別の各点 へのパスが存在する <->グラフが連結 連結でないグラフ 練習１ • グラフは連結か？ （a) （b) Eulerの定理 グラフがEuler閉路を持つ グラフの点の次数がすべて偶数 かつ グラフが連結 Euler閉路の求め方 （アルゴリズム） 適当な点から出発し、出発点と通過していない枝からな るグラフが連結であるように枝を適当な順番でたどる。 Euler閉路 このような手順をアルゴリズムと呼ぶ 宿題１（パーキングチェック） P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P 図のような道がある．パーキングメーターをチェックするための ルートを見つけるために有効なグラフを作図せよ．ただし，道全 て２車線であるとし，パーキングメーターは一度に片側しか チェックできないとする． 宿題２（ごみ収集） 図のような道がある．ごみを収集するためのルートを見つける ための有効なためのグラフを作図せよ．ただし，道は全て２車 線であるが，ごみは一度に両側を収集できるとする． 宿題３：点次数とEuler閉路 それぞれ(パーキングとゴミ収集）のグラフ の点の次数を求めよ． それぞれのグラフはEuler閉路を持つであ ろうか？ もつならばそれを求めよ． 最小木問題 スパイは全部で5人いて，コードネームは，アリゲータ，ホワイ トベア，ブル，コンドル，シャークである． 新しい極秘情報を，他の4人のスパイに連絡せよという指令 が伝えられた． ただし，費用を安くしなければならない． どのように連絡を取れば，最小の費用で極秘情報を仲間に連 絡できるだろうか？ 最小木問題 2 4 ホワイトベア コンドル アリゲータ 5 1 1 4 ブル 3 シャーク 木(tree) 木＝閉路を含まない連結グラフ 全域木(spanning tree) 全域木＝全ての点をつなぐ木 最小木問題（Kruskal法） 2 3 ホワイトベア コンドル アリゲータ 5 11 1 4 ブル 3 費用の小さい枝から順次試す 8万円 貪欲アルゴリズム (greedy algorithm) シャーク 最小木問題（Prim法） 2 3 ホワイトベア コンドル アリゲータ 5 1 1 4 ブル アリゲータに 接続する最小費用 3 シャーク 最小木問題（Prim法） 2 3 ホワイトベア コンドル アリゲータ 1 1 5 4 ブル 3 シャーク アリゲータ＋ブルに 接続する最小費用 最小木問題（Prim法） 2 3 ホワイトベア コンドル アリゲータ 1 5 1 4 ブル 3 アリゲータ＋ブル＋ホワイトベア に接続する最小費用 シャーク 最小木問題（Prim法） 2 3 ホワイトベア アリゲータ 1 1 コンドル アリゲータ＋ブル＋ ホワイトベア+シャーク 5 に接続する最小費用4 ブル 3 シャーク 最小木問題（Prim法） 2 3 ホワイトベア アリゲータ コンドル 1 5 1 4 ブル 3 総計8万円 これも一種の貪欲アルゴリズム シャーク 最小木問題（改善法） 2 3 ホワイトベア コンドル アリゲータ 5 1 1 4 ブル 3 シャーク 総費用＝14万円 最小木問題（改善法） 2 この枝を 加える 3 ホワイトベア コンドル アリゲータ 5 1 1 4 ブル 3 シャーク 総費用＝14万円 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 1 5 1 4 ブル 総費用＝14+3万円 3 シャーク 閉路ができるので 一番費用の大きい この枝を削除する 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 1 5 1 4 ブル 3 閉路ができるので 一番費用の大きい この枝を削除する シャーク 総費用＝14+3-5万円（2万円得した！） ＝12万円 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 1 5 1 4 ブル 3 シャーク 総費用＝12万円 この枝を加える 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 1 5 1 4 ブル 3 閉路ができるので 一番費用の大きい シャーク この枝を削除する 総費用＝12+1-4万円（3万円得した！） ＝9万円 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 1 5 1 4 ブル 3 総費用＝9万円 この枝を加える シャーク 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 閉路ができるので 5 一番費用の大きい この枝を削除する 4 1 1 ブル 3 総費用＝9+1-2万円（1万円得した！） ＝8万円 シャーク 最小木問題（改善法） 2 ホワイトベア 3 コンドル アリゲータ 1 5 1 4 ブル 3 総費用＝8万円 シャーク 宿題４ 全域木（Kruskal,Prim,改善法） 18 38 47 56 69 73 65 71 84 62 •上のグラフの全域木をKruskal法で求めよ． •上のグラフの全域木をPrim法で求めよ． •上のグラフの全域木を改善法で求めよ．
© Copyright 2024 ExpyDoc
