高等学校21卌纪教材 欧拉在这篇论文中提出了一条简单准则, 确定七桥问题是不能解的。下面就来讨论这个 问题。 定义1.1图G中的一圈(或回路),若它通 G中的每一条边(或弧)恰好一次,则称该圈(或回 路)为欧拉圈(或回路),具有这种圈(或回路)的图 称为欧拉无向(或有向)图。 定理1.1给定连通无向图G,G有欧拉圈 台G中每个结点都是偶度结点 PT PRESS 人民邮电出版社
欧拉在这篇论文中提出了一条简单准则， 确定七桥问题是不能解的。下面就来讨论这个 问题。 定义11.1.1 图G中的一圈(或回路)，若它通 G中的每一条边(或弧)恰好一次，则称该圈(或回 路)为欧拉圈(或回路)，具有这种圈(或回路)的图 称为欧拉无向(或有向)图。 定理11.1.1 给定连通无向图G，G有欧拉圈 G中每个结点都是偶度结点
高等学校21卌纪教材 由定义1.1.可知,具有欧拉圈的图 是欧拉图,故图G为欧拉图G中每个结 点都是偶度结点。 由于七桥问题所对应的图中每个结点 都是奇度结点,根据上述定理可知,七桥 问题无解。 PT PRESS 人民邮电出版社
由定义11.1.1可知，具有欧拉圈的图 是欧拉图，故图G为欧拉图G中每个结 点都是偶度结点。 由于七桥问题所对应的图中每个结点 都是奇度结点，根据上述定理可知，七桥 问题无解
高等学校21卌纪教材 定义1..2图G中的一条链(或路),若它通 过G中的每条边(或弧)恰好一次,则称该链(或路) 为欧拉链(或路) 定理11.1.2给定连通无向图G=<V,E>,u, v∈T且≠v,u与v间存在欧拉链>G中仅有u和v 为奇度结点。 PT PRESS 人民邮电出版社
定义11.1.2 图G中的一条链(或路)，若它通 过G中的每条边(或弧)恰好一次，则称该链(或路) 为欧拉链(或路)。 定理11.1.2 给定连通无向图G=<V，E>，u， v∈V且u≠v，u与v间存在欧拉链G中仅有u和v 为奇度结点
高等学校21卌纪教材 定理1..3给定弱连通有向图G,G有欧拉 回路G中的每个结点的入度等于出度。 定理11.4给定弱连通有向图G=<V,E>, u,v∈且nv,u与在欧拉路令→G中唯有u和 v的入度不等于出度,且u的入度比其出度大于1 和的出度比其入度小于1(或者反之)。 PT PRESS 人民邮电出版社
定理11.1.3 给定弱连通有向图G，G有欧拉 回路G中的每个结点的入度等于出度。 定理11.1.4 给定弱连通有向图G=<V，E>， u，v∈V且u≠v，u与v存在欧拉路G中唯有u和 v的入度不等于出度，且u的入度比其出度大于1 和v的出度比其入度小于1(或者反之)
高等学校21卌纪教材 这两个定理的证明,可以看作是关于无向 图的欧拉圈和欧拉链的推广。因为对于有向图 的任意一个结点来说,如果入度与出度相等, 则该结点为偶度结点;如果入度与出度之差为1 时,该结点必是奇度结点,所以定理1.13和 1414与前面两个定理的证明类似。 PT PRESS 人民邮电出版社
这两个定理的证明，可以看作是关于无向 图的欧拉圈和欧拉链的推广。因为对于有向图 的任意一个结点来说，如果入度与出度相等， 则该结点为偶度结点；如果入度与出度之差为1 时，该结点必是奇度结点，所以定理11.1.3和 14.1.4与前面两个定理的证明类似