このページは以下の「ITパスポート シラバス6.3」学習用コンテンツです。
◆大分類：7.基礎理論
◆中分類：13.基礎理論
| ◆小分類 | ◆見出し | ◆学習すべき用語 |
|---|---|---|
| 34.応用数学 | (3) グラフ理論 | 頂点（ノード） 辺（エッジ） 有向グラフ 無向グラフ |
ポイント解説グラフ理論は点（頂点）と線（辺）で構成されるネットワークを扱う数学の分野です。例えば、駅（頂点）と線路（辺）の関係を考えるイメージですね。
グラフを使うと複雑なネットワークの構造を簡単に表現でき、インターネットやソーシャルネットワーク、配送ルートの最適化など、現実の多くの問題に応用されていたりします。
最短経路や全ての点を通る経路を探すといったことができるようになります。
頂点（ノード）
頂点（ノード）はグラフ理論においてグラフを構成する基本単位の一つです。頂点は通常点として表されそれぞれが一つの要素やオブジェクトを表します。
頂点同士は辺（エッジ）によって接続されることがあります。この接続関係を用いてさまざまなネットワーク構造やパスの探索などの解析を行います。
例えば、ソーシャルネットワークにおけるユーザーや、道路網における交差点が頂点として考えられます。
コンピュータネットワーク（TCP/IP）では、構成するPC、ルーター、プリンターなどの機器は「ノード」になります。
クラウド環境などではサーバ1台を指す単位として「台」ではなく「ノード」という言い方もよくされます。
頂点（ノード）に関する学習用問題
問題
グラフ理論における頂点（ノード）の役割として正しいものはどれですか？
- グラフ内の全ての辺を接続する役割
- グラフの基本単位として他の頂点と接続する点
- グラフにおけるサイクルを形成する点
%%replace6%%
正解
2 グラフの基本単位として他の頂点と接続する点
解説
頂点（ノード）はグラフ理論で基本単位となり、他の頂点と接続してネットワークを形成します。
選択肢1や3は誤りであり、辺の接続やサイクル形成は頂点の役割とは異なります。
問題
頂点（ノード）が持つ特性として最も適切なものはどれですか？
- 互いに直接接続されている全ての辺の集まり
- グラフにおける一つの要素またはオブジェクトを表す点
- グラフ内のすべての辺の数
%%replace6%%
正解
2 グラフにおける一つの要素またはオブジェクトを表す点
解説
頂点はグラフにおける要素やオブジェクトを表し点として表現されます。
選択肢1と3は辺に関する特性であり頂点の説明とは異なります。
問題
以下のうち、頂点（ノード）の具体的な例として適切でないものはどれですか？
- ソーシャルネットワークにおけるユーザー
- 道路網における交差点
- 電力網における配電線
%%replace6%%
正解
3 電力網における配電線
解説
配電線は辺（エッジ）に該当し頂点ではありません。
ユーザーや交差点は頂点の具体的な例として適切です。
辺（エッジ）
辺（エッジ）はグラフ理論において頂点同士を接続する線のことです。辺は頂点間の関係や結びつきを表し、方向性があるもの（有向辺）と方向性がないもの（無向辺）があります。
例えば、ソーシャルネットワークではユーザー間の友達関係、道路網では交差点間の道路が辺に相当します。辺の有無や数はグラフの構造や性質に大きく影響を与えます。
辺（エッジ）に関する学習用問題
問題
辺（エッジ）の役割として適切なものはどれですか？
- 頂点を表す点
- 頂点同士を接続する線
- グラフ全体のサイクルを示すループ
%%replace6%%
正解
2 頂点同士を接続する線
解説
辺（エッジ）はグラフにおいて頂点同士を接続する役割を持ちます。
選択肢1や3は誤りであり、頂点やサイクルの説明に該当します。
問題
グラフ内の辺（エッジ）に関する記述として正しいものはどれですか？
- グラフ内のすべての頂点を一意に識別する
- 頂点間の関係や結びつきを表す
- グラフにおけるすべての経路を示す
%%replace6%%
正解
2 頂点間の関係や結びつきを表す
解説
辺（エッジ）は頂点間の関係性を示します。
選択肢1や3は頂点や経路に関する説明であり、辺の特性ではありません。
問題
以下のうち、辺（エッジ）の具体的な例として最も適切なものはどれですか？
- ソーシャルネットワークにおける友達関係
- 道路網における交差点
- 電力網における変電所
%%replace6%%
正解
1 ソーシャルネットワークにおける友達関係
解説
友達関係は辺（エッジ）の具体的な例です。
交差点や変電所は頂点に該当するもので、辺の例ではありません。
有向グラフ
有向グラフとはグラフの辺に方向性があるグラフのことを指します。すなわち、各辺が始点と終点を持ち、片方向にのみ接続されていることが特徴です。
片方向の関係性や依存関係を表現するのに適しています。例えば、ウェブサイト間のリンク構造やプロジェクトのタスク依存関係などが有向グラフで表現されることがあります。
有向グラフに関する学習用問題
問題
有向グラフの特徴として正しいものはどれですか？
- 辺に方向性がある
- すべての頂点が一つの頂点に接続されている
- 辺の数が頂点の数と常に等しい
%%replace6%%
正解
1 辺に方向性がある
解説
有向グラフは辺に方向性があるため一方通行の関係を表現できます。
選択肢2や3は有向グラフの特徴ではありません。
問題
有向グラフが適用されるシーンとして適切でないものはどれですか？
- ウェブサイト間のリンク構造
- プロジェクトのタスク依存関係
- 道路網の交差点間の双方向交通
%%replace6%%
正解
3 道路網の交差点間の双方向交通
解説
有向グラフは片方向の関係を表すため双方向交通を表すには適していません。
ウェブサイトのリンク構造やタスクの依存関係には有向グラフが適しています。
問題
有向グラフの具体的な例として最も適切なものはどれですか？
- プロジェクト管理におけるタスクの依存関係
- 道路網における交差点
- ソーシャルネットワークにおける友達関係
%%replace6%%
正解
1 プロジェクト管理におけるタスクの依存関係
解説
タスクの依存関係は有向グラフで適切に表現されます。
交差点や友達関係は無向グラフで表されることが多いです。
無向グラフ
無向グラフはグラフの辺に方向性がないグラフです。つまり、辺が頂点間を双方向に接続しており、どちらの方向からでも到達可能であることが特徴です。
無向グラフは対等な関係を表現するのに適しており、ソーシャルネットワークの友人関係や道路網の交差点間の道路などが無向グラフの例として挙げられます。
無向グラフに関する学習用問題
問題
無向グラフの特徴として正しいものはどれですか？
- 辺に方向性がない
- すべての辺が片方向に接続されている
- 辺の数が頂点の数と常に等しい
%%replace6%%
正解
1 辺に方向性がない
解説
無向グラフは辺に方向性がなく双方向の関係を表現します。
選択肢2や3は無向グラフの特徴ではありません。
問題
無向グラフが適用されるシーンとして最も適切なものはどれですか？
- 片方向の依存関係を表すプロジェクト管理
- ソーシャルネットワークにおける友人関係
- ウェブサイト間のリンク構造
%%replace6%%
正解
2 ソーシャルネットワークにおける友人関係
解説
友人関係は双方向の関係を持つため無向グラフで適切に表現できます。
片方向の依存関係やリンク構造は有向グラフが適しています。
問題
無向グラフの具体的な例として適切でないものはどれですか？
- ソーシャルネットワークにおける友人関係
- プロジェクト管理におけるタスクの依存関係
- 道路網における交差点間の道路
%%replace6%%
正解
2 プロジェクト管理におけるタスクの依存関係
解説
タスクの依存関係は片方向の関係であり有向グラフが適しています。
友人関係や交差点間の道路は無向グラフで表されます。