确定度序列是否可以形成简单图 | Havel-Hakimi 算法
图论中的度链表示顶点度的顺序。确定度顺序是否可以产生简单图或没有平行或自循环边的图至关重要。我们将在本博客中研究解决此问题的三种方法，重点介绍 Havel-Hakimi 算法。我们将介绍每种技术使用的算法，提供带有适当标题的相关代码表示，并展示每种方法的独特结果。
使用的方法
Havel-Hakimi 算法
排序和检查
直接计数
Havel-Hakimi 算法
Havel-Hakimi 算法是一种流行的技术，用于确定度序列是否可以产生简单的图形。在达到初始情况之前，度数一次被消除。
算法
使用以下算法按降序排列度数系列。
如果度数链为零（创建简单图），则返回 true。
如果初始度数不利或高于余数度数之和，则返回 false（无法形成简单图）。
从列表中减去初始度数。
从以下"k"度数中减去 1，其中"k"是已删除度数的值。
再次从步骤 1-5 执行。
示例
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool havelHakimi(vector<int>& degrees) {
sort(degrees.rbegin(), degrees.rend()); // 按非升序排序
while (!degrees.empty() && degrees.front() > 0) {
int firstDegree = degrees.front();
degrees.erase(degrees.begin()); // 删除一级
if (firstDegree > degrees.size()) {
return false;
}
for (int i = 0; i < firstDegree; ++i) {
degrees[i]--;
}
sort(degrees.rbegin(), degrees.rend()); // 重新排序顺序
}
return degrees.empty(); // 如果序列为空，则返回 true
}
int main() {
// 测试 havelHakimi 函数
vector<int> degrees = {3, 1, 2, 3, 1, 0};
bool result = havelHakimi(degrees);
if (result) {
cout << "该序列可以表示有效图形。" << endl;
} else {
cout << "该序列无法表示有效图形。" << endl;
}
return 0;
}
输出
该序列无法表示有效图形。
排序和检查
第二种方法是按非递减顺序对度数系列进行排序，并反复确定是否满足简单图形的先决条件。
算法
使用以下算法按降序对度数系列进行排序。
对系列中的每个度数重复此过程。
如果当前级别不利或数量超过可用度数，则返回 false。
如果每个度数都通过测试，则返回 true（它会创建一个简单的图表）。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool havelHakimiAlgorithm(vector<int>& degrees) {
// 按非递增顺序对度数序列进行排序
sort(degrees.rbegin(), degrees.rend());
while (!degrees.empty() && degrees[0] > 0) {
int highestDegree = degrees[0];
int n = degrees.size();
// 检查最高度数是否大于剩余顶点数
if (highestDegree >= n) {
return false;
}
// 删除最高度数顶点
degrees.erase(degrees.begin());
// 减少其邻居的度数
for (int i = 0; i < highestDegree; ++i) {
degrees[i]--;
}
// 再次对度数序列进行排序
sort(degrees.rbegin(), degrees.rend());
}
// 如果所有度数均为零，则度数序列可以形成一个简单的图
return degrees.empty();
}
int main() {
// 度数序列示例
vector<int> degrees = {3, 3, 2, 2, 1};
// 检查度数序列是否可以形成简单图
bool canFormGraph = havelHakimiAlgorithm(degrees);
if (canFormGraph) {
cout << "度数序列可以形成简单图。" << endl;
} else {
cout << "度数序列无法形成简单图。" << endl;
}
return 0;
}
输出
度数序列无法形成简单图。
直接计数
第四种方法只是测量满足预定标准的级别数，以确定序列是否可以表示为简单图。
算法
确定大于或等于 0 的度数并将结果保存在"n"中。
如果"n"为奇数（无法形成简单图形），则返回 false。
测量大于左度数的非零度数并将其保存在"k"中。
如果"k"高于左度数，则返回 false。
如果满足所有要求（创建基本图形），则返回 true。
示例
#include <iostream>
#include <vector>
using namespace std;
bool directCount(vector<int>& degrees) {
int n = 0;
int k = 0;
for (int degree : degrees) {
if (degree >= 0) {
n++;
if (degree > degrees.size() - n) {
k++;
}
}
}
return (n % 2 == 0) && (k <= n);
}
int main() {
// 测试 directCount 函数
vector<int> degrees = {3, 1, 2, 3, 1, 0};
bool result = directCount(degrees);
if (result) {
cout << "该序列可以表示一个有效的图形。" << endl;
} else {
cout << "该序列不能表示一个有效的图形。" << endl;
}
return 0;
}
输出
该序列可以表示一个有效的图形。
结论
在这篇文章中，我们研究了三种不同的方法来确定特定度数序列是否可以产生一个简单的图形。我们讨论了 Havel-Hakimi 算法，该算法采用逐步减少的方法来确定图形的形成是否可行。我们还研究了度数组方法、直接计数方法以及排序和检查方法，每种方法都有不同的策略来验证基本图的条件。通过理解和使用这些技术，您可以快速确定是否可以从特定度序列创建图。所选方法将取决于当前度序列的特定规格和特征。
