【离散数学】无向欧拉图的判定 （c++）_用c写判断是不是欧拉图-程序员宅基地
实验要求：
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<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
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
欧拉回路答案不唯一，需自己验证
智能推荐
分享11个web前端开发实战项目案例+源码_前端项目实战案例-程序员宅基地
文章浏览阅读4.1w次，点赞12次，收藏193次。小编为大家收集了11个web前端开发，大企业实战项目案例+5W行源码！拿走玩去吧！1）小米官网项目描述：首先选择小米官网为第一个实战案例，是因为刚开始入门，有个参考点，另外站点比较偏向目前的卡片式设计，实现常见效果。目的为学者练习编写小米官网，熟悉div+css布局。学习资料的话可以加下web前端开发学习裙：600加上610再加上151自己去群里下载下。项目技术：HTML+CSS+Div布局2）迅雷官网项目描述：此站点特效较多，所以通过练习编写次站点，学生可以更多练习CSS3的新特性过渡与动画的实_前端项目实战案例
计算质数-埃里克森筛法（间隔黄金武器）-程序员宅基地
文章浏览阅读73次。素数，不同的质数，各种各样的问题总是遇到的素数。以下我们来说一下求素数的一种比較有效的算法。就是筛法。由于这个要求得1-n区间的素数仅仅须要O（nloglogn）的时间复杂度。以下来说一下它的思路。思路：如今又1-n的数字。素数嘛就是除了1和本身之外没有其它的约数。所以有约数的都不是素数。我们从2開始往后遍历，是2的倍数的都不是素数。所以我们把他们划掉然后如...
探索Keras DCGAN：深度学习中的创新图像生成-程序员宅基地
文章浏览阅读532次，点赞9次，收藏14次。探索Keras DCGAN：深度学习中的创新图像生成项目地址:https://gitcode.com/jacobgil/keras-dcgan在数据驱动的时代，图像生成模型已经成为人工智能的一个重要领域。其中，Keras DCGAN 是一个基于 Keras 的实现，用于构建和训练 Deep Convolutional Generative Adversarial Networks（深度卷积生...
org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):_spring-could org.apache.ibatis.binding.bindingexce-程序员宅基地
文章浏览阅读116次。今天在搭建springcloud项目时，发现如上错误，顺便整理一下这个异常：1. mapper.xml的命名空间（namespace）是否跟mapper的接口路径一致<mapper namespace="com.baicun.springcloudprovider.mapper.SysUserMapper">2.mapper.xml接口名是否和mapper.java接..._spring-could org.apache.ibatis.binding.bindingexception: invalid bound state
四种高效数据库设计思想——提高查询效率_数据库为什么能提高效率-程序员宅基地
文章浏览阅读1.1k次。四种高效数据库设计思想——提高查询效率：设计数据库表结构时，我们首先要按照数据库的三大范式进行建立数据。1. 1NF每列不可拆分2. 2NF确保每个表只做一件事情3. 3NF满足2NF，消除表中的依赖传递。三大范式的出现是在上世纪70年代，由于内存资源比较昂贵，所以严格按照三大范式进行数据库设计。而如今内存变得越来越廉价，在考虑效率和内存的基础上我们可以做出最优选择以达到最高效率。_数据库为什么能提高效率
网页播放器（CKplayer）的视频怎么下载——m3u8简单探索_index网站入口m3u8-程序员宅基地
文章浏览阅读6.8w次，点赞8次，收藏22次。简要说明由于最近（2018-12-8）想看一个电影视频（《狗十三》），于是去网上找资源。这个电影本来2013年就已经开始有资源了，但是迟迟没有上映，有许多的原因导致影片没有上映，但是在2018-12-07日，终于开始上映了。（不扯了，，，再说会被认为是影评了）。于是呢，我就在网上找资源，之前是有资源的，但是由于现在正在上映，所以网上各种迅雷链接被屏蔽了，于是我就找 能在线播放的网站，终于找..._index网站入口m3u8
随便推点
二、使用GObject——一个简单类的实现-程序员宅基地
文章浏览阅读170次。Glib库实现了一个非常重要的基础类--GObject，这个类中封装了许多我们在定义和实现类时经常用到的机制： 引用计数式的内存管理 对象的构造与析构 通用的属性（Property）机制 Signal的简单使用方式 很多使用GObject..._
golang 定时任务处理-程序员宅基地
文章浏览阅读6.3k次，点赞2次，收藏9次。在 golang 中若写定时脚本，有两种实现。一、基于原生语法组装func DocSyncTaskCronJob() { ticker := time.NewTicker(time.Minute * 5) // 每分钟执行一次 for range ticker.C { ProcTask() }}func ProcTask() { log.Println("hello world")}二、基于 github 中封装的 cron 库实现package taskimport (_golang 定时任务
VC获取精确时间的方法_vc 通过线程和 sleep 获取精准时间-程序员宅基地
文章浏览阅读2.1k次。 来源:http://blog.csdn.net/clever101/archive/2008/10/18/3096049.aspx 声明：本文章是我整合网上的资料而成的，其中的大部分文字不是我所为的，我所起的作用只是归纳整理并添加我的一些看法。非常感谢引用到的文字的作者的辛勤劳动，所参考的文献在文章最后我已一一列出。 对关注性能的程序开发人员而言，一个好的计时部件既是益友，也_vc 通过线程和 sleep 获取精准时间
wml入门-程序员宅基地
文章浏览阅读58次。公司突然说要进行wap开发了，以前从没了解过，但我却异常的兴奋，因为可以学习新东西了，呵呵，我们大家一起努力吧。首先说说环境的搭建。可以把.wml的文件看做是另一种的html进行信息的展示，但并不是所有的浏览器都支持，好用的有Opera，还有WinWap。编写wml文件语法比较严格，不好的是我还没有找到好的提示工具，就先用纯文本吧。我找到了一个很好的学习网站：http://w3sc..._winwap学习
计算机考研怎么给老师发邮件,考研复试前，手把手教你怎么给导师发邮件！4点要注意...-程序员宅基地
文章浏览阅读504次。考研成绩出来后，第一件事是干什么？当然不只是高兴，而是马上给心仪的导师发邮件，先露个“名字熟”。不要以为初试考了高分或者过线了，一切都稳妥了，一时得意忘形，居然没联系导师，等想起时，导师已经属于他人了。对于一些大佬，热门导师一定要趁早发邮件咨询，一是表示尊重；二是这类老师可能已经没有统招名额，所以越早知道，越有利于下一步计划。但是，在给导师发邮件中，要注意以下4点，不求一步成功，但求先留下个好印象..._跨考计算机怎么给导师发邮件
美国计算机生物学大学,美国计算机大学排名-程序员宅基地
文章浏览阅读287次。作为美国目前就业薪资最高的专业，竞争很激烈，很多学生想要去美国读计算机专业，那么美国计算机专业大学排名情况是怎么样的呢？出国留学网介绍了相关的信息，来看看吧！一、美国计算机专业大学排名二、美国计算机专业分类人工智能结合实际与理论，将计算机科学运用到日常生活中，用电脑智能解决现实问题。适合已经有计算机背景，对该领域有兴趣，掌握编程等计算机技术的申请人。计算机生物科技涉及大量基因组学，生物学，医药学知...