algorithm - 从给定的节点度数构造图

我必须找出以下哪些值可以是具有 6 个顶点的无向图的度数:

a) 3 2 2 2 3 3
b) 4 2 2 2 3 2
c) 5 2 2 2 0 3
d) 5 2 2 2 1 2

我找到的唯一方法是尝试在一张纸上绘制图形，然后检查是否可能。
如果可能的话，我只需要一个提示来开始这个问题，而不是绘制每个图形。

最佳答案

以下算法决定是否可以用给定的节点度数构造一个简单的图:

按降序对度数进行排序

如果第一个度数为 0(即所有度数为 0)，那么显然可以形成这样的图(没有边)，您就完成了。

如果第一个度数的值是 d (> 0) 那么下面的 d 度数必须大于 0。如果不是，你就完成了:不能形成这样的图。

去掉第一个度数(值 d )并将后面的 d 度数减少一个(即，将请求的边数从最高度数的节点绘制到其余节点中度数最高的节点 - 请参见下面的证明以了解其正确性假设)，然后继续第 1 步(现在少一个节点)

示例 a)(可能会因为权重和为奇数而被拒绝，但上述算法也有效)

3 2 2 2 3 3
3 3 3 2 2 2
  2 2 1 2 2
  2 2 2 2 1
    1 1 2 1
    2 1 1 1
      0 0 1
      1 0 0
        -1   not possible

示例 c)

5 2 2 2 0 3
5 3 2 2 2 0
  2 1 1 1 -1   not possible

例子 d)

5 2 2 2 1 2
5 2 2 2 2 1
  1 1 1 1 0
    0 1 1 0
    1 1 0 0
      0 0 0  ok

缺少的是一个证明，如果一个图可以用给定的节点度数绘制，那么匹配的图之一具有第 4 步的属性，即具有最高度数的节点与具有次高度数的节点相连。

因此，让我们假设 A 是度数最高的节点，并且它与节点 B 相连，该节点的度数小于节点 C 未连接到 A 的度数。由于 degree(B) > 0 我们知道 degree(C) > 1 。因此还有另一个节点 D 连接到 C 。所以我们有边 AB 和 CD，我们可以用 eges AC 和 BD 替换它们，而不会改变节点的度数。

通过重复这个过程足够多的次数，我们可以让所有次高度数的节点都连接到度数最高的节点。

关于algorithm - 从给定的节点度数构造图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14736909/