2度,若u在通路中重复出现j次,则deg(u)=2j。? 即u的度数必为偶数。Р由于在回路C中边不可能重复出现Р2018/7/26Р计算机学院Р7Р“”? 设连通图G的结点的度数都是偶数,则G必含有简单回路(可对结点个数进行归纳证明) 。? 设C是一条包含G中边最多的简单回路:?⑴若C已经包含G中所有的边,则C就是Euler回路,结论成立。?⑵若C不能包含G中所有的边,则删边子图? G-E(C)仍然无奇数度结点。Р由于G是连通的,C中应至少存在一点v,使G-E(C)中有一条包含v的回路C′。(见示意图)РWhy?Р2018/7/26Р计算机学院Р8Р这样,就可以构造出一条由C和C′组成的G的回路,其包含的边数比C多,与假设矛盾。因此,C必是Euler回路,结论成立。Р2018/7/26Р计算机学院Р9Р证明:“”设G具有一条Euler道路L,则在L中除起点和终点外,其余每个结点都与偶数条边相关联,所以,G中仅有零个(Euler回路)或者两个奇数度结点。?“”?⑴若 G没有奇度数结点,则结论显然成立;?⑵若G有两个奇度数结点u和v,则G+uv是Euler图,从而存在Euler回路C。从C中去掉边uv,则得到一条简单道路L(起点u和终点v),且包含了G的全部边,即L是一条Euler道路。Р推论13-1.1.1非平凡连通图G=<V,E>含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。Р注意:若有两个奇度数结点,则它们是G中每条欧拉通路的端点。Р2018/7/26Р计算机学院Р10Р例13-1.2Р由定理13-1.1及推论13-1.1.1容易看出:Р是欧拉图;?不是欧拉图,但存在欧拉道路;?既不是欧拉图,也不存在欧拉道路。РV2РV1РV5РV3РV4Р(a)РV2РV1РV5РV3РV4Р(b)РV1РV4РV2РV3Р(c)Р现在,我们是不是已经解决了哥尼斯堡七桥问题?
全文预览
