半欧拉图的判别(无向图) 定理:无向图G是半欧拉图,当且仅当G是连通的,且G中恰有两个 奇度顶点 明 (必要性) 设G是m条边的n阶无向图。因为G为半欧拉图,因而G中存在欧 拉通路(但不存在欧拉回路 设r= v: e: v1…v1,e1V1为G中一条欧拉通路,vn≠v1。显然, G是连诵性。 v∈v(G,若V不在的端点出现,显然dv为偶数;若v在端点出 现过,则d()为奇数 因为r只有两个端点且不同,所以G中只有两个奇数顶点7 半欧拉图的判别(无向图) 定理: 无向图G是半欧拉图, 当且仅当G是连通的, 且G中恰有两个 奇度顶点。 (必要性) 设G是m条边的n阶无向图。因为G为半欧拉图, 因而G中存在欧 拉通路(但不存在欧拉回路)。 设Γ = vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路, vi0 ≠ vim。显然, G是连通性。 ∀v ∈ V(G), 若v不在Γ的端点出现, 显然d(v)为偶数; 若v在端点出 现过, 则d(v)为奇数. 因为Γ只有两个端点且不同, 所以 G中只有两个奇数顶点。 证明: