DAG!! 強連結な部分 強連結成分 8. 有向グラフの連結性 強連結グラフ（辺を⼀つ除去すると弱連結になる） 教科書p. 弱連結(weakly connected), 弱(weak): ダイグラフの任意の2頂点u, vの間に半道が存在する; 片方向連結(unilaterally connected), 方方向(unilateral): ダイグラフの任意の2頂点u, vに対して、uがvに到達可能または、vがuに到達できる(一方の頂点から他方の頂点への道が存在する) 連結性. 1.1.5. HCPC勉強会 2016/01/07 7 強連結成分分解 有向グラフの強連結な部分を潰してDAGにする v1 v2 v5 v3 v4 v7 v8 v9 v6 V10 v1 V2,3,4,5 V7,8,9 v6 V10 Directed Graph DAG! 強連結 （255ページ） 有向グラフの各頂点から任意の 頂点へ至る道が存在するとき、 この有向グラフを強連結であるという。 部分グラフのうち、強連結であって、 しかもそれ以上頂点を追加すると 強連結でなくなるものを強連結成分という。 9 3正則2枝連結グラフ ... 弱 双対定理. 強連結グラフ構造でとらえ，実証的に解析・評価し，クラスターの特徴を摘出し，新たな知見を提示している。 とく に，非対称類似度行列として，流出と流入の概念に基づく3 種類のとらえ方を提示し，提案法の性能を具体化してい 3正則2枝連結グラフ ... 弱 双対定理. HCPC勉強会 2016/01/07 8 何が嬉しいの？ また，この有向グラフGの弱連結成分（Gの弱連結な部分有向グラフの中で極大なもの）は， 頂点集合{a, b, c}, {d}からそれぞれ生成されるGの点誘導部分グラフである． 片方向連結については授業で説明していないので省略．

強連結性 (有向)グラフG =(V,A)において, 任意な点から任意な点への有向道が存在するとき, Gは強連結(strongly connected) という. X の部分集合A ˆ X に対して, 像f(A) = ff(a) j a 2 Ag はY の部分集合であり, Y の部分集合B ˆ Y に対して, 逆像f 1(B) = fx 2 X j f(x) 2 Bg はX の部分集合である. 強連結 （255ページ） 有向グラフの各頂点から任意の 頂点へ至る道が存在するとき、 この有向グラフを強連結であるという。 部分グラフのうち、強連結であって、 しかもそれ以上頂点を追加すると 強連結でなくなるものを強連結成分という。 9

強連結成分分解の計算：例 a d c b e g f h 8 6 5 4 1 3 2 7 •2回目： – 右の深さ優先探索（修正版）を実行 （無向グラフの連結成分分解と類似） • 各頂点, 各枝を白く塗る • 各頂点u∈V に対し，f(u)の大きい順 に以下を実行 u が白色（未走査）ならば k=u とおき， 例1.4: 図1.1のグラフGは,2枝連結,3枝連結であるが,4枝連結ではない. 156 離散グラフの特徴 有向グラフで、任意の2節点間に双⽅向に有向順路が存在す るものを強連結（strongly connected）グラフ … 3.強連結でないグラフに対して Dijkstra 法を適用した場合，どのような 結果になるか？（例えば，v1 から v3 に至る path がないようなグラフ の場合，f3 の値は？） 4.Dijkstra 法を，最短距離のみではなく最短経路も出力できるように書き 換えよ。 弱連結な有向グラフが与えられたときに，いくつか の枝を縮約して強連結なグラフを作ることを考える． ただし，有向グラフが弱連結であるとは，枝の向きを 無視した無向グラフが連結であることをい … 離散数学問題(2) (担当: 塚本千秋) 2019年10月10日 学 生 番 号 氏 名 集合X から集合Y への写像f:X !Y を考える. 強連結成分分解の計算：例 a d c b e g f h 8 6 5 4 1 3 2 7 •2回目： – 右の深さ優先探索（修正版）を実行 （無向グラフの連結成分分解と類似） • 各頂点, 各枝を白く塗る • 各頂点u∈V に対し，f(u)の大きい順 に以下を実行 u が白色（未走査）ならば k=u とおき， Q ... 問題に実行可能解が存在するならば， の組に対して，両者に最適解が存在して， =cx yb. Q ... 問題に実行可能解が存在するならば， の組に対して，両者に最適解が存在して， =cx yb. k 連結は, 枝連結との区別を強調して, k 点連結とも呼ばれる. 強連結と向き付け可能性 強連結 ： 任意の2点v,wの間に点vから点wへの道がある 向き付け可能 ： グラフGの全ての辺を方向付けて強連結有向グラフが得られるとき 向き付け可能なグラフの一例