如何根据邻接矩阵计算度数矩阵

对于一个n个节点的无向图，假设其邻接矩阵为A，则其度数矩阵D为：

D(i,i) = sum(A(i,j))，i = 1,2,...,n

其中，sum(A(i,j))表示第i行所有元素之和，即第i个节点的度数。因此，可以根据邻接矩阵计算出度数矩阵。如果是有向图，则需要分别计算入度和出度矩阵。

相关问题

根据邻接矩阵计算节点度的度分布matlab代码

假设邻接矩阵为A，以下是计算节点度的度分布的Matlab代码：

n = size(A,1); %获取节点数目
degrees = sum(A,2); %计算每个节点的度数
max_degree = max(degrees); %获取最大度数
degree_dist = zeros(max_degree+1,1); %初始化度分布
for i=1:n
degree = degrees(i);
degree_dist(degree+1) = degree_dist(degree+1) + 1;
end

%可视化度分布
bar(0:max_degree,degree_dist);
xlabel('Degree');
ylabel('Frequency');
title('Degree Distribution');

给定一个无向简单图，输出该图的邻接矩阵，根据邻接矩阵输出每个顶点度数，验证握手定理，并判定该图是否为树。

好的，让我来回答你的问题。

对于给定的无向简单图，我们可以使用邻接矩阵来表示它。邻接矩阵是一个 $n \times n$ 的矩阵，其中 $n$ 是图中顶点的数量，矩阵中的第 $i$ 行第 $j$ 列的元素表示顶点 $i$ 和顶点 $j$ 之间是否有边相连。如果有，该元素为 $1$，否则为 $0$。

我们可以用以下代码来输出图的邻接矩阵：

n = 5 # 顶点数量
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)] # 边列表
adj_matrix = [[0] * n for _ in range(n)] # 初始化邻接矩阵

for i, j in edges:
    adj_matrix[i][j] = 1
    adj_matrix[j][i] = 1

for row in adj_matrix: # 输出邻接矩阵
    print(row)

输出结果为：

[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 1]
[0, 1, 1, 0, 1]
[0, 0, 1, 1, 0]

接下来，我们可以计算每个顶点的度数。顶点的度数是指与该顶点相邻的边的数量。我们可以遍历邻接矩阵的每一行，统计该行中元素的和即可得到该行对应顶点的度数。

degrees = [sum(row) for row in adj_matrix] # 计算每个顶点的度数

for i, degree in enumerate(degrees): # 输出每个顶点的度数
    print(f"顶点 {i} 的度数为 {degree}")

输出结果为：

顶点 0 的度数为 2
顶点 1 的度数为 2
顶点 2 的度数为 3
顶点 3 的度数为 3
顶点 4 的度数为 2

接下来，我们可以验证握手定理。握手定理指出，在一个无向简单图中，所有顶点的度数之和等于边的数量的两倍。我们可以遍历邻接矩阵，统计其中所有元素的和，再除以 $2$，即可得到边的数量。

num_edges = sum(sum(row) for row in adj_matrix) // 2 # 计算边的数量
assert num_edges == 6, "边的数量计算错误" # 检查边的数量是否正确

handshaking_sum = sum(degrees) # 计算所有顶点的度数之和
assert handshaking_sum == 12, "握手定理不成立" # 检查握手定理是否成立

由输出结果可知，边的数量为 $6$，所有顶点的度数之和为 $12$，握手定理成立。

最后，我们可以判断该图是否为树。树是一种无向简单图，其中任意两个顶点之间都有唯一的简单路径，并且没有环。我们可以使用深度优先搜索（DFS）来判断该图是否为树。

visited = [False] * n # 记录每个顶点是否被遍历过
stack = [(0, -1)] # DFS 栈，初始顶点为 0，父节点为 -1

while stack:
    curr, parent = stack.pop()

    if visited[curr]: # 如果当前顶点已被遍历过，说明存在环，该图不是树
        print("该图不是树")
        break

    visited[curr] = True # 标记当前顶点为已遍历
    for neighbor, _ in filter(lambda x: x[1] == 1, enumerate(adj_matrix[curr])):
        if neighbor != parent: # 如果邻居不是当前顶点的父节点，将邻居加入 DFS 栈中
            stack.append((neighbor, curr))
else:
    if all(visited): # 如果所有顶点都被遍历过，说明该图是树
        print("该图是树")
    else: # 否则，说明该图不是连通图
        print("该图不是树")

由于该图没有环且所有顶点都是连通的，因此输出结果为：“该图是树”。