A degree sequence is a non-decreasing sequence \((d_1\leq \cdots\leq d_n)\) of positive integers such that there is a graph whose vertices are labelled with \(1,\ldots,n\) with \(\deg(i) = d_i\). Erdős–Gallai theorem gives a necessary and sufficient condition that a given non-increasing sequence is a degree sequence. However, there is a very simple recursive algorithm called Havel–Hakimi algorithm that determines if a given non-increasing sequence is a degree sequence. Today, I’ll implement Havel-Hakimi in common lisp.
Here is my implementation:
(defun havel-hakimi (xs)
(cond
((null xs) t)
((oddp (reduce #'+ xs)) nil)
(t (havel-hakimi (delete 0 (sort (mapcar #'-
(cdr xs)
(append (loop repeat (car xs) collect 1)
(loop repeat (- (length xs) (car xs) 1) collect 0)))
#'<))))))HAVEL-HAKIMIAnd here are some tests:
(havel-hakimi '(3 3 3 3))
(havel-hakimi '(1 2 3 4))T
NILHere is a large sequence to test:
(havel-hakimi '(1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 5 5 6))T