Havel, Hakimiの定理をPerlで

今季最後のテストであるのグラフ理論のテストが月曜に控えている。といっても、まだ今の段階ではまったく勉強する気にもならないんだけど、さすがに何もやらないのもアレなので教科書に出てくるHavel, Hakimiの定理をPerlで実装してみた。

Havel, Hakimiの定理は与えられた次数列をもつようなグラフが存在するかどうかの必要十分条件を与える。なんか都合良い解説サイトがあったら参照を貼っとけばいいんだろうけど、ぱっと見つかんないので(Havel Hakimi| ハーベル ハキミ)でぐぐりヨロ。

で、下に書いたhakimiをいう関数は与えられた次数列からグラフを構成できれば真を出来なければ偽を返す。

use warnings;
use strict;

my @degrees = defined @ARGV ? @ARGV : ( 3, 3, 3, 3, 3, 1, );
if(&hakimi(@degrees)) {
    print "A graph can be made from (@degrees)\n";
}
else {
    print "A graph can't be made from (@degrees)\n";
}

sub hakimi {
    my @degrees = sort { $b <=> $a } @_;

    print "(@degrees)\n";

    my $top = shift @degrees;
    if ($top == 0) {
        return 1;
    }
    elsif ($top < 0) {
        return 0;
    }

    if ($top-1 > $#degrees) {
        return 0;
    }
    foreach my $i (0 .. $top-1) {
        $degrees[$i]--;
    }

    return &hakimi(@degrees);
}

id:omochistにネタふったらRubyで書いてくれたりしたので、そのコードを参考にしてブラッシュアップしてみたりも。ていうかRubyだとこういうのすごくきれいに書けていいなぁ。てまぁ、そのへんはコード書いてる人間の技量によるところなんだろうが。

実行すると、こんなかんじ。

$ perl hakimi
(3 3 3 3 3 1)
(3 2 2 2 1)
(1 1 1 1)
(1 1 0)
(0 0)
A graph can be made from (3 3 3 3 3 1)