Pythonで指定された頂点の次数が木（ツリー）を表すかグラフを表すかを判定する方法

問題の概要

いくつかの頂点に対する次数（degree）のリストが与えられたとき、そのリストが木（ツリー）を表しているのか、それとも一般的なグラフを表しているのかを判定する問題を考えます。

例えば、入力として deg = [2,2,3,1,1,1] が与えられた場合、出力は「Tree」となります。

判定のアルゴリズム

この問題は、次の手順で解くことができます。

• vert: 頂点の数を取得する
• deg_sum: すべての頂点の次数の合計を計算する
• もし 2 × (vert − 1) が deg_sum と等しければ「Tree」を返す
• そうでなければ「Graph」を返す

この判定が成り立つ理由

グラフ理論における握手の補題（Handshaking Lemma）によると、グラフのすべての頂点の次数の総和は、辺の数のちょうど2倍になります。一方、木とは連結かつ閉路（サイクル）を持たないグラフであり、n 個の頂点を持つ木の辺の数は必ず n − 1 本です。

したがって、次数の合計が 2 × (n − 1) と一致すれば、そのグラフは n − 1 本の辺を持つことになり、木であると判定できます。逆に一致しない場合は木にはなり得ないため、「Graph」と判定されます。

サンプルコード

理解を深めるために、以下のPythonの実装を見てみましょう。

def solve(deg):
    vert = len(deg)
    deg_sum = sum(deg)
    
    if 2 * (vert - 1) == deg_sum:
        return 'Tree'
    return 'Graph'

deg = [2, 2, 3, 1, 1, 1]
print(solve(deg))

入力

[2,2,3,1,1,1]

出力

Tree