实验题目：可简单图化、连通图、欧拉图和哈密顿图的判断
实验目的：
- 掌握可简单图化的定义及判断方法；
- 掌握连通图、欧拉图的判断方法；
- 掌握欧拉回路的搜索方法；
- 了解欧拉图的实际应用。
实验要求：
- 给定一非负整数序列（例如：(4,2,2,2,2)）。
- 判断此非负整数序列是否是可图化的，是否是可简单图化的。
- 如果是可简单图化的，根据Havel定理过程求出对应的简单图，并输出此图。
- 判断此简单图是否是连通的。
- 如果是连通图，判断此图是否是欧拉图。如果是欧拉图，请输出一条欧拉回路（输出形式如：v2->v1->v5->v3->v4->v5->v2）。
相关知识回顾
可简单图化的判断
方式一：
方式二：
上面的两个定理都是充分必要条件。文章来源：https://www.toymoban.com/news/detail-448471.html
欧拉回路(Euler tour/circuit)
即经过图中所有边的简单回路文章来源地址https://www.toymoban.com/news/detail-448471.html
思路
- 是否可简单图化，利用顶点度数之和为偶数 和 顶点度数位于 0 到 n - 1 之间这两个条件。其中第一个条件是可图化的判定条件。我用上面的第二个充分必要条件判断是否可简单图化，利用Havel定理由度数列得到邻接矩阵。最初求邻接矩阵时遇到了一个Bug，对于 4 4 4 2 2 2这个测试用例，无法自底向上推出相邻矩阵，我觉得原因是顶点的序号在Havel定理的过程中被我打乱了。如果每次都从头开始寻找可以连接的顶点，中间会卡在 4 4 2 2 2那里无法加边，就是说会空出一个孤立顶点和两条边无法加入。所以我把从头遍历改为循环遍历，类似操作系统中首次适应算法改为循环首次适应算法。
- 是否为欧拉图，无向图若是欧拉图，每个顶点的度数都是偶数；
- 是否连通，从一个顶点出发，若是能够遍历所有的顶点，就是连通的；
- 求欧拉回路，从一个顶点出发，每次加入一条没有走过的路径，不能出现环，如果无路可走时所有边都已经走过了并且回到了最初的起点，说明这是一条正确的欧拉回路。
实现代码
/*
1、给定一非负整数序列（例如：(4,2,2,2,2)）。
2、判断此非负整数序列是否是可图化的，是否是可简单图化的。
使用无向相邻矩阵表示该简单图
3、如果是可简单图化的，根据Havel定理过程求出对应的简单图，并输出此图。
4、判断此简单图是否是连通的。
5、如果是连通图，判断此图是否是欧拉图。如果是欧拉图，请输出一条欧拉回路（输出形式如：v2->v1->v5->v3->v4->v5->v2）。
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[11] = {0}; // 存储度数列
int n = 0; // 顶点个数
int graph[11][11]; // 用于存储简单图的邻接矩阵
int visited[11];
int used[11][11]; // 求欧拉回路时是否已经走过
stack<int> path; // 存储欧拉回路
int m = 0; // 边的数量
int curEdge = 0;
bool cmp(int t1, int t2)
{
return t1 >= t2;
}
// 判断是否可图化和可简单图化，可图化返回1，可简单图化返回2，不可图化返回0
int isGraphic()
{
int sum = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] < 0) // 负数不可图化
{
return 0;
}
sum += a[i];
}
if (sum % 2 == 0) // 可图化
{
if (n - 1 >= a[1] && 0 <= a[n]) // 可简单图化的第二个判断
{
int left = 0;
int right = 0;
int flag = true;
for (int r = 1; r <= n - 1; ++r)
{
left += a[r];
right = r * (r - 1);
for (int j = r + 1; j <= n; ++j)
{
right += min(r, a[j]);
}
if (left > right)
{
flag = false;
break;
}
}
if (flag == true)
{
return 2;
}
else
{
return 1;
}
}
else // 不可简单图化,返回1
{
return 1;
}
}
else // 不可图化，返回0
{
return 0;
}
}
// 用Havel定理判断邻接矩阵，自顶向下
void isGraphicHavel(int c[11], int len) // 传入度数列c[11],以及顶点个数len,
{
int b[11] = {0};
int j = 1;
for (int i = 2; i <= c[1] + 1; ++i)
{
b[j++] = c[i] - 1;
}
for (int i = c[1] + 2; i <= len; ++i)
{
b[j++] = c[i];
}
sort(b + 1, b + 1 + len - 1, cmp); // 降序排序
// cout << "c[i]: " << endl;
// for (int i = 1; i <= len; ++i)
// {
// cout << c[i] << " ";
// }
// cout << endl;
// cout << "b[i]: " << endl;
// for (int i = 1; i <= len - 1; ++i)
// {
// cout << b[i] << " ";
// }
// cout << endl;
int flag = true; // 判断是否到最底层，即全部为孤立点
for (int i = 1; i <= len - 1; ++i)
{
if (b[i] != 0)
{
flag = false;
break;
}
}
if (!flag) // 继续往下求一层
{
isGraphicHavel(b, len - 1);
}
int temp[11];
copy(c, c + 11, temp); // c的临时数组，防止影响上一层
// 对底层度数列b[11]的相邻矩阵添加本层c[11]新的顶点和边
// 这段代码在测试4 4 4 2 2 2这个样例时无法正常运行，因为在4 4 2 2 2时无法向上变成4 4 4 2 2 2
// ，最后会空出一个孤立点无法加边，因为不能有平行边
// 将首次适应算法改为循环首次或许更好
int start = 1;
for (int i = 1; i <= len; ++i)
{
while(temp[i] > b[i]) // 需要添加新的边，需要改变两个值
{
int num = 0;
for (int j = start; num < len && temp[i] > b[i]; j = (j == len) ? 1 : j + 1)
{
num++;
if (i != j && graph[i][j] != 1){ // 不能有环和平行边
if (temp[j] > b[j]) // 该顶点也需要新加一条边
{
graph[i][j] = 1;
graph[j][i] = 1;
temp[i]--;
temp[j]--;
start = (j == len) ? 1 : j + 1; // 指针指向下一个点而不是第一个点
}
}
}
}
}
// cout << "邻接矩阵：" << endl;
// for (int i = 1; i <= n; ++i)
// {
// for (int j = 1; j <= n; ++j)
// {
// cout << graph[i][j] << " ";
// }
// cout << endl;
// }
}
// 判断是否是欧拉图，是返回1，不是返回0
int isEuler()
{
// 如果是欧拉图，所有顶点度数为偶数
for (int i = 1; i <= n; ++i)
{
if (a[i] % 2 != 0)
{
return 0;
}
}
return 1;
}
// dfs遍历二位数组中所有的点
void dfs(int t)
{
for (int i = 1; i <= n; ++i)
{
if (visited[i] == 0 && graph[t][i] == 1) // i没有访问过，顶点t和i之间有边
{
visited[i] = 1;
dfs(i);
}
}
}
// 根据邻接矩阵判断是否是连通图
bool isConnected()
{
// 先排除有孤立点的
if (n == 1)
{
return false;
}
for (int i = 1; i <= n; ++i)
{
if (a[i] == 0)
{
return false;
}
}
// 从v1开始搜索
visited[1] = 1;
dfs(1);
for (int i = 1; i <= n; ++i)
{
if (visited[i] == 0) // 有顶点没有访问到
{
return false;
}
}
return true;
}
bool EulerCircuit(int v) // 返回值代表能否走通
{
// 先计算边数，用栈存储已经经过的顶点，如果没有走完就无路可走，或者回不到起点了，就弹出栈顶的顶点
// 对于每一个顶点，利用邻接矩阵，一次尝试每个邻接的顶点
int flag = false; // 能否走通的标志
for (int i = 1; i <= n && !flag; ++i)
{
if (graph[v][i] == 1 && used[v][i] == 0) // 没走过的路
{
used[v][i] = 1; // 标记已经走过了
used[i][v] = 1;
path.push(i);
curEdge++;
flag = true;
if (!EulerCircuit(i)) // 不能继续走下去
{
flag = false;
used[v][i] = 0; // 标记已经走过了
used[i][v] = 0;
path.pop();
curEdge--;
}
}
}
if (!flag) // 已经无路可走了
{
if (v == 1 && curEdge == m) // 回到了起点并且边都走遍了
{
return true;
}
else // 上次走的不对
{
return false;
}
}
else
{
return true;
}
}
int main()
{
while (true)
{
memset(graph, 0, sizeof(graph));
memset(a, 0, sizeof(a));
memset(visited, 0, sizeof(visited));
memset(used, 0, sizeof(used));
m = 0;
curEdge = 0;
cout << "请输入顶点个数：" << endl;
cin >> n; // 输入顶点个数
cout << "请输入度数列，降序输入，以空格作为间隔：" << endl;
for (int i = 1; i <= n; ++i) // 输入度数列，降序输入，第一个位置不存数据
{
cin >> a[i];
}
int t1 = isGraphic();
if (t1 == 0)
{
cout << "不可图化" << endl;
}
else if (t1 == 1)
{
cout << "可图化" << endl;
}
else
{
cout << "可简单图化" << endl;
isGraphicHavel(a, n); // 根据Havel定理求简单图的邻接矩阵
cout << "邻接矩阵：" << endl;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
cout << graph[i][j] << " ";
}
cout << endl;
}
// 判断是否连通
if (isConnected())
{
cout << "连通图" << endl;
if(isEuler())
{
cout << "欧拉图" << endl;
// 利用握手定理求边数
for (int i = 1; i <= n; ++i)
{
m += a[i];
}
m = m / 2;
path.push(1); // 先从v1开始
EulerCircuit(1);
cout << path.top();
path.pop();
while(!path.empty())
{
cout << "->" << path.top();
path.pop();
}
cout << endl;
}
else
{
cout << "非欧拉图" << endl;
}
}
else
{
cout << "非连通图" << endl;
}
}
}
return 0;
}
到了这里，关于离散数学实验一的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
