【ITパスポート練習問題 6.3対応】(3) グラフ理論（ノード、エッジ、有向グラフ、無向グラフ）

【解説】

正解: 2 グラフの基本単位として他の頂点と接続する点

この問題は、データ構造やアルゴリズムの基礎となる「グラフ理論」において、最も基本的な要素である「頂点（ノード）」の定義を正しく理解しているかを確認するものです。

正解は「グラフの基本単位として他の頂点と接続する点」です。グラフ理論におけるグラフとは、頂点（点）とそれらを結ぶ辺（線）で構成される図形やデータ構造のことです。頂点は、ネットワーク内の位置や要素を表す役割を持ち、辺によって他の頂点とつながることで構造を作ります。

選択肢1の「グラフ内の全ての辺を接続する役割」は、頂点が辺の接続点であることは確かですが、全ての辺を接続するわけではないため不正確です。選択肢3の「グラフにおけるサイクルを形成する点」は、サイクル（閉じた経路）は頂点と辺の組み合わせで形成されるものであり、頂点単体の役割の説明としては適切ではありません。

【解説】

正解: 2 グラフにおける一つの要素またはオブジェクトを表す点

この問題は、グラフ理論を用いて現実世界の事象をモデル化する際に、頂点（ノード）が何を表しているかをイメージできているかを問うものです。

正解は「グラフにおける一つの要素またはオブジェクトを表す点」です。例えば、路線図であれば「駅」、組織図であれば「人」、コンピュータネットワークであれば「端末」といったように、頂点は個々の具体的な対象（オブジェクト）を表現します。

選択肢1の「互いに直接接続されている全ての辺の集まり」は、頂点の定義ではなく、頂点に接続する辺の集合に関する説明です。選択肢3の「グラフ内のすべての辺の数」は、グラフの規模を示す数値であり、頂点の特性の説明ではありません。

【解説】

正解: 3 電力網における配電線

この問題は、具体的な事例において「頂点（ノード）」と「辺（エッジ）」の違いを正しく区別できるかを確認するものです。

選択肢3の「電力網における配電線」は、電気を運ぶための経路であり、グラフ理論では頂点同士を結ぶ「辺（エッジ）」に相当するため、頂点の例としては不適切であり、これが正解となります。

一方、選択肢1の「ソーシャルネットワークにおけるユーザー」や、選択肢2の「道路網における交差点」は、ネットワークを構成する主体や地点であるため、これらは「頂点（ノード）」として表現される適切な例です。

【解説】

正解: 2 頂点同士を接続する線

この問題は、グラフを構成するもう一つの基本要素である「辺（エッジ）」の役割について理解しているかを確認するものです。

正解は「頂点同士を接続する線」です。辺は、2つの頂点の間に存在し、それらの間に関係性や経路があることを示します。視覚的には線で描かれます。

選択肢1の「頂点を表す点」は、文字通り頂点（ノード）の説明です。選択肢3の「グラフ全体のサイクルを示すループ」は、グラフの特定の部分構造を指す言葉であり、辺そのものの基本的な定義ではありません。

【解説】

正解: 2 頂点間の関係や結びつきを表す

この問題は、辺（エッジ）がデータ構造としてどのような意味を持つかを問うものです。単なる線としてだけでなく、情報の結びつきとしての意味を理解しているかがポイントです。

正解は「頂点間の関係や結びつきを表す」です。例えば、人間関係のグラフであれば「友人である」という関係、路線図であれば「線路でつながっている」という物理的な結びつきを辺が表します。

選択肢1の「グラフ内のすべての頂点を一意に識別する」は、頂点に割り当てられるIDやラベルの役割です。選択肢3の「グラフにおけるすべての経路を示す」は、経路探索などの処理の結果として得られるものであり、個々の辺の説明としては不適切です。

【解説】

正解: 1 ソーシャルネットワークにおける友達関係

この問題は、身近な事例を通じて「辺（エッジ）」の概念を正しく認識できているかを確認するものです。

正解は「ソーシャルネットワークにおける友達関係」です。ここではユーザーが「頂点」となり、ユーザー同士のつながりである友達関係が「辺」として表現されます。

選択肢2の「道路網における交差点」や、選択肢3の「電力網における変電所」は、場所や施設を表すものであり、これらは「頂点（ノード）」に該当するため、辺の例としては不適切です。

