function [y ShowVecs] = GraphSequenceShowRecursive(DegSeq) %[y ShowVec] = GraphSequenceShowRecursive(DegSeq) %Recursive Algorithm based on the Havel-Hakimi theorem on degree sequences %(Alg. 8.1, in book). %input: DegSeq = a vector of nonnegative integers (in decreasing order) %outputs: y = 0 or 1, will be 1 if there exists a simple graph with degree %sequence as the inputted vector, 0 if not %ShowVecs (optional), a matrix, each row showing the reduction od DegSeq to %the next vector, until the algorithm is completed fprintf('Initial Sequence: (') for i=1:length(DegSeq)-1 fprintf('%d, ',DegSeq(i)) end fprintf('%d)\r', DegSeq(end)) if max(DegSeq) >= length(DegSeq) fprintf('Degrees are too large for the number of vertices'), y = 0; return end d1 = DegSeq(1); n = length(DegSeq); ShowVecs(1,:) = DegSeq; iterCount = 1; while d1 > 0 fprintf('Iteration #%d: (i) (',iterCount) DegSeqNew = DegSeq(2:end); DegSeq = DegSeqNew; DegSeq(1:d1) = DegSeq(1:d1) - 1; for i=1:length(DegSeq)-1 fprintf('%d, ',DegSeq(i)) end fprintf('%d), (ii) (', DegSeq(end)) DegSeq = sort(DegSeq,[2],'descend'); for i=1:length(DegSeq)-1 fprintf('%d, ',DegSeq(i)) end fprintf('%d)\r', DegSeq(end)) %ShowVecs(iterCount, iterCount:n) = DegSeq; ShowVecs(iterCount, 1:iterCount-1) = NaN; iterCount = iterCount + 1; d1 = DegSeq(1); end if min(DegSeq)>=0 y = 1; else y = 0; end