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

以你之姓@ 2022-05-20 07:36 131阅读 0赞

## 算法分析（推理过程） ##

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

## 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");
    }