从给定的节点度构造图形

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未连接到A 的节点的程度.因为degree(B) > 0我们知道degree(C) > 1.因此,有另一个节点D连接到C.因此,我们必须边AB和CD我们可以通过更换EGES AC并BD没有改变nodes'度.

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