© Peking University 21Fleury算法(递归形式)算法: (1) if d(v)1 then e:=v关联的任意非割边 (2) else e:=v关联的唯一边 (3) u:=e的另一个端点. (4) 递归地求G-e的从

证明 若G是平凡图，结论显然成立。下面设G为非平凡图，设G是m条边的n阶无 向图，并设G的顶点集V＝{v1,v2,…,vn}。 必要性。因为G为欧拉图，所以G中存在欧 拉回路，设C为G中任意一条欧拉回路，vi,vj∈V， v2i0,2v0/

2016/12/6IntroductionToCS--Xiaofeng Gao10有向连通图的欧拉回路【推论】若有向连通图G中各节点的正负度 相等,则G中存在有向欧拉回路.证明方法类似之前定理，由G是有穷图且每 个节点正负度相等可以断定从G

第三章欧拉图与哈密顿图 （七桥问题与一笔画，欧拉图与哈密顿图） 教学安排的说明 章节题目：§3.1环路；§3.2 欧拉图；§3.3 哈密顿图 学时分配：共2课时 本章教学目的与要求：认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关

13实例在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？14无向哈密顿图的一个必要条件定理15.6 设无向图G=V,E是哈密顿图，对于任意V1V且 V1，均有 p(GV1) |

欧拉图与哈密顿图Euler and Hamilton Graph高晓沨 (Xiaofeng Gao)Department of Computer Science Shanghai Jiao Tong Univ.2016/12/6欧拉道路与欧

10例如，由定理可知，下图 (a)图为欧拉图，本图 既v成圈8 可圈画v6之v以在1并(看vc2)(成v中为3 圈v)清。4 vv晰1将5v起v2(6av见v)87分v，v1解8，将v成1v与42若个v圈3干圈vv42个画vv24边在，v6

说明：该推论是充分条件但不是必要的。 例如：该五边形是哈密顿图，但任意两个不相邻的顶点度 数之和为4，图形阶数为5。座位问题例 在某次国际会议的预备会中，共有8人参加，他 们来自不同的国家。如果他们中任两个无共同语言的人 与其余有共同语言的

举例欧拉图半欧拉图无欧拉通路欧拉图无欧拉通路无欧拉通路无向欧拉图的判定定理定理15.1 无向图G是欧拉图当且仅当G是连通图，且G中没有奇 度顶点。 证明 若G是平凡图，结论显然成立

(1) G 不含割边； (2) 对 ∀u,v ∈V (G)，存在圈 C，使 u,v 均在 C 上。 证明 (1) G，欧拉图 G ⇒ G 存在欧拉回路 C′ 设 C′=v1v2…v

12实例在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？13无向哈密顿图的一个必要条件定理15.6 设无向图G=&l

（1）（2）（3）（5） （6） 图2 易知，图 2 中， 、 （1）（4）为欧拉图， ， （2）（5）为半欧拉图， ， （3）（6） 既不是欧拉图，也不是半欧拉图. 在（3）（6

定理15.7下面证G中存在哈密顿通路。 设Г＝v1v2…vl为G中用“扩大路径法”得到的“极大路径”， 即Г的始点v1与终点vl不与Г外的顶点相邻。显然有l≤n。 (1)若l＝n，

例：图中给出的二部图，哪些是哈密顿图， a 哪些是半哈密顿图？ a e fbc f G1debgh j kidc G2 (1)V1={a,f},V2={b,c,d,e}，p(G1-V1)=4|V1|,都不是 (2)V1={a,g,h,i,c

由定义可知,二部图不会有自回路。 定义8.4―2 二部图G=〈X,E,Y〉中,若X的每一 顶点都与Y的每一顶点邻接,则称G为完全二部图,记为 Km,n,这里m=｜X｜,n=｜Y｜。 图8.4―1给出K2,4和K3,3的图示。图 8.4―1

穿过每一道门，通过所有房间？15.2 哈密顿图1859年，爱尔兰数学家威廉·哈密尔顿发明 了一个旅游世界的游戏。将一个正十二面体的 20个顶点分别标上世界上大城市的名字，要求 玩游戏的人从某城市出发沿12面体的棱，通过 每个城市恰一次，最后

例如，由定理可知，下图 (a)图为欧拉图，本图 既v成圈8 可圈画v6之v以在1并(看vc2)(成v中为3 圈v)清。4 vv晰1将5v起v2(6av见v)87分v，v1解8，将v成1v与42若个v圈3干圈vv42个画vv24边在，v6不(

构造欧拉回路思想：在画欧拉回路时，已经经过的边不能再用。因此， 在构造欧拉回路过程中的任何时刻，假设将已经经过的边 删除，剩下的边必须仍在同一连通分支当中。构造欧拉回路-Fleury算法算法：输入：欧拉图G输出：简单通路P = v0e1v1

v1 v2v3v1v8v2 v2v3v4 v4v1v2 v2v3v8v4v8 v7 v6 v6v8v8 v6v4v4（a） （b） （c） 定理9.1.3 G是非平凡的欧拉图当且仅

3、无向欧拉图的应用 ① 七桥问题 A B C D d(B)=5， d(A)= d (C)= d(D)=3，七桥问题无解 。② 一笔划问题v1 v2 v3所给图能否一笔画出？ v1