グラフの基本きほん

導入どうにゅう

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

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

用語ようごと定義ていぎ

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

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

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

方針ほうしん

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

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

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

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

見分みわけ方かた

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

最終形さいしゅうけい

一言ひとことでいうと

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