グラフ理論：ステップごとの解答つき練習問題

1頂点・辺・次数

グラフは、頂点（点）と辺（2 つの頂点を結ぶ線）からなります。単純グラフには、ループも多重辺もありません。

頂点の次数は、その頂点に接する辺の数です。どの辺にも端が 2 つあるので、それぞれの端の次数に 1 ずつ加えます。これが握手補題です：

次の 2 つが導かれます：次数の和は常に偶数であり、奇数次数の頂点の数も偶数です。

• 完全グラフ K_n はすべての頂点の組を結びます：辺は n(n − 1)/2 本です。
• 完全二部グラフ K_m,n は、一方の側のすべての頂点を他方の側のすべての頂点と結びます：辺は m·n 本です。
• n 個の頂点をもつ k 正則グラフには、n·k/2 本の辺があります。

隣接行列は、i と j が結ばれているとき (i, j) 成分が 1 です。無向グラフでは対称で、行の和が次数になり、Mᴸ の (i, j) 成分は i から j への長さ L の歩道の数を表します。

2オイラーとハミルトン

オイラー閉路はすべての辺をちょうど 1 回ずつ通って出発点に戻ります。オイラー路はすべての辺を 1 回ずつ通りますが、別の場所で終わってもかまいません。連結グラフでは次のようになります：

• すべての次数が偶数：オイラー閉路が存在する。
• 奇数次数がちょうど 2 つ：オイラー路が存在し、一方の奇数次数の頂点から他方へ通る。
• 奇数次数が 3 つ以上：どちらも存在しない。

ハミルトン閉路は、すべての頂点をちょうど 1 回ずつ訪れます。これには簡単な次数の判定法はありません。K_n には異なるハミルトン閉路が (n − 1)!/2 個あります：始点を固定し、残りの n − 1 個の頂点を並べ、向きが 2 通りあるので 2 で割ります。

3木

木は、閉路をもたない連結グラフです。n 個の頂点をもつ木には、必ずちょうど n − 1 本の辺があります。どの辺を加えても閉路ができ、どの辺を取り除いても非連結になります。

n 個の頂点に c 本の木からなる森は、n − c 本の辺をもちます。m 本の辺をもつ連結グラフは、m − n + 1 本の辺を取り除いても全域木が残ります。

握手補題から葉の数が分かります：Σ deg = 2(n − 1)。短い形は、次数 d ≥ 3 の頂点について L = 2 + Σ (d − 2) です。次数 3 の頂点が 2 つで、残りがすべて葉の木には、2 + 1 + 1 = 4 枚の葉があります。

4ダイクストラ法と最小全域木

ダイクストラ法は、重みが非負のグラフで、始点からの最短距離を求めます。

1. 始点の距離を 0、ほかのすべての頂点の距離を ∞ とします。
2. 未確定の頂点のうち距離が最小のものを確定します。その距離はこれで最終です。
3. 各隣接頂点 v について、d(v) = min(d(v), d(u) + w(u, v)) と更新します。
4. 目的の頂点が確定するまで繰り返します。

最小全域木は、合計の重みが最小になるようにすべての頂点をつなぎます。クラスカル法は辺を軽い順に並べ、閉路をつくらない辺を順に取ります。プリム法は始点から 1 本の木を成長させ、その木から出る最も軽い辺を常に加えます。どちらも n − 1 本の辺で終わります。

5よくある間違い

• 辺の数を求めるときに、次数の和を 2 で割り忘れる。
• グラフが連結かどうかを確かめずに、オイラー閉路の有無を判定する。
• ダイクストラ法で、暫定距離が最小になる前に頂点を確定してしまう。
• 閉路を確かめずに、軽い方から n − 1 本の辺を取ってしまう。
• K_n のハミルトン閉路の数を (n − 1)!/2 ではなく n! と数える。

6試験問題の例

• やさしい：次数と辺。握手補題を使う、K_n、K_m,n、正則グラフ、木の辺の数を求める、隣接行列を読む、指定された次数の頂点をクリックする、といった問題です。
• ふつう：オイラー路と木。グラフにオイラー閉路やオイラー路があるかを判断する、木の葉を数える、全域木にするために取り除く辺の数を求める、K_n のハミルトン閉路を数える、といった問題です。
• むずかしい：最短経路と全域木。ダイクストラ法を実行する、指定したラウンドで確定する頂点を求める、最小全域木の重みを求める、クラスカル法やプリム法が次に加える辺をクリックする、隣接行列で歩道を数える、といった問題です。