3

我必须找出以下哪个值可以是具有 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

我发现的唯一方法是尝试在一张纸上绘制图表，然后检查是否可行。如果可能的话，我只需要一个提示来启动这个问题，而不是绘制每个图表。

4

2 回答 2

12

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

  1. 按降序排列度数

  2. 如果第一个度数是 0（即所有度数都是 0），那么显然可以形成这样的图（没有边），你就完成了。

  3. 如果第一个度数具有值d（> 0），则以下d度数必须大于 0。如果不是，则完成：无法形成这样的图。

  4. 去掉第一个度数（值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不用改变节点的度数。

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

于 2013-02-06T19:41:37.597 回答
2

在这种情况下，握手引理或度求和公式是充要条件，因为我们只关心它是否形成了一个无向图（边的方向无关紧要，但没有提到循环或平行边）。因此，选项 c 和选项 d 是有效的 6 顶点无向图。

如果问题要求简单的无向图（不允许循环和平行边），那么我们需要引入Havel/Hakimi的算法，如 @coproc 所述。

于 2013-02-07T04:28:16.447 回答