A matlab implementation of Havel-Hakimi algorithm

Tags: ,

In graph theory, degree of a given vertex is the number of vertices which are neighbour to this vertex. Let (d_0, d_1, \ldots , d_n) be a degree sequence then we can check whether it is possible to construct a graph such that the degrees of vertices follows this degree sequence. We call such a degree sequence graphical. The first simple check is to sum all the degree values. This number should even by hand-shakking lemma. This is a necessary condition but not sufficient. For example it is impossible to construct a graph with a degree sequence [3 3 3 1].

Erdős–Gallai theorem gives us necessary and sufficient conditions for this problem.

the sum of the sequence is even and
\sum_{i=1}^{k}d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i,k) \quad \text{for } k \in \{1,\dots,n\}

Suppose the degree sequence is graphical then the following simple procedure construct a possible graph implementation from this given degree sequence.

Pseudocode: Havel-Hakimi

  • Begin with no edges
  • Start residual degree requirement values with the given degree sequence
  • While residual degree requirement of some vertex is non-zero
    • Sort vertices in non-increasing order of residual degree requirement rd_1, rd_2, \ldots rd_n
    • Make an edge between first vertex and the next rd_1 vertices in the previous list
    • Update residual degree requirements

Matlab Code: Havel-Hakimi

function E = mcmc_graph(degree_sequence)

n = size(degree_sequence,2);
% Check if the given degree sequence is graphical
degree_sequence_feasible = 1;
if mod(sum(degree_sequence),2)
    degree_sequence_feasible = 0;
else
    sorted_degree_sequence = sort(degree_sequence,'descend');
    for k=1:n
        temp_sum = 0;
        for i=k+1:n
            temp_sum = temp_sum + min(sorted_degree_sequence(i),k);
        end
        if (sum( sorted_degree_sequence(1:k)) > k*(k-1) + temp_sum )
            degree_sequence_feasible = 0;
        end
    end
end

m = sum(degree_sequence)/2;
E = zeros(m,2);

% Construct an initial graph with Havel-Hakini
if degree_sequence_feasible
    ds = degree_sequence;
    i = 0;
    while sum(ds) > 0
        [residual_degree vertices] = sort(ds,'descend');
        selected_vertices = vertices(2:residual_degree(1)+1);
        E(i+1:i+residual_degree(1),:) = ...
            [repmat(vertices(1),residual_degree(1)) selected_vertices'];
        i = i + residual_degree(1);
        ds(vertices(1)) = ds(vertices(1)) - residual_degree(1);
        ds(selected_vertices) = ds(selected_vertices) - 1;
    end

Comments are closed.