無向グラフ

無向グラフは、頂点の集合Vと、向きを持たない辺の集合Eで対象間の対称な関係を表すグラフです。辺$\{u,v\}$はuからvとvからuを区別せず、友人関係や双方向道路などを表します。

■ 試験で押さえるポイント

• 頂点vに接続する辺の本数を次数deg(v)とし、全頂点の次数の和は各辺を両端で二度数えるため$\sum_v\deg(v)=2|E|$です。

• 辺の重複と自己ループを認めないものを単純グラフと呼びます。自己ループは次数へ2を加えるなど、問題のグラフ定義を確認します。

• 頂点間を辺でたどれる列が道で、全頂点間に道があれば連結です。連結でない場合は互いに到達可能な連結成分へ分かれます。

• 隣接行列は無向グラフでは対称になり、隣接リストなら空間量は$O(|V|+|E|)$です。疎なグラフでは隣接リストが適します。

■ 選択肢での判断ポイント

辺に向きがなく、次数和が$2|E|$、隣接行列が対称という性質が手掛かりです。有向グラフの入次数・出次数とは区別します。

例: 頂点A、B、Cに辺AB、AC、BCがある三角形では各次数は2、次数和は6で、$2\times3=6$と一致します。