实验要求：
1.给定一非负整数序列（例如：(4,2,2,2,2)）。
2.判断此非负整数序列是否是可图化的，是否是可简单图化的。
3.如果是可简单图化的，根据Havel定理过程求出对应的简单图，并输出此简单图的相邻矩阵（默认第i行对应顶点vi）。
4.判断此简单图是否是连通的。
5.如果是连通图，判断此图是否是欧拉图。如果是欧拉图，请输出一条欧拉回路（输出形式如：v2->v1->v5->v3->v4->v5->v2）。
--------------------------------------------分割线------------------------------------------------
对于整数序列的定义，这里运用了struct来进行运算，方便后续代码实现
struct k
{
int len;//该点的度数
int num;//该点的编号
int d;//该点的度数，保存不动，方便运算结束后将度数恢复
}a[10000];
可图化的判断：所有顶点的度数和为偶数。
for (int i = 1; i <= n; i++)
{
cin >> s;
int t = s;
while (s < 0|| s !=t)
{
cout << "不能输入负数,小数" << endl;
cin >> s;
}
a[i].len = s;
a[i].num = i;
a[i].d = a[i].len;
sum += a[i].len;
}
if (sum % 2 != 0)
{
cout << "该序列不可图化" << endl;
return 0;
}
可简单图化判断：Havel定理
Havel定理描述
给定一个非负整数序列{d1,d2,…dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。（顶点的度是指与该顶点相铃的顶点数）
可图化的判定比较简单：d1+d2+…dn=0(mod2)。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。
可简单图化的判定，有一个Havel定理，是说: 我们把序列排成不增序，即d1>=d2>=…>=dn，则d可简单图化当且仅当d’=(d2-1, d3-1, … d(d1+1)-1, d(d1+2), d(d1+3), … dn)可简单图化。
原文链接：https://blog.csdn.net/qq_35033987/article/details/78889683）
例如：（4 4 2 2 2 2）可简单图化——>（3 1 1 1 2）可简单图化——>
（3 2 1 1 1）可简单图化——>（1 0 0 1）可简单图化——>（1 1 0 0）可简单图化——>（0 0 0 0）可简单图化
（0 0 0 0）显然可简单图化，故（4 4 2 2 2 2）可简单图化
代码见下：
bool cmp(k x, k y)
{
return x.len > y.len;
}
bool book = 1;//判断是否可简单图化;
int t = n;//t为当前序列元素不为零的个数
for (int i = 1; i <= t; i++)
{
sort(a + i, a + n + 1, cmp);//快排
if (a[i].len == 0)
break;
if (a[i].len > t - i)//若最大元素大于剩余元素个数，即会出现负数
{
book = 0;
break;
}
for (int j = 1; j <= a[i].len; j++)//模拟Havel
{
a[i + j].len--;
c[a[i].num][a[i + j].num] = 1;//c[i][j]=1——>i与j有边
c[a[i + j].num][a[i].num] = 1;
if (a[i + j].len == 0)
t--;
}
}
if (book == 0)
{
cout << "不可简单图化" << endl;
return 0;
}
cout << "可简单图化" << endl;
输出简单图相邻矩阵：直接将 c[n][n] 输出
cout << " " ;
for (int i = 1; i <= n; i++)
{
cout << "v" << i << " ";
}
cout << endl;
for (int i = 1; i <= n; i++)
{
cout << "v" << i << " ";
for (int j = 1; j <= n ; j++)
{
if (c[i][j] == 1)
cout << "1 ";
else
cout << "0 ";
}
cout << endl;
}
判断图是否连通：暴力dfs遍历
void tomako(int x)
{
p[x] = 1;//p[x]=1 ——> x遍历过
for (int i = 1; i <= n; i++)
{
if (p[i] == 1)
continue;
if (c[x][i] == 1)
tomako(i);
}
}
tomako(1);
bool book1 = 1;//可否简单图化标签
for (int i = 1; i <= n; i++)
{
if (p[i] == 0)
{
book1 = 0;
break;
}
}
if (book1 == 0)
{
cout << "不连通" << endl;
return 0;
}
cout << "连通" << endl;
欧拉图定义：
欧拉图是指通过图（ 无向图 或 有向图 ）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。. 具有 欧拉回路 的图称为欧拉图（Euler Graph）
**
无向图G是欧拉图的充分必要条件是G 是连通图并且没有奇数度顶点**
证明：
平凡图显然成立
必要性：图G是欧拉图，证明G中没有奇数度节点
G是欧拉图 ——> G中存在欧拉回路 ——>欧拉回路中每个点每出现在欧拉回路的序列中就必定会获得两个度 ——>欧拉序列中的所有的点必然都是偶数度的节点 ——>不存在奇数度的节点
充分性：
G中没有奇数度的节点，证明G是欧拉图——数学归纳法
假设边数是m
1.m=1，没有奇数度节点——该边只能是一个环——G是欧拉图
2.假设m<=k成立，现在证明m=k+1成立
G连通且没有奇数度顶点——G中必然存在圈——删去圈上的所有的边——假设获得了s个连通分量，每个连通分量有最多k条边，并且都是偶数度的节点（圈上的边每条给顶点贡献两个度）——根据上述的归纳假设每个连通分量都是一个欧拉图——我们现在将圈复原——必然存在一条欧拉回路连接了所有的节点并回到原点（这条回路的主路就是刚才删去的圈，每次进入连通分量的时候，遍历连通分量的欧拉回路在出来继续走圈）
(原文链接：https://blog.csdn.net/ltyqljhwcm/article/details/53232384)
故一个无向图为欧拉图——>无奇数顶点
代码如下：
for (int i = 1; i <= n; i++)
{
if (a[i].d % 2 == 1)//奇度
{
book2 = 0;
break;
}
}
if (book2 == 0)
{
cout << "不是欧拉图" << endl;
return 0;
}
寻找欧拉回路：
有两种方法：Fleury算法， 逐步插入回路法
这里使用逐步插入回路法
1.逐步插入回路法
根据我们上面的证明，我们其实已经得到了一种求解欧拉回路的算法，那就是我们找到了一个圈，我们从圈开始，每次找到一个连通分量就进入走完连通分量的回路，知道我们的主路的圈全部走完，那么我们的走过的序列就是一个欧拉回路
即寻找与当前顶点相关联的顶点，删除两点之间的边，更新主顶点为关联的点。
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
}
若走到尽头（x的度数为零），将x添加进数组，回溯回上个顶点，判断是否有路可走。
完整代码如下：
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
sum1++;
ol[sum1] = a[x].num;//ol[i]为欧拉回路第i个元素的编号
}
该代码可能不太容易理解，可以举个例子画图一步一步跟着代码实现来理解
举例：
本图是一个无向图
1——2 | | | | 3—— | | | | 4————5
如上所示，边为（1,3）（1,2）（2,3）（3,4）（3,5）（4,5）
我们从1开始深搜(随机的，别的情况也会出现，这里模拟最容易看清本质的搜索过程)
1——>2——>3——>1
这时候我们会发现回到原点了，但是显然我们并没并且1走到了死胡同里，算法除了问题吗？
并不是，我们接着看
DFS搜索到1，这时候并没有出边开始执行add *** 作，我们将1节点加入最后的欧拉回路序列
函数递归回溯，3这时有多余的出边指向4，继续递归至顶点4
1——>2——>3——>4——>5——>3
又回到了顶点3这时候，顶点3也没有多余的出边，add 3
1——>2——>3——>4——>5
函数回溯至顶点5，顶点5没有多余的出边，add 5
1——>2——>3——>4
函数回溯至顶点4,4没有多余的出边，add 4
1——>2——>3 add 3
1——>2 add 2
1 add 1
最终结果1 3 5 4 3 2 1 为欧拉回路
通过上面的模拟我们已经可以发现了这个逐步插入回路法的DFS的实现的精髓了
实际上我们第一次搜索会起点的时候，就是找到了一个圈，然后我们函数回溯找每个节点是否还有多余的出边，有多余的出边就从这个入口节点我们就继续递归下去（进入一个连通分量），直到返回到入口节点，直到入口节点没有多余的出边的时候我们这时开始回溯一次回溯连通分量，将连通分量加入结果序列直到将整个圈上的所有的顶点都回溯完之后，返回最开始的起点，欧拉回路查找完毕
（该例子解题过程参考其他文章，原文链接：https://blog.csdn.net/ltyqljhwcm/article/details/53232384）
完整代码：
void tomako1(int x)
{
for (int i = 1; i <= n; i++)
{
if (c[a[x].num][a[i].num] == 1)
{
c[a[x].num][a[i].num] = 0;
c[a[i].num][a[x].num] = 0;
tomako1(i);
}
}
sum1++;
ol[sum1] = a[x].num;//ol[i]为欧拉回路第i个元素的编号
}
for (int i = 1; i < sum1; i++)
cout<<"v"<< ol[i]<<"->";
cout << "v" << ol[sum1];
最后放出全部代码
#include#include #include #include using namespace std; struct k { int len; int num; int d; }a[10000]; int ol[10000];//欧拉回路 int c[100][100];//c[i][j]=1——>i与j有边 int n, sum = 0,sum1=0; bool book2 = 1; int p[10000] = {}; bool cmp(k x, k y) { return x.len > y.len; } void tomako(int x) { p[x] = 1;//p[x]=1 ——> x遍历过 for (int i = 1; i <= n; i++) { if (p[i] == 1) continue; if (c[x][i] == 1) tomako(i); } } void tomako1(int x) { for (int i = 1; i <= n; i++) { if (c[a[x].num][a[i].num] == 1) { c[a[x].num][a[i].num] = 0; c[a[i].num][a[x].num] = 0; tomako1(i); } } sum1++; ol[sum1] = a[x].num;//ol[i]为欧拉回路第i个元素的编号 } int main() { cin >> n; double s; for (int i = 1; i <= n; i++) { cin >> s; int t = s; while (s < 0|| s !=t) { cout << "不能输入负数,小数" << endl; cin >> s; } a[i].len = s; a[i].num = i; a[i].d = a[i].len; sum += a[i].len; } if (sum % 2 != 0) { cout << "该序列不可图化" << endl; return 0; } bool book = 1;//判断是否可简单图化; int t = n;//t为当前序列元素不为零的个数 for (int i = 1; i <= t; i++) { sort(a + i, a + n + 1, cmp);//快排 if (a[i].len == 0) break; if (a[i].len > t - i)//若最大元素大于剩余元素个数，即会出现负数 { book = 0; break; } for (int j = 1; j <= a[i].len; j++)//模拟Havel { a[i + j].len--; c[a[i].num][a[i + j].num] = 1;//c[i][j]=1——>i与j有边 c[a[i + j].num][a[i].num] = 1; if (a[i + j].len == 0) t--; } } if (book == 0) { cout << "不可简单图化" << endl; return 0; } cout << "可简单图化" << endl; cout << " " ; for (int i = 1; i <= n; i++) { cout << "v" << i << " "; } cout << endl; for (int i = 1; i <= n; i++) { cout << "v" << i << " "; for (int j = 1; j <= n ; j++) { if (c[i][j] == 1) cout << "1 "; else cout << "0 "; } cout << endl; } tomako(1); bool book1 = 1; for (int i = 1; i <= n; i++) { if (p[i] == 0) { book1 = 0; break; } } if (book1 == 0) { cout << "不连通" << endl; return 0; } cout << "连通" << endl; for (int i = 1; i <= n; i++) { if (a[i].d % 2 == 1)//奇度 book2 = 0; } if (book2 == 0) { cout << "不是欧拉图" << endl; return 0; } tomako1(1); for (int i = 1; i < sum1; i++) cout<<"v"<< ol[i]<<"->"; cout << "v" << ol[sum1]; return 0; }
以及几个有用的样例：
输入 1
8
2 2 2 2 4 4 4 4
输出 1
输入 2
5
4 2 2 2 2
输出 2
欧拉回路答案不唯一，需自己验证
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）