欧拉图的判别(无向图) 定理:无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点 证明:若G是平凡图,结论显然成立.下面假设G为非平凡图 设G=<V,E>是含有m条边的n阶非平凡无向图,其中:V={v1 (必要性) 因为G为欧拉图,所以G中存在欧拉回路。设C是G中的欧拉 匈∈VvV都在C上,因此,v和是连通的,所以G为连通 路,Vv; 又v1∈V,v在C上每出现一次获得2度。若出现k次就获得2k 度,即:dv)=2k,所以,G中无奇度顶点4 欧拉图的判别(无向图) 定理: 无向图G是欧拉图, 当且仅当G是连通图, 且G中没有奇度顶点. (必要性.) 因为G为欧拉图, 所以G中存在欧拉回路。设C是G中的欧拉回 路, ∀vi, vj ∈ V, vi, vj都在C上, 因此, vi和vj是连通的, 所以G为连通 图. 又∀vi ∈ V, vi在C上每出现一次获得2度。若出现k次就获得2k 度, 即: d(vi) = 2k, 所以, G中无奇度顶点。 证明: 若G是平凡图, 结论显然成立. 下面假设G为非平凡图. 设G = <V, E>是含有m条边的n阶非平凡无向图, 其中: V = { v1, v2, …, vn }