基本情報技術者試験 練習問題 14：グラフの種類と特性
グラフ理論について述べた文として、正しいものはどれか。
- グラフは必ず連結である必要があり、複数の独立した部分グラフに分かれることはない。
- 有向グラフは矢印付きのエッジを持ち、通信方向が一方通行で指定される。
- 重み付きグラフではすべてのエッジに同じ重みが付与されている。
- 完全グラフは複数の独立したコンポーネントで構成される疎なグラフである。
- オイラー路（Eulerian Path）はすべてのノードをちょうど1回ずつ訪問する路である。
Qraftユーザーの成績：難易度 Cランク（レーティング1196）・正答率 56%（9/16回正解）
レーティングは解いた人の実力と正誤から算出する難しさ（初期値1200）。ランクはその全問題中の順位（S+が最難関、F-が最易）
正解と解説を見る
正解：有向グラフは矢印付きのエッジを持ち、通信方向が一方通行で指定される。
グラフ理論はネットワーク分析、社会ネットワーク、経路探索など多くの応用があります。
グラフの構成要素：
- 頂点（ノード）とエッジ（辺）から構成
- 無向グラフ：エッジに方向がない（例：友人関係）
- 有向グラフ：エッジに方向がある（例：フォローする/されるTwitterの関係）
正しいのは「有向グラフは矢印付きのエッジを持ち、通信方向が一方通行で指定される」です。
その他の概念：
連結性：グラフが連結でない場合、複数の独立したコンポーネントに分かれることがあります。
重み付きグラフ：エッジごとに異なる重みが付与されます（例：都市間の距離、通信コスト）。すべて同じ重みではありません。
完全グラフ：すべての頂点対の間にエッジが存在する密なグラフです。決して疎なグラフではありません。
オイラー路とハミルトン路：
- オイラー路：すべてのエッジをちょうど1回ずつ訪問する路
- ハミルトン路：すべてのノード（頂点）をちょうど1回ずつ訪問する路
問題文の説明はハミルトン路の説明です。