Graph Theory
点と線で表現する
- 様々なシステムは，本質的には，点と線で表現できるものが多い．
- 例えば? →昔から考察の対象になっている →グラフ理論の発生，ネットワーク計画 →ORで用いる手法の大きな柱へ
グラフ
ネットワーク
グラフとは
- 写像 ∂+ , ∂ｰ ：A→V とからなる複合概念 G=(V, A ;∂+ , ∂ｰ )
グラフの種類
完備グラフ （完全グラフ） complete graph
グラフの種類（2）
ネットワークとは
例：各枝に距離dが与えられたグラフはネットワークN=(G=(V,A;∂+ , ∂ｰ ) ,d)
演習4‐1 身近なグラフ,ネットワーク
- グラフまたはネットワークで表現できる身近な社会現象，社会システムをいくつか挙げてみよう．
- 物理的なネットワーク（例えば鉄道網など）以外の例をなるべく考えてみよう．
- それらを具体的にグラフ，ネットワークで表現してみよう.
グラフ上の基本的な操作
- グラフを分解する
- 連結成分分解 （無向グラフ）
- 強連結成分分解 （有向グラフ）
グラフ，ネットワークで表現されたシステムを扱うために必要な基本的な技．
グラフの探索
グラフの効率の良い探索方法
- 幅優先探索 Breadth-first search
以下のStep2，3を未探索辺がなくなるまで繰り返す．
Step2: 最新ラベルを持つ点から未探索辺を走査する．
Step2: 最も早いラベルを持つ点から未探索辺を走査する．
Step3: 走査した未探索辺の終点にラベルが付いていなかったらラベルを付ける．
探索木
- 探索中に点にラベルを付ける原因となった枝の集まりは，グラフの全点を結ぶ出発点を根とする有向木になっている．（どうして？） ⇒「探索木」と呼ぶ
- 探索木はグラフを取り扱う際に，有用な情報を与えてくれることが多い．
練習4-1 奥優先探索をしてみよう
PPT Slide
演習4-2 グラフの探索
グラフの分解
- 点ｖは関節点 ⇔連結なグラフから点ｖを除くと 非連結になる
無向グラフの2連結成分分解
有向グラフの強連結成分分解
- 有向グラフが強連結 ⇔任意の2点間に両方向の 有向道が存在
Hasse図
2連結成分，強連結成分の求め方
- 2連結成分分解，強連結成分分解共に，深さ優先探索をしながら情報を集めることにより可能である．（解法を作ってみよう!!）
演習4-3 2連結成分分解
（1）機能が停止することにより，他の中継局間の通信にまで影響を及ぼす中継局はどれか指摘せよ．
（2）通信の信頼性を高めるためには新たにどのような線をどこに引けばよいか．適切な設置計画を提案せよ．
演習4-4 強連結成分分解
グラフ，ネットワークを表現する
ネットワークのデータ
隣接行列での表現
接続行列での表現
リスト表現
演習4-5
なお，各表現において不都合が生じる場合は，それがどのような状況でおきるのか考察せよ．