基礎理論グラフ理論

無向グラフにおいて「次数（degree）」の説明として正しいものはどれか。

ア.最短経路の長さのことである。

イ.グラフ全体の辺の総数のことである。

ウ.あるノードに接続されている辺の本数のことである。正解

エ.グラフが連結かどうかを示す指標のことである。

解説

次数は「その人が持っている名刺の枚数」。友人が多い人ほど次数が高い、社交的なノードの指標です。

なぜウが正解か

無向グラフの「次数」とは、あるノードに接続されている辺（エッジ）の本数のことです。たとえばノードAに3本の辺がつながっていれば、Aの次数は3です。グラフ理論の重要な定理「握手補題」では「全ノードの次数の合計 = 辺の本数 × 2」が成り立ちます。

なぜアは間違いか

最短経路の長さは「距離（distance）」と呼ばれ、ダイクストラ法などで求めます。次数は経路の長さではなく、ノードにつながる辺の本数です。

なぜイは間違いか

グラフ全体の辺の総数は「辺数」または「|E|」と呼びます。次数はグラフ全体でなく個々のノードに対して定義される局所的な値です。

なぜエは間違いか

グラフが連結かどうかを示す概念は「連結性（connectivity）」です。次数は接続された辺の数であり、グラフ全体の連結性とは別の概念です。

出典: AI生成問題（学習用）

← 前の問題

2つのベクトル a = (3, 4) と b = (1, -2) の内積 a·b の値はどれか。

次の問題 →

ハフマン符号の特徴として最も適切なものはどれか。