algorithm - 对于图，给定一个顶点有一个循环，为什么该顶点的度取为 2 而不是 1？

Question

我正在阅读 Kenneth H. Rosen 的一本名为“离散数学及其应用”的书。书中对无向图顶点度的定义如下:

“无向图中顶点的度数是与其关联的边数，除了顶点处的循环对该顶点的度数贡献两倍。顶点 v 的度数表示为 deg(v )。”

我有点困惑，为什么如果有循环，顶点的度数取2而不是1。这是什么原因？如果我们想跟踪图中边的数量，难道我们不应该将其设为 1 而不是 2 吗？

Answer 1

这与编程关系不大，与数学关系很大(有人会说两者之间的区别有些武断)。

我的看法是，以这种方式定义它更简单，并且在有向图的一般情况下更一致。假设您有一个有向图数据结构，具有传入和传出边:

struct Node {
   int id;
   vector<Edge> outgoing;
   vector<Edge> incoming;
}

按照书上的定义，

int degree(const Node &node) {
  return outgoing.size() + incoming.size();
}

使用替代定义(不计算两次循环)，您需要为传入和传出的边做一个特殊情况。