グラフの基本きほん

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

Graph Basics

1Introduction

This lecture defines graphs as representations of relationships between objects and develops adjacency, paths, distance, and connectivity as the concepts required for graph traversal.

In a road network, connectivity matters more than the shapes of intersections. In a communication network, reachability matters more than the appearance of devices. A graph extracts these relationships and allows structurally identical questions to be treated in a common language.

2Terms and definitions

A graph $$G=(V,E)$$G=(V,E) consists of a set $$V$$V of vertices and a set $$E$$E of edges. Vertices represent objects, while edges represent relationships between pairs of objects. An undirected graph in this lecture is a finite simple graph with

Thus it contains neither self-loops nor parallel edges.

For a directed graph, $$E\subseteq V\times V$$E\subseteq V\times V, and an edge $$(u,v)$$(u,v) is oriented from $$u$$u to $$v$$v. Unless stated otherwise, the remainder of this lecture considers finite simple undirected graphs.

Two vertices $$u,v$$u,v are adjacent when an edge directly joins them. The neighborhood of a vertex $$v$$v is

3Paths and distance

A sequence of vertices

is a walk of length $$k$$k when $$\{v_{i-1},v_i\}\in E$$\{v_{i-1},v_i\}\in E for every $$i=1,\dots ,k$$i=1,\ldots,k. It is a path when $$v_0,\dots ,v_k$$v_0,\ldots,v_k are distinct. If a walk from $$s$$s to $$v$$v exists, deleting cycles yields a path, and $$v$$v is reachable from $$s$$s.

In an unweighted graph, the distance $$d(s,v)$$d(s,v) is the minimum length of a path from $$s$$s to $$v$$v. If no path exists, set $$d(s,v)=\mathrm{\infty }$$d(s,v)=\infty. Here, “unweighted” means that every edge counts as one step.

4Connectivity

An undirected graph is connected when a path exists between every pair of vertices. A disconnected graph decomposes into connected components, each consisting of vertices that are mutually reachable.

For example, if

then $$a,b,c$$a,b,c form one connected component, while $$d$$d forms a component by itself. Moreover, $$d(a,c)=2$$d(a,c)=2.

5Representations

An adjacency list stores $$N\left(v\right)$$N(v) for each vertex $$v$$v. If the graph has $$\left|V\right|$$|V| vertices and $$\left|E\right|$$|E| edges, all adjacency lists of an undirected graph contain $$2\left|E\right|$$2|E| entries in total, because every edge appears once at each endpoint.

An adjacency matrix numbers the vertices and records edge existence in matrix entries. It supports fast edge-existence queries but requires space proportional to the square of the number of vertices. Adjacency lists are suitable for sparse graphs; adjacency matrices are candidates for dense graphs or workloads dominated by edge-existence queries.

6Connection to traversal

A graph traversal starts at a vertex, examines adjacent vertices in a specified order, and enumerates reachable vertices. Vertices, edges, adjacency, paths, and distance as defined here form the input and claims of DFS and BFS.

7Summary

• A graph $$G=(V,E)$$G=(V,E) represents objects as vertices and relationships as edges.
• A path is a sequence of distinct adjacent vertices, and unweighted distance is the number of edges in a shortest path.
• Connectivity is defined by reachability between every pair of vertices.
• Adjacency lists and adjacency matrices represent the same graph with different computational tradeoffs.