graph - 为什么在找到顶点的度数时自循环计数两次？

Question

在无向图中，自环将两个节点的度数相加。为什么不加一个呢？

标签： graphtheory

Answer 1

考虑一个没有自环的图。假设你看不到它，但你被告知每个节点的度数。你能重现它吗？

在许多情况下，答案是“否”，因为度数不包含有关特定边连接到哪个节点的信息。

所以真正的问题是：我们是否应该关注自环连接到哪个节点，即使我们不关注任何其他类型的边？

从这个角度来看，我认为很明显，为了保持一致，我们必须将自循环视为将两个节点的度数相加。

另一种说法是指出，在没有自环的图中，边的数量正好是所有节点度数之和的一半。如果图表有自环，那真的应该改变吗？同样，我认为很明显答案是否定的。