【解説】

正解: 1 辺に方向性がある

この問題は、グラフの種類の一つである「有向グラフ」の定義とその特徴を理解しているかを確認するものです。

正解は「辺に方向性がある」です。有向グラフでは、辺に矢印のような向きが設定されており、AからBへの移動は可能だが、BからAへは移動できない（あるいは別の辺が必要）といった、一方通行の関係を表現できます。

選択肢2の「すべての頂点が一つの頂点に接続されている」は、スター型トポロジーなどの特定の形状を指すもので、有向グラフ全体の特徴ではありません。選択肢3の「辺の数が頂点の数と常に等しい」も、特定の条件下でのみ起こり得ることであり、有向グラフの定義ではありません。

【解説】

正解: 3 道路網の交差点間の双方向交通

この問題は、有向グラフの特性である「方向性」が、どのようなシーンのモデル化に適していないかを判断させるものです。

選択肢3の「道路網の交差点間の双方向交通」は、どちらの方向にも自由に行き来できる関係です。これを表現するには、方向を持たない「無向グラフ」を用いるのが一般的であるため、有向グラフの適用シーンとして「適切でない」ものとなり、これが正解です。

選択肢1の「ウェブサイト間のリンク構造」は、ページAからページBへのリンクがあっても逆があるとは限らないため、有向グラフが適しています。選択肢2の「プロジェクトのタスク依存関係」も、タスクAが終わらないとタスクBができないという順序があるため、有向グラフが適しています。

【解説】

正解: 1 プロジェクト管理におけるタスクの依存関係

この問題は、有向グラフを使用すべき具体的な業務シーンを理解しているかを問うものです。順序や流れが重要なプロセスを判別できるかが鍵です。

正解は「プロジェクト管理におけるタスクの依存関係」です。これはアローダイアグラムやPERT図などで用いられるように、「前の工程が終わってから次の工程へ進む」という明確な向きが存在するため、有向グラフの典型的な例です。

選択肢2の「道路網における交差点」や、選択肢3の「ソーシャルネットワークにおける友達関係」は、通常はお互いに行き来可能であったり、相互に対等な関係であったりするため、方向のない無向グラフで表されることが一般的です。

【解説】

正解: 1 辺に方向性がない

この問題は、「無向グラフ」の基本的な定義と特徴を理解しているかを確認するものです。

正解は「辺に方向性がない」です。無向グラフの辺は単なる線で表され、頂点Aと頂点Bがつながっている場合、AからBへも、BからAへも、対等に関係があることを示します。

選択肢2の「すべての辺が片方向に接続されている」は有向グラフの説明です。選択肢3の「辺の数が頂点の数と常に等しい」は、グラフの種類に関わらず、特定の構造（例：リング状など）の場合に限られる話であり、無向グラフの一般的な特徴ではありません。

【解説】

正解: 2 ソーシャルネットワークにおける友人関係

この問題は、無向グラフがどのようなデータのモデル化に適しているかを問うものです。相互的な関係性を持つデータを選べるかがポイントです。

正解は「ソーシャルネットワークにおける友人関係」です。一般的に「友達」という関係は、片方が友達ならもう一方も友達であるという相互（双方向）の関係であるため、方向性を持たない無向グラフで表現するのが最適です。

選択肢1の「片方向の依存関係を表すプロジェクト管理」や、選択肢3の「ウェブサイト間のリンク構造」は、どちらも「AからBへ」という向きが重要な意味を持つため、有向グラフを使用するのが適切です。

【解説】

正解: 2 プロジェクト管理におけるタスクの依存関係

この問題は、無向グラフで表現するには不適切な、方向性が必須となる事例を識別できるかを確認するものです。

選択肢2の「プロジェクト管理におけるタスクの依存関係」は、工程の順序（前後関係）が厳密に決まっており、方向性を無視すると業務の流れが表現できなくなります。そのため、無向グラフの例として「適切でない」ものとなり、これが正解です。

選択肢1の「ソーシャルネットワークにおける友人関係」や、選択肢3の「道路網における交差点間の道路（双方向通行）」は、どちら向きにも関係が成立するため、無向グラフで表現するのに適しています。