欧拉图与哈密顿图 PPT.ppt

--哥尼斯堡七桥问题欧拉图是一笔画出的边不重复的回路。3通路:设G为无向标定图,G中顶点与边的交替序列Г=vi0ej1vi1ej2vi2…ejivil称为vi0到vil的通路,其中,vi0,vil分别称为Г的始点与终点。 回路:若vi0=vil,则称通路为回路。 简单通路:通路中,若Г的所有边各异; 简单回路: 简单通路中,若vi0=vil; 初级通路或路径:若Г的所有顶点(除vi0与vij可能相同外)各异,所有边也各异; 初级回路或圈:初级通路或路径中,若vi0=vil,:通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路;欧拉回路:通过图中所有边一次并且仅一次行遍所有顶点的回路。欧拉图:具有欧拉回路的图;半欧拉图:具有欧拉通路而无欧拉回路的图。,且G中没有奇度顶点。,且G中恰有两个奇度顶点。,且G中没有奇度顶点。证明 若G是平凡图,结论显然成立。下面设G为非平凡图,设G是m条边的n阶无向图, 并设G的顶点集V={v1,v2,…,vn}。必要性。因为G为欧拉图,所以G中存在欧拉回路, 设C为G中任意一条欧拉回路,vi,vj∈V,vi,vj都在C上, 因而vi,vj连通,所以G为连通图。又vi∈V,vi在C上每出现一次获得2度, 若出现k次就获得2k度,即d(vi)=2k, 所以G中无奇度顶点。8大家有疑问的,可以询问和交流可以互相讨论下,,且G中没有奇度顶点。充分性。由于G为非平凡的连通图可知,G中边数m≥1。对m作归纳法。(1)m=1时,由G的连通性及无奇度顶点可知, G只能是一个环,因而G为欧拉图。(2)设m≤k(k≥1)时结论成立,要证明m=k+1时,结论也成立。 由G的连通性及无奇度顶点可知,δ(G)≥2。 无论G是否为简单图,都可以用扩大路径法证明G中必含圈。10