离散数学第15章.pptxVIP

15.1 欧拉图历史背景：哥尼斯堡七桥问题与欧拉图欧拉图定义定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.(3) 欧拉图——具有欧拉回路的图.(4) 半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.欧拉图实例上图中，(1) ,(4) 为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图. 在(3),(6)中各至少加几条边才能成为欧拉图？ 无向欧拉图的判别法定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点.证 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图.必要性 设C 为G 中一条欧拉回路.(1) G 连通显然.(2) ?vi?V(G)，vi在C上每出现一次获2度，所以vi为偶度顶点. 由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）.(1) m=1时，G为一个环，则G为欧拉图.(2) 设m?k（k?1）时结论为真，m=k+1时如下证明：从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3. PLAY欧拉图的判别法定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇度顶点.证 必要性简单. 充分性（利用定理15.1）设u,v为G 中的两个奇度顶点，令 G ? =G?(u,v)则G ? 连通且无奇度顶点，由定理15.1知G ?为欧拉图，因而存在欧拉回路C，令 ?=C?(u,v)则? 为 G 中欧拉通路.有向欧拉图的判别法定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并. 可用归纳法证定理15.5. (1) (2)例题例1 设G是欧拉图，但G不是平凡图，也不是一个环，则?(G)?2.证 只需证明G中不可能有桥（如何证明？）上图中，(1),(2)两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？Fleury算法算法：(1) 任取v0?V(G)，令P0=v0. (2) 设Pi = v0e1v1e2…eivi 已经行遍，按下面方法从 E(G)?{e1,e2,…,ei }中选取ei+1： (a) ei+1与vi 相关联； (b) 除非无别的边可供行遍，否则ei+1不应该为 Gi = G?{e1,e2,…,ei }中的桥. (3) 当 (2)不能再进行时，算法停止.可以证明算法停止时所得简单通路 Pm = v0e1v1e2…emvm(vm=v0)为G 中一条欧拉回路. 用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点出发都可以）的欧拉回路各一条. (1) (2) 15.2 哈密顿图历史背景：哈密顿周游世界问题与哈密顿图哈密顿图与半哈密顿图定义15.2 (1) 哈密顿通路——经过图中所有顶点一次仅一次的通路.(2) 哈密顿回路——经过图中所有顶点一次仅一次的回路.(3) 哈密顿图——具有哈密顿回路的图.(4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上实例在上图中，(1),(2) 是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图，为什么？无向哈密顿图的一个必要条件定理15.6 设无向图G=V,E是哈密顿图，对于任意V1?V且V1??，均有 p(G?V1) ? |V1|证 设C为G中一条哈密顿回路(1) p(C?V1) ? |V1|(2) p(G?V1) ? p(C?V1) ? |V1|（因为C?G）推论 设无向图G=V,E是半哈密顿图，对于任意的V1?V且V1??均有 p(G?V1) ? |V1|+1证 令? uv为G中哈密顿通路，令G? = G?(u,v)，则G?为哈密顿图. 于是 p(G?V1) = p(G??V1?(u,v)) ? |V1|+1几点说明定理15.6中的条件是哈密顿图的必要条件，但不是充分条件