【アルゴリズム・データ構造】ノード間に複数の経路・辺が存在する！「多重グラフ」｜情報処理問題1000本ノック
基本情報技術者試験、応用情報技術者試験のアルゴリズム・データ構造（グラフ理論）分野における重要概念。「多重グラフ（Multigraph）」の定義と、対となる「単純グラフ（Simple Graph）」との違いを攻略しましょう。
1. 【 問題 】：テクノロジ系（アルゴリズム・データ構造）
【 問題 】 グラフ理論におけるデータ構造の定義に関する記述です。同一の2つの頂点（ノード）間に複数の辺（エッジ）が存在すること（多重エッジ）が許容されているグラフ構造は、次のうちどれか。
（ア）単純グラフ（Simple Graph）
（イ）多重グラフ（Multigraph）
（ウ）完全グラフ（Complete Graph）
（エ）二部グラフ（Bipartite Graph）
2. 正解：
正解：（イ）多重グラフ（Multigraph）
3. 解説：「『2点間に複数の経路や結びつきがある』ネットワーク！」
多重グラフ（Multigraph）は、同じ2頂点間に複数のエッジが存在する（多重辺 / Parallel Edges）グラフ構造です。
実世界の複雑なネットワーク（複数の交通手段、時間帯ごとの経路、複数の通信リンクなど）を直接モデル化する際に用いられます。
| 分類 | 同一2ノード間の複数エッジ | 自己ループ（自分へのエッジ） |
|---|---|---|
| （ア）単純グラフ （Simple Graph） |
許可しない （高々1本のみ） |
許可しない |
| （イ）多重グラフ （Multigraph） |
許可する （多重エッジあり） |
文脈により異なる （一般には許可しないことが多い） |
| 擬グラフ （Pseudograph） |
許可する | 許可する |
1. 理解のコツ:
・「東京駅」と「横浜駅」の間に「JR東海道線」「京浜東北線」「横須賀線」の3つの路線（エッジ）が並行して走っているような路線網をイメージしてください。このように2地点間に複数の線が存在できるモデルが多重グラフです。
2. 試験対策の視点:
・問題文に「同じノード間に複数のエッジが存在」「多重辺を許可する」と出たら、迷わず多重グラフを選択しましょう！
・アルゴリズム分野（ダイクストラ法や隣接行列など）では、前提として「自己ループも多重エッジもない単純グラフ」を扱うことが多いので、両者の前提条件の違いを押さえておくことが重要です。
4. まとめ
同じ頂点（ノード）ペアの間に複数の辺（エッジ）が存在することを許容するデータ構造。これが多重グラフです。多重辺も自己ループも持たない標準的な「単純グラフ」との定義の違いを整理しておきましょう！