简单图的度序列判定Matlab算法

假设有一个简单图G，我们可以通过判断它的度序列来确定它是否是一个合法的简单图。下面是一个Matlab算法实现：

function isSimpleGraph = isSimpleGraph(degrees)
% 判断给定的度序列是否对应一个简单图
% degrees: 输入的度序列
% isSimpleGraph: 返回布尔值，true表示对应一个简单图，false表示不是

n = length(degrees);  % 获取节点数
sum_degrees = sum(degrees);  % 获取所有节点的度数之和

if mod(sum_degrees, 2) ~= 0
    isSimpleGraph = false;  % 度数和为奇数，不是简单图
    return;
end

% 对度数序列降序排序
degrees = sort(degrees, 'descend');

while true
    if degrees(1) < 0 || degrees(1) >= n
        isSimpleGraph = false;  % 度数不合法，不是简单图
        return;
    end
    
    if degrees(1) == 0
        isSimpleGraph = true;  % 所有节点的度数都为0，是简单图
        return;
    end
    
    % 将最大度数的节点与后面的节点逐一连接，并将度数减1
    for i = 2 : degrees(1) + 1
        degrees(i) = degrees(i) - 1;
        if degrees(i) < 0
            isSimpleGraph = false;  % 度数不合法，不是简单图
            return;
        end
    end
    
    degrees(1) = -1;  % 将最大度数的节点标记为已处理
    
    % 对度数序列重新降序排序
    degrees = sort(degrees, 'descend');
    
    if degrees(1) == -1
        isSimpleGraph = true;  % 所有节点的度数均为0或1，是简单图
        return;
    end
end

算法的思路是，先判断所有节点的度数之和是否为偶数，如果不是则不可能是一个简单图。然后对度数序列进行降序排序，每次将最大度数的节点与后面的节点逐一连接，并将度数减1。如果有节点的度数小于0，则不是简单图；如果有节点的度数大于等于节点数n，则不是简单图。如果所有节点的度数都为0或1，则是简单图。