グラフの基本きほん

date2026-03-27descriptionグラフの基本を、点と辺で関係を表す見方から整理し、探索アルゴリズムの土台を説明します。prerequisites離散数学の入口 / 論理と真理値表の基本 / DFSとBFSの基本type講義statusactive

informationgraphundergraduatelecture

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、グラフは図ずそのものではなく、「どの対象たいしょうとどの対象たいしょうがつながっているか」を頂点ちょうてんと辺へんで表あらわす構造こうぞうだということです。

人間関係にんげんかんけい、道路網どうろもう、依存関係いぞんかんけいのように、個々ここの対象たいしょうそのものより「関係かんけい」が重要じゅうような問題もんだいでは、グラフで表現ひょうげんすると整理せいりしやすくなります。DFS や BFS は、この構造こうぞうの上うえをどう歩あるくかという話はなしです。

用語ようごと定義ていぎ

頂点ちょうてんVertex とは、対象たいしょうを表あらわす点てんです。

辺へんEdge とは、頂点ちょうてんどうしの関係かんけいを表あらわす線せんです。

隣接りんせつAdjacency とは、2 つの頂点ちょうてんが辺へんで直接ちょくせつつながっていることです。

方針ほうしん

まず対象たいしょうを頂点ちょうてん、関係かんけいを辺へんに置おき換かえます。そのあと、どの頂点ちょうてんからどこへ進すすめるかという隣接関係りんせつかんけいで構造こうぞうを読よみます。

直感的ちょっかんてきな説明せつめい

駅えきを点てん、線路せんろを線せんだと考かんがえると、路線図ろせんずはグラフです。このとき大事だいじなのは、駅えきの形かたちや大おおきさではなく、「どことどこがつながっているか」です。

厳密げんみつな説明せつめい

1. グラフ

グラフ $G = (V, E)$ は、頂点ちょうてん集合しゅうごう $V$ と辺へん集合しゅうごう $E$ からなります。

2. 無向むこうグラフと有向ゆうこうグラフ

向むきのない関係かんけいなら無向むこうグラフ、向むきのある関係かんけいなら有向ゆうこうグラフです。

3. 探索たんさくとのつながり

DFS や BFS は、始点してんから辺へんをたどって到達とうたつできる頂点ちょうてんを調しらべる方法ほうほうです。

見分みわけ方かた

対象たいしょうそのものより、関係かんけいが主役しゅやくならグラフを疑うたがいます。
最短経路さいたんけいろ、到達可能性とうたつかのうせい、連結れんけつが問とわれたら、グラフとして整理せいりできないか考かんがえます。
順番じゅんばんだけの列れつとして見みると扱あつかいにくい関係かんけいは、グラフにすると見通みとおしがよくなります。

最終形さいしゅうけい

[PARSE ERROR: Undefined("Command(\"boxed\")")] G = (V, E)

[PARSE ERROR: Undefined("Command(\"boxed\")")] 頂点 = 対象, 辺 = 関係

一言ひとことでいうと

グラフは、対象たいしょうの集あつまりではなく、その間あいだの関係かんけいを主役しゅやくにして表あらわす構造こうぞうです。