グラフの基本きほん

1導入どうにゅう

この講義こうぎでは、対象間たいしょうかんの関係かんけいを頂点ちょうてんと辺へんで表あらわすグラフの定義ていぎと、探索たんさくを記述きじゅつするために必要ひつような隣接りんせつ・道みち・距離きょり・連結性れんけつせいを説明せつめいする。

道路網どうろもうでは交差点こうさてんの形かたちより接続関係せつぞくかんけいが重要じゅうようであり、通信網つうしんもうでは機器ききの外観がいかんより通信可能性つうしんかのうせいが重要じゅうようである。グラフは、対象たいしょうそのものから関係かんけいだけを抽出ちゅうしゅつし、異ことなる問題もんだいを同おなじ構造こうぞうとして扱あつかうための表現ひょうげんである。

2用語ようごと定義ていぎ

グラフ $$G=(V,E)$$G=(V,E) は、頂点ちょうてんの集合しゅうごう $$V$$V と辺へんの集合しゅうごう $$E$$E からなる。頂点ちょうてんは対象たいしょうを、辺へんは二ふたつの対象間たいしょうかんの関係かんけいを表あらわす。この講義こうぎの無向むこうグラフは有限単純ゆうげんたんじゅんグラフであり、

とする。したがって、自己じこループと多重辺たじゅうへんは含ふくまれない。

有向ゆうこうグラフでは $$E\subseteq V\times V$$E\subseteq V\times V とし、辺へん $$(u,v)$$(u,v) は $$u$$u から $$v$$v への向むきを持もつ。以下いかでは、特とくに断ことわらない限かぎり有限単純無向ゆうげんたんじゅんむこうグラフを扱あつかう。

二頂点にちょうてん $$u,v$$u,v が辺へんで直接結ちょくせつむすばれているとき、$$u$$u と $$v$$v は隣接りんせつするという。頂点ちょうてん $$v$$v に隣接りんせつする頂点ちょうてんの集合しゅうごうを

と書かく。

3道みちと距離きょり

頂点列ちょうてんれつ

が各かく $$i=1,\dots ,k$$i=1,\ldots,k について $$\{v_{i-1},v_i\}\in E$$\{v_{i-1},v_i\}\in E を満みたすとき、この列れつを長ながさ $$k$$k の歩道ほどうという。さらに $$v_0,\dots ,v_k$$v_0,\ldots,v_k が相異あいことなるとき、これを道みちという。頂点ちょうてん $$s$$s から $$v$$v への歩道ほどうが存在そんざいするとき、閉路へいろを除のぞけば道みちが得えられるため、$$v$$v は $$s$$s から到達可能とうたつかのうである。

無重むおもみグラフにおける距離きょり $$d(s,v)$$d(s,v) は、$$s$$s から $$v$$v への道みちの長ながさの最小値さいしょうちである。道みちが存在そんざいしない場合ばあいは $$d(s,v)=\mathrm{\infty }$$d(s,v)=\infty とする。ここで「無重むおもみ」とは、すべての辺へんを一歩いっぽとして数かぞえることを意味いみする。

4連結性れんけつせい

任意にんいの二頂点にちょうてんの間あいだに道みちが存在そんざいする無向むこうグラフを連結れんけつという。連結れんけつでないグラフは、互たがいに到達可能とうたつかのうな頂点ちょうてんをまとめた連結成分れんけつせいぶんに分解ぶんかいできる。

例れいえば

では、$$a,b,c$$a,b,c は同おなじ連結成分れんけつせいぶんに属ぞくし、$$d$$d は単独たんどくの連結成分れんけつせいぶんをなす。また、$$d(a,c)=2$$d(a,c)=2 である。

5表現方法ひょうげんほうほう

隣接りんせつリストは各頂点かくちょうてん $$v$$v に対たいして $$N\left(v\right)$$N(v) を保存ほぞんする。頂点数ちょうてんすうを $$\left|V\right|$$|V|、辺数へんすうを $$\left|E\right|$$|E| とすると、無向むこうグラフの全隣接ぜんりんせつリストの要素数ようそすうは $$2\left|E\right|$$2|E| である。各辺かくへんが両端点りょうたんてんのリストに一度いちどずつ現あらわれるためである。

隣接行列りんせつぎょうれつは、頂点ちょうてんに番号ばんごうを付つけ、辺へんの有無うむを行列要素ぎょうれつようそで表あらわす。辺へんの存在判定そんざいはんていは高速こうそくだが、頂点数ちょうてんすうの二乗にじょうに比例ひれいする領域りょういきを必要ひつようとする。疎そなグラフでは隣接りんせつリストが適てきし、密みつなグラフや辺へんの存在判定そんざいはんていを頻繁ひんぱんに行おこなう場合ばあいは隣接行列りんせつぎょうれつが候補こうほになる。

6探索たんさくへの接続せつぞく

グラフ探索たんさくは、始点してんから隣接頂点りんせつちょうてんを順じゅんに調しらべ、到達可能とうたつかのうな頂点ちょうてんを列挙れっきょする操作そうさである。この講義こうぎで定義ていぎした頂点ちょうてん、辺へん、隣接りんせつ、道みち、距離きょりが、DFSとBFSの入力にゅうりょくと主張しゅちょうを構成こうせいする。

7まとめ

• グラフ $$G=(V,E)$$G=(V,E) は、対象たいしょうを頂点ちょうてん、関係かんけいを辺へんとして表あらわす。
• 道みちは相異あいことなる隣接頂点りんせつちょうてんを順じゅんに並ならべた列れつであり、無重むおもみ距離きょりは最短さいたんの道みちの辺数へんすうである。
• 連結性れんけつせいは、任意にんいの二頂点間にちょうてんかんの到達可能性とうたつかのうせいで定義ていぎされる。
• 隣接りんせつリストと隣接行列りんせつぎょうれつは、同おなじグラフを異ことなる計算特性けいさんとくせいで表現ひょうげんする。