【アルゴリズム】すべてのペアが直接つながる！「完全グラフ」｜情報処理問題1000本ノック
アルゴリズムや離散数学における「グラフ理論」。すべての頂点間に枝（エッジ）が存在する「完全グラフ」の構造と、試験でよく問われるエッジ数の計算公式を攻略しましょう。
1. 【 問題 】：アルゴリズムとデータ構造（グラフ理論）
【 問題 】 グラフ理論における無向グラフの構造に関する記述です。含まれるすべての異なる2頂点のペアの間に、必ず1本の枝（エッジ）が存在する（すべての頂点が互いに直接結ばれている）グラフを何と呼ぶでしょうか？
（ア）完全グラフ（Complete Graph）
（イ）連結グラフ（Connected Graph）
（ウ）平面グラフ（Planar Graph）
（エ）二部グラフ（Bipartite Graph）
2. 正解：
正解：（ア）完全グラフ（Complete Graph）
3. 解説：「全員が全員と友達！密度の極限グラフ」
完全グラフ（Complete Graph）は、頂点の集合において「これ以上枝を追加できない」限界まで枝が張られたグラフ構造です。
頂点数が $N$ 個の完全グラフは通常 $K_N$ と表記されます。たとえば、頂点数3の完全グラフ（$K_3$）は三角形、頂点数4（$K_4$）は対角線を含む四角形（四面体の展開図のような形）になります。
頂点数が N 個の完全グラフにおける枝（エッジ）の総数 E は、以下の公式で求められます。
【例】頂点数が 5個（N=5）の完全グラフのエッジ数：
E = 5 × (5 - 1) / 2 = 10本 （※組み合わせ ₅C₂ の計算と同じ）
1. 理解のコツ: 「総当たり戦（リーグ戦）」に例えてみましょう。
・参加チームを「頂点」、対戦試合を「枝（エッジ）」と考えます。
・完全グラフとは、「全員が他のすべてのチームと1回ずつ対戦する総当たり戦」の対戦表そのものです。5チームで総当たり戦を行うと全10試合になりますが、これがそのまま枝の数になります。
2. 試験対策の視点: 基本情報技術者試験や応用情報技術者試験のテクノロジ系（離散数学・アルゴリズム）で出題されます。
用語の定義問題として「すべての頂点間に枝がある」と問われたら即座に完全グラフを選びましょう。
また、「頂点数 N の完全グラフの枝の数はいくつか？」という計算問題も多いため、$N(N-1)/2$ の計算式を頭に入れておくと一瞬で解けます。
4. まとめ
「すべての頂点ペアの間に枝が存在するグラフ」。これが完全グラフです。用語の意味に加えて、枝の総数を求める公式 N(N-1)/2 とセットで完璧に記憶しておきましょう！