离散数学报告欧拉图

阶为6，最大度为4，含有3边环，是欧拉图

存在欧拉路的充要条件是有2个奇点，但欧拉图中，是有欧拉回路，没有奇点。

无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)；

无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；

有向连通图D是欧拉图，当且仅当D中每个结点的入度＝出度

有向连通图D含有欧拉通路，当且仅当D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1。（起始点s的入读=出度+1，结束点t的出度=入度+1 或两个点的入读=出度）

扩展资料：

假设有一张图有向图G'，在不论方向的情况下它与G同构。并且G'包含了G的所有有向边。那么如果存在一个图G'使得G'存在欧拉回路，那么G就存在欧拉回路。

其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个G'。用Ii表示第i个点的入度，Oi表示第i个点的出度。如果存在一个点k，|Ok-Ik|mod 2=1，那么G不存在欧拉回路。

接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边，对于所有Ii

参考资料来源：百度百科-欧拉回路

无向图是欧拉图的充要条件是每个顶点度数为偶数，你数邻接矩阵每一行1的个数，如果各行均是偶数，就是欧拉图

欧拉图比较简单：每个结点的度数都是偶数这样就排除了AC哈密尔顿图要求删除任意一个后不能有2个以上的连通分支D图删除中下方的那个点以后，会有2个连通分支排除D这样就只剩下B了