从给定的节点度构造图形

Question

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

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

Answer 1

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

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的程度小于节点degree(B) > 0未连接到A的程度。因为degree(C) > 1我们知道D。因此，有另一个节点C连接到AB。所以我们有边缘CD和AC，我们可以用eges BD和handshaking lemma代替，而不改变节点的度数。

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

Answer 2

在这种情况下，Havel/Hakimi或度和公式是必要且充分的条件，因为我们只关心它形成无向图（边的方向无关紧要，但没有关于环或平行边的说法）。因此，选项c和选项d是有效的6顶点无向图。

如果问题要求简单的无向图（不允许循环和平行边），那么我们需要通过qazxswpoi引入算法，这是由@coproc描述的。