可简单图化算法(Havel算法)

算法分析（推理过程）

• 首先，我们很容易通过握手定理（所以点的度数加起来是偶数）知道，对应的度序列是否可图化。
• 在确定了可图化之后。但是担心会出现不可简单图化的情况。
• 我们只需要对于这种可能进行讨论就好了。
• 在可图化，但是不可简单图化的这种图中，就是因为会出现一些点上，一定会出现环（或者重边）的情况
• 所以，我们只需要确定了一个固定的顺序，这样就可以解决掉这里重边的情况。（在操作系统中，关于解决死锁的时候，也用了类似的一个解决方案来破掉死锁的条件之一 —— 循环等待）。然后只允许前面的点与后面的点来构建边，在这样的边建立完成之后，就不允许反过来的操作（这样就避免重边 情况）
• 所以，关键还是在环路的这种情况上。有环是怎么一回事呢？就是在前面的点，在合理的与（顺序在其后面的）点相连之后，任然剩下度没有能解决掉。这样的剩下来的度，岂不就是必须由环来提供。所以，只需要保证这样的点不存在就好了。
• 注意，这里我们使用了前面已知的有序性。（这里有序性就直接用度的有序性来做就好了（从大到小））
• 保证了上面的有序性还有一个作用，因为度大的点更有可能满足条件。。（否则会出现负的情况）。
• 证明到这里，其实已经可以确定了上面的算法是可以确定一个充分条件，至于是不是必要条件，这个似乎还有待考究。
• 而仔细再推理一下，就会发现，其实这其实也是一个必要条件
• 因为，出现矛盾的情况，就是通过上面的排好序之后再选出来，结果判断的是不可简单图化，但是我们可以找到一个简单图来描述。因为用排好序之后，顺着减的话，减的都是在每一轮中比较大的那些。如果这些比较大的点最后都是出现了不能瞒住的情况，那么后面的用随机选点来减的这种情况就更不可能实现了。（注意这个逻辑）

C++代码实现

核心代码：

int *a, N;
bool Havel() {
    for (int i = N - 1; i >= 0; --i) {
        sort(a, a + i+1); // sort the list
        if (!a[i]) break;
        for (int j = i - 1; j >= 0 && a[i]; j--) {
            a[j]--; a[i] --;
            if (a[j] < 0) return false;
        }
        if (a[i] > 0) return false; // 任然有剩余
    }
    return true;
}

解释：

• 在上面的算法中，用系统自带的排序。默认是从小到大来排序，所以，上面都是从后面来数的。
• 第一个判断： if (!a[i]) break; 表示，目前剩下的所有点的度都是0（在输入的时候就保证了所有度都是大于等于0的）
• 之后的for循环会最大的那些点都做处理，一直到a[i] == 0为止。
• 一旦出现了减完之后，后面的某些点变成了负数了，那么说明就一定有问题了。否则就是可以继续。
• 但是结束之后剩余还有度数的话，就说明必有环了。 if (a[i] > 0) return false; // 任然有剩余

#include <iostream>
using namespace std;
#include <algorithm>
int *a, N;
bool Havel() {
    for (int i = N - 1; i >= 0; --i) {
        sort(a, a + i+1); // sort the list
        if (!a[i]) break;
        for (int j = i - 1; j >= 0 && a[i]; j--) {
            a[j]--; a[i] --;
            if (a[j] < 0) return false;
        }
        if (a[i] > 0) return false; // 任然有剩余
    }
    return true;
}
int main() {
    cin >> N;
    _ASSERT(N > 0);
    a = new int[N];
    int temp = 0; 
    bool gama = true;
    for (int i = 0; i < N; ++i) {
        cin >> a[i]; 
        gama &= (a[i] >= 0);
        temp += a[i];
    }
    if (!gama || temp % 2 || temp <= 0)
        cout << false<< endl;
    else 
        cout << Havel() << endl;
    delete[] a;
    system("pause");
}