1、1 图论 Graph Theory 2 1.1. 图的基本概念图的基本概念 2.2. 图的连通性图的连通性 3.3. 图的矩阵表示图的矩阵表示 4.4. 欧拉图与哈密顿图欧拉图与哈密顿图 5.5. 无向树与根树无向树与根树 6.6. 平面图平面图 内容提要内容提要 1 1、图的基本概念、图的基本概念 概念概念： 无向图、有向图、关联与相邻、简单图、完全图、无向图、有向图、关联与相邻、简单图、完全图、 正则图、子图、补图，握手定理，图的同构正则图、子图、补图，握手定理，图的同构 4 预备知识预备知识 多重集合多重集合元素可以重复出现的集合元素可以重复出现的集合 无序积无序积A B=(x,y) |
2、 x A y B 5 无向图无向图G = , 其中其中 (1) V 为顶点集，元素称为为顶点集，元素称为顶点；顶点； (2) E为为V V 的多重集，其元素称为无向边，简称的多重集，其元素称为无向边，简称边。边。 例：例： 设设 V = v1, v2, v3, v4,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则则 G = 为一无向图为一无向图 6 有向图有向图 D=, 只需注意只需注意E是是V V 的多重子集的多重子集 例：例：下图表示的是一个有向图，下图表示的是一个有向图， D= V = a,b
3、,c,d, E =, 1.1. n n阶图阶图：顶点个数为：顶点个数为n.n. 2. 2. 零图零图：边的个数为：边的个数为0. 0. n n 阶零阶零图记图记为为N Nn n 平凡平凡图图：1 1 阶零图阶零图N N1 1 4. 4. 空图空图 5 5. . 标定图标定图与与非标定图非标定图：依据顶点和边是否命名标识。：依据顶点和边是否命名标识。 6.6.有向图的有向图的基图基图：有向边改为无向边后的图。：有向边改为无向边后的图。 图的相关概念图的相关概念 用用 e ek k 表示无向边或有向边。表示无向边或有向边。 1. 1. 顶点与边的关联关系顶点与边的关联关系e ek k=(v=(vi
4、 i , , v vj j) ) 关联关联： e ek k与与v vi i , , v vj j关联 关联 关联次数关联次数：0(0(不关联不关联) )，1(v1(vi i v vj j ) )， 2(v2(vi i = =v vj j ) ) 环环：与同一顶点关联次数为：与同一顶点关联次数为2 2的边；的边； 孤立点孤立点：不与任何边关联的顶点。：不与任何边关联的顶点。 2.2. 顶点相邻顶点相邻：两个顶点之间有边。：两个顶点之间有边。 3.3. 边相邻边相邻：两条边有公共端点。：两条边有公共端点。 4.4. 平行边平行边：关联的端点相同的两条边。：关联的端点相同的两条边。 点与边的相关概念
5、点与边的相关概念 9 )()( )(),()(|)( vvNvNv vuGEvuGVuuvNv 的闭邻域的闭邻域 的邻域的邻域 )(|)(关联关联与与veGEeevI )()( )()()( )(,)(|)( )(,)(|)( vvNvNv vvvNv vuDEvuDVuuvv vuDEuvDVuuvv D D DDD D D 的闭邻域的闭邻域 的邻域的邻域 的先驱元集的先驱元集 的后继元集的后继元集 v V(G) (G为无向图为无向图) v 的关联集的关联集 v V(D) (D为有向图为有向图) 邻域与关联集邻域与关联集 10 多重图与简单图多重图与简单图 多重图：多重图：含平行边的图；含平
6、行边的图； 简单图：简单图：即不含平行边又不含环的图。即不含平行边又不含环的图。 11 顶点的度数顶点的度数 (1) 设设G=为无向图为无向图, v V, d(v)v的的度数度数, 简称简称度度 (2) 设设D=为有向图为有向图, v V, d+(v)v的的出度出度 d (v)v的的入度入度 d(v)v的度或度数的度或度数 (3) 最大度最大度 (G)，最小度最小度 (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点奇顶点度与偶度顶点 12 mvd n i i 2)( 1 mvdvdmvd n i i n i i n i i 111 )()
7、(,2)(且且 定理定理 （1） 设设G=为任意无向图，为任意无向图，V=v1,v2,vn, |E|=m, 则则 握手定理握手定理 (2) 设设D=为任意有向图，为任意有向图，V=v1,v2,vn, |E|=m, 则则 推论推论 ： 任何图任何图 (无向或有向无向或有向) 中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数. 13 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余顶点度顶点，其余顶点 度数均小于度数均小于3，问，问G的阶数的阶数n为几？为几？ 解解 本题的关键是应用握手定理本题的关键是应用握手定理. 设除设除3度与度与4度顶点外，还有度顶点外，还有x
8、个顶点个顶点v1, v2, , vx， 则则 d(vi) 2，i =1, 2, , x， 于是得不等式于是得不等式 32 24+2x 得得 x 4, 阶数阶数 n 4+4+3=11. 握手定理应用例握手定理应用例 14 图的度数列图的度数列 1 . V=v1, v2, , vn为无向图为无向图G的顶点集，称的顶点集，称d(v1), d(v2), , d(vn)为为G的的度数列度数列 。 2. V=v1, v2, , vn为有向图为有向图D的顶点集，的顶点集， D的的度数列度数列：d(v1), d(v2), , d(vn) D的的出度列出度列：d+(v1), d+(v2), , d+(vn) D
9、的的入度列入度列：d (v1), d (v2), , d (vn) 3. 非负整数列非负整数列d=(d1, d2, , dn)是是可图化的可图化的；是；是可简单图化的可简单图化的. 定理定理（1）非负整数列非负整数列d=(d1, d2, , dn)是可图化的当且仅当是可图化的当且仅当 为偶数为偶数. （2）设）设G为任意为任意n阶无向简单图，则阶无向简单图，则 (G) n -1. n i i d 1 例：判断下列度数列是否可图化？可简单图化？例：判断下列度数列是否可图化？可简单图化？ (2, 4, 6, 8, 10)(2, 4, 6, 8, 10) (1, 3, 3, 3, 4)(1, 3,
10、3, 3, 4) (2, 2, 3, 4, 5)(2, 2, 3, 4, 5) (3, 3, 3, 4)(3, 3, 3, 4) (2, 4, 6, 8, 10)是可图化的是可图化的 (1, 3, 3, 3, 4) 是可图化的，也是可简单图化的是可图化的，也是可简单图化的 (2, 2, 3, 4, 5) 是可图化的，是可图化的， 但不是可简单图化的，但不是可简单图化的， (3, 3, 3, 4)不不 是可图化的是可图化的 16 图的同构图的同构 设设G1=, G2=为两个无向图为两个无向图(两个有向图两个有向图)，若存，若存 在双射函数在双射函数f :V1V2 ，对于，对于vi, vj V1,
11、 (vi,vj) E1 当且仅当当且仅当 (f(vi), f(vj) E2 （ （ E1 当且仅当当且仅当 E2 ) 并且并且, (vi,vj)（）与）与 (f(vi), f(vj)（）的重数相）的重数相 同，则称同，则称G1与与G2是是同构的同构的，记作，记作G1 G2. 例例 不同构不同构 （度数列不同）（度数列不同） 不同构不同构 同构同构 图中图中(1)(1)与与(2)(2)的度数列相同，它们同构吗？为什么？的度数列相同，它们同构吗？为什么？ (1) (2) 答：不同构答：不同构 1与与2同构的必要条件同构的必要条件： 1、顶点数相同、顶点数相同 2、边数相同、边数相同 3、度数相同的
12、顶点数目相等、度数相同的顶点数目相等 例例 21 n 阶完全图与竞赛图阶完全图与竞赛图 (1) n (n 1) 阶阶无向完全图无向完全图每个顶点与其余顶点均相邻的每个顶点与其余顶点均相邻的 无向简单图，记作无向简单图，记作 Kn. 性质性质：边数：边数 (2) n (n 1)阶阶有向完全图有向完全图每对顶点之间均有两条方向相每对顶点之间均有两条方向相 反的有向边的有向简单图反的有向边的有向简单图. 性质性质：边数：边数 (3) n (n 1) 阶阶竞赛图竞赛图基图为基图为Kn的有向简单图的有向简单图. 性质性质：边数：边数 1, 2 )1( n nn m 1),1( 2),1( nnnnm 1
13、, 2 )1( n nn m 22 实例实例 (1) 为为K5 (2) 为为3阶有向完全图阶有向完全图 (3) 为为4阶竞赛图阶竞赛图. (1) (2) (3) 性质性质：边数（由握手定理得）：边数（由握手定理得） 2 nk m n 阶阶 k 正则图正则图 n n 阶阶k k正则图正则图 = = = =k k 的无向简单图。的无向简单图。 K Kn n是是 n n 1 1正则图。正则图。 24 子子 图图 G=, GG=, G = (1) (1) V V V V 且且E E E E , ,则称则称G G为为G G的的子图子图，记为，记为G GG G ， 称称G G为为G G 的的母图母图; ;
14、 (2) (2) 若若G GG G且且V V =V=V，则称，则称G G 为为G G的的生成子图；生成子图； (3) (3) 若若V VV V或或E EE E，称，称G G 为为G G的的真子图；真子图； (4) V(4) V （V VV V且且V V）的）的导出子图导出子图，记作，记作GVGV ； (5) E(5) E （E EE E且且E E）的）的导出子图导出子图，记作，记作GEGE . 例例: : 子图子图 1 1 2 2 3 3 例：例： 画出画出K K4 4的所有非同构的生成子图的所有非同构的生成子图 27 补图补图 设设G=为为n阶无向简单图，以阶无向简单图，以V为顶点集，以所有
15、使为顶点集，以所有使G 成为完全图成为完全图Kn的添加边组成的集合为边集的图，称为的添加边组成的集合为边集的图，称为G的的 补图补图，记作，记作 . 若若G , 则称则称G是是自补图自补图. G G 例例 G G 2 2、图的连通性、图的连通性 概念概念： 通路，回路，简单通路，简单回路（迹）初级通路（路通路，回路，简单通路，简单回路（迹）初级通路（路 径），初级回路（圈）径），初级回路（圈） 点连通，连通图，点割集，割点，边割集，割边点连通，连通图，点割集，割点，边割集，割边 点连通度，边连通度点连通度，边连通度 弱连通图，单向连通图，强连通图弱连通图，单向连通图，强连通图 二部图（二分图）
16、二部图（二分图） 30 通路与回路通路与回路 给定图给定图G G=（无向或有向的），（无向或有向的），G G中中顶点与边的交替序列顶点与边的交替序列 = = v v0 0e e1 1v v1 1e e2 2e el lv vl l称为从称为从v v0 0到到v vl l的的通路通路，其中，其中v vi i 1 1, , v vi i 是 是 e ei i 的端点的端点. .；若；若 v v0 0= =v vl l， 为为回路回路。 中的边数称为通路的长中的边数称为通路的长 度度. . 简单通路简单通路与与简单简单回路回路：所有边各异。：所有边各异。 初级通路初级通路( (路径路径) )与与初级
17、回路初级回路( (圈圈) )： 中所有顶点各异中所有顶点各异 （v v0 0= =v vl l 除外），除外），所有所有边也各异边也各异 复杂通路复杂通路与与复杂回路复杂回路：有边重复出现。：有边重复出现。 31 几点说明几点说明 表示法表示法 定义表示法定义表示法 只用边表示法只用边表示法 只用顶点表示法（在简单图中）只用顶点表示法（在简单图中） 混合表示法混合表示法 环（长为环（长为1 1的圈）的长度为的圈）的长度为1 1 两条平行边构成的圈长度为两条平行边构成的圈长度为2 2 无向简单图中，圈长无向简单图中，圈长 3 3 有向简单图中圈的长度有向简单图中圈的长度 2 2 32 通路与回路
18、的长度通路与回路的长度 定理定理 在在n 阶图阶图G中，若从顶点中，若从顶点vi 到到vj（vi vj）存在通路，）存在通路， 则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 的通路的通路. 推论推论 在在 n 阶图阶图G中，若从顶点中，若从顶点vi 到到 vj（vi vj）存在通路，则）存在通路，则 从从vi 到到vj 存在长度小于或等于存在长度小于或等于n 1的初级通路（路径）的初级通路（路径）. 定理定理 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到自身的回路，则一定存到自身的回路，则一定存 在在vi 到自身长度小于或等于到自身长度小于或等于 n 的回路
19、的回路. 推论推论 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到自身的简单回路，则一到自身的简单回路，则一 定存在长度小于或等于定存在长度小于或等于n 的初级回路的初级回路. 33 顶点的连通性顶点的连通性 G=为无向图，若为无向图，若 vi 与与 vj 之间有通路，则称之间有通路，则称vi 与与 vj是是 连通的连通的，记为，记为vi vj。 。 注：注： 是是V上的等价关系上的等价关系 R=| u,v V且且u v 34 图的连通性图的连通性 若若 u,v V，u v，则称，则称G是是连通的连通的； V/R=V1,V2,Vk，称，称GV1, GV2, ,GVk为为连通分支连通分
20、支， 其个数称为其个数称为连通分支数连通分支数，记为，记为 p(G)。 注：若注：若 p(G) =1，G是是连通的。连通的。 35 短程线与距离短程线与距离 u与与v之间的之间的短程线短程线：u v，u与与v之间长度最短的通路之间长度最短的通路 u与与v之间的之间的距离距离：d(u,v)短程线的长度短程线的长度 d(u,v)的性质的性质 d(u,v) 0, u v时时d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w) 36 图的运算图的运算 删除顶点及删除边删除顶点及删除边 G v 从从G中将中将v及关联的边去掉及关联的边去掉 G V 从从G中删除中删除V 中
21、所有的顶点中所有的顶点 G e 将将e从从G中去掉中去掉 G E 删除删除E 中所有边中所有边 37 点割集与边割集点割集与边割集 点割集与割点点割集与割点 G=, VV V 为为点割集点割集p(G V )p(G)，且对任意，且对任意VV 均有均有p(G V )=p(G). v为为割点割点v为点割集为点割集 边割集与割边边割集与割边 G=, EE E 是是边割集边割集p(G E )p(G)且有极小性且有极小性 e是是割边（桥）割边（桥）e为边割集为边割集 38 例例: （1） v1,v4，v6是点割集，是点割集，v6是割点是割点. v2,v5是点割集吗？是点割集吗？ （2）e1,e2，e1,e
22、3,e5,e6，e8等是边割集，等是边割集，e8是桥。是桥。 e7,e9,e5,e6 是边割集吗？是边割集吗？ 39 点连通度点连通度 G为连通非完全图为连通非完全图 （1） 点连通度点连通度 (G) = min |V | V 为点割集为点割集 规定规定 (Kn) = n1 若G非连通，(G) = 0 （2） 若若 (G) k，则称，则称G为为 k-连通图连通图 例：例： 图中，图中， =1，它是，它是 1-连通图。连通图。 40 边连通度边连通度 设设G为连通图为连通图 边连通度边连通度 (G) = min|E | E 为边割集为边割集 规定： 若G非连通，则(G) = 0 若若 (G) r
23、，则称，则称G是是 r 边边-连通图连通图 例：例： 图中，图中， =1，它是，它是 1边边-连通图。连通图。 41 , , 之间的关系之间的关系 定理定理 (G)(G)(G) 证明思路： 证明思路： （1） (G)(G) （2） (G)(G) 42 有向图的连通性有向图的连通性 D=为有向图为有向图 vi vj（vi 可达可达 vj）：存在从：存在从vi 到到vj 有通路有通路 vi vj（vi 与与vj 相互可达）相互可达）： vi vj 且且vj vi 性质性质 具有自反性具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 vi 到到vj 的短
24、程线与距离的短程线与距离 类似于无向图中，只需注意距离表示法的不同类似于无向图中，只需注意距离表示法的不同 (无向图中无向图中d(vi,vj)，有向图中，有向图中d) 及及 d无对称性无对称性 43 有向图的连通性有向图的连通性 D=为有向图为有向图 D弱连通弱连通(连通连通)基图为无向连通图基图为无向连通图 D单向连通单向连通 vi,vj V，vivj 或或 vjvi D强连通强连通 vi,vj V，vivj 注：强连通注：强连通单向连通单向连通弱连通弱连通 例例 强连通强连通 单连通单连通 弱连通弱连通 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3
25、 4 4 45 有向图的连通性判别法有向图的连通性判别法 (1) D强连通强连通当且仅当当且仅当D中存在经过每个顶点至少一次的回路；中存在经过每个顶点至少一次的回路； (2) D单向连通单向连通当且仅当当且仅当D中存在经过每个顶点至少一次的通路。中存在经过每个顶点至少一次的通路。 46 二部图二部图 设设 G=为一个无向图，若能将为一个无向图，若能将 V分成分成 V1和和V2 (V1 V2=V， V1 V2=)，使得，使得 G 中的每条边的两个端点都是一个属于中的每条边的两个端点都是一个属于V1， 另一个属于另一个属于V2，则称，则称 G 为为二部图二部图 ( 或称或称二分图、偶图二分图、偶图
26、等等 )，称，称 V1和和V2为为互补顶点子集互补顶点子集，常将二部图，常将二部图G记为记为. 特殊特殊地地，若，若G是简单二部图，是简单二部图，V1中每个顶点均与中每个顶点均与V2中所有的顶中所有的顶 点相邻，则称点相邻，则称G为为完全二部图完全二部图，记为，记为 Kr,s，其中，其中r=|V1|，s=|V2|. 注意，注意，n 阶零图为二部图阶零图为二部图. 47 二部图的判别法二部图的判别法 定理定理 无向图无向图G=是是二部图二部图当且仅当当且仅当G中无奇圈中无奇圈 。 例：例：由定理可知下列各图都是二部图，哪些是完全二部图？由定理可知下列各图都是二部图，哪些是完全二部图？ 3 3、图
27、的矩阵表示、图的矩阵表示 概念概念： 关联矩阵，邻接矩阵，可达矩阵关联矩阵，邻接矩阵，可达矩阵 49 无向图的关联矩阵无向图的关联矩阵（对图无限制）（对图无限制） 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为 vi 与与 ej 的关联次数，的关联次数， 称称(mij)n m为为G 的的关联矩阵关联矩阵，记为，记为M(G). 性质性质 平行边的列相同平行边的列相同)4( 2)3( ),.,2 , 1()()2( ),.,2 , 1(2)1( , 1 1 mm nivdm mjm ji ij i m j ij n i ij 0 1 0 1 0 0 1 1 0 0 2 0 0 0 1
28、 0 0 1 1 1 M(G) 例例 51 ji ij m j m j iijiij n i ij m nivdmvdm mjm , 11 1 0)3( ,.,2 , 1),()1(),()1()2( ),.,2 , 1(0)1( 的终点的终点为为， 不关联不关联与与， 的始点的始点为为 ji ji ji ij ev ev ev m 1 0 ,1 有向图的关联矩阵有向图的关联矩阵（无环有向图）（无环有向图） 有向图有向图D=，令则称，令则称 (mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D). (4) 平行边对应的列相同平行边对应的列相同 性质性质 1- 1- 0 0 0 1 0
29、1- 0 0 0 0 0 1 1- 0 1 1 1- 1 M(G) 例例 有向图的邻接矩阵有向图的邻接矩阵 设设D D(V,E)(V,E)是是有向图有向图， V V =v=v1 1,.,.,v vn n ，构造矩阵，构造矩阵 A=A=a aij ij 如下： 如下： i,ji,j(1(1 i,ji,j n) n) 没有边到若从 条边有到若从 ji ji ij vv kvvk a 0 称称A A为图为图D D的的邻接矩阵邻接矩阵。 例例 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0 A 55 有向图的邻接矩阵性质有向图的邻接矩阵性质 的回路数的回路数中长度为中长度为 的通路数的
30、通路数中长度为中长度为 1)4( 1)3( ,.,2 , 1),()2( ,.,2 , 1),()1( 1 )1( , )1( 1 )1( 1 )1( Da Dma njvda nivda n i ii ji ij j n i ij i n j ij 56 推论推论 设设Bl=A+A2+Al（l 1），则），则 Bl中元素中元素 为D中长度为 l 的通路总数， )(l ij a )(l ii a n i n j l ij a 11 )( n i l ii a 1 )( n i n j l ij b 11 )( n i l ii b 1 )( 定理定理 设设 A为有向图为有向图 D 的邻接矩阵，
31、的邻接矩阵，V=v1, v2, , vn为顶点为顶点 集，则集，则 A 的的 l 次幂次幂 Al（l 1）中元素）中元素 为D中vi 到vj长度为 l 的通路数，其中 为vi到自身长度为 l 的回路数，而 为为D中长度小于或等于中长度小于或等于 l 的回路数的回路数 为为D中长度小于或等于中长度小于或等于 l 的通路数的通路数. 邻接矩阵的含义邻接矩阵的含义 为为D 中长度为中长度为 l 的回路总数的回路总数. 57 有向图有向图D如图所示，求如图所示，求 A, A2, A3, A4，并回答诸问题：，并回答诸问题： (1) D 中长度为中长度为1, 2, 3, 4的通路各有多少条？其中回路分别
32、为多的通路各有多少条？其中回路分别为多 少条？少条？ (2) D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路？的通路为多少条？其中有多少条回路？ 实例实例 58 1004 0104 1005 0001 0103 1003 0104 0001 1002 0102 1003 0001 0101 1001 0102 0001 43 2 AA AA (1) D中长度为中长度为1的通路为的通路为8条，其中有条，其中有1条是回路条是回路. D中长度为中长度为2的通路为的通路为11条，其中有条，其中有3条是回路条是回路. D中长度为中长度为3和和4的通路分别为的通路分别为14和和17
33、条，回路分别条，回路分别 为为1与与3条条. (2) D中长度小于等于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路条是回路. 实例求解实例求解 59 否则,0 可达,1 ji ij vv p 1101 1101 1111 0001 P 有向图的可达矩阵有向图的可达矩阵 设设D=为有向图为有向图. V=v1, v2, , vn, 令令 称称 (pij)n n 为为D的的可达矩阵可达矩阵，记作，记作P(D)，简记为，简记为P. 例例：求下图所示有向图：求下图所示有向图 D D 的可达矩阵。的可达矩阵。 4 4、欧拉图与哈密顿图、欧拉图与哈密顿图 概念概念： 欧拉通路、欧拉回路
34、、欧拉图、半欧拉图及其判别法欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 61 历史背景：哥尼斯堡七桥问题与欧拉图历史背景：哥尼斯堡七桥问题与欧拉图 62 定义定义 (1) 欧拉通路欧拉通路经过图经过图（无向图或有向图）（无向图或有向图）中每条边一次中每条边一次 且仅一次行遍所有顶点的通路且仅一次行遍所有顶点的通路. (2) 欧拉回路欧拉回路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶 点的回路点的回路. (3) 欧拉图欧拉图具有欧拉回路的图具有欧拉回路的图. (4) 半欧拉
35、图半欧拉图具有欧拉通路而无欧拉回路的图具有欧拉通路而无欧拉回路的图. 注：注：(1) 约定：平凡图是约定：平凡图是欧拉图欧拉图. (2) 欧拉欧拉通路是通路是简单简单通路，通路，欧拉欧拉回路是简单回路回路是简单回路. 63 上图中，上图中，(1) ,(4) 为欧拉图，为欧拉图，(2),(5)为半欧拉图，为半欧拉图，(3),(6)既不是既不是 欧拉图，也不是半欧拉图欧拉图，也不是半欧拉图. 在在(3),(6)中各至少加几条边才能成为欧拉图？中各至少加几条边才能成为欧拉图？ 欧拉图判别实例欧拉图判别实例 (1) (3) (2) (4) (6) (5) 64 无向欧拉图的判别法无向欧拉图的判别法 定
36、理：定理： (1) 无向图无向图G是是欧拉图欧拉图当且仅当当且仅当G连通且无奇度数顶点连通且无奇度数顶点. (2) 无向图无向图G是是半欧拉图半欧拉图当且仅当当且仅当G 连通且恰有两个奇度顶点连通且恰有两个奇度顶点. 65 有向欧拉图的判别法有向欧拉图的判别法 定理：定理： (1) 有向图有向图D是是欧拉图欧拉图当且仅当当且仅当D是强连通的且每个顶点的入是强连通的且每个顶点的入 度都等于出度度都等于出度. (2) 有向图有向图D是是半欧拉图半欧拉图当且仅当当且仅当D是单向连通的，且是单向连通的，且D中恰中恰 有两个奇度顶点，其中一个的入度比出度大有两个奇度顶点，其中一个的入度比出度大1，另一个
37、的，另一个的 出度比入度大出度比入度大1，而其余顶点的入度都等于出度，而其余顶点的入度都等于出度. 66 Fleury算法算法 算法：算法： (1) 任取任取v0 V(G)，令，令P0=v0. (2) 设设Pi = v0e1v1e2eivi 已经行遍，按下面方法从已经行遍，按下面方法从 E(G) e1,e2,ei 中选取中选取ei+1： (a) ei+1与与vi 相关联；相关联； (b) 除非无别的边可供行遍，否则除非无别的边可供行遍，否则ei+1不应该为不应该为 Gi = G e1,e2,ei 中的桥中的桥. (3) 当当 (2)不能再进行时，算法停止不能再进行时，算法停止. 注：注：(1)
38、 Fleury算法的基本思路是能不走桥就不走桥算法的基本思路是能不走桥就不走桥; (2) 假如假如G是欧拉图，则算法停止时所得简单通路是欧拉图，则算法停止时所得简单通路 Pm = v0e1v1e2emvm(vm=v0)为为G 中一条欧拉回路中一条欧拉回路. 67 历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图 (1) (2) 68 定义定义: (1) 哈密顿通路哈密顿通路经过图经过图（无向图或有向图）（无向图或有向图）中所有顶点中所有顶点 一次仅一次的通路一次仅一次的通路. (2) 哈密顿回路哈密顿回路经过图中所有顶点一次仅一次的回路经过图中所有顶点一次仅一次的回
39、路. (3) 哈密顿图哈密顿图具有哈密顿回路的图具有哈密顿回路的图. (4) 半哈密顿图半哈密顿图具有哈密顿通路且无哈密顿回路的图具有哈密顿通路且无哈密顿回路的图. 注：注：(1) 约定：平凡图是哈密顿图约定：平凡图是哈密顿图. (2) 哈密顿通路是初级通路，哈密顿回路是初级回路哈密顿通路是初级通路，哈密顿回路是初级回路. 69 实例实例 在上图中，在上图中， (1),(2) 是哈密顿图是哈密顿图; (3)是半哈密顿图是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？既不是哈密顿图，也不是半哈密顿图，为什么？ (1) (3) (2) (4) 70 哈密顿图的必要条件哈密顿图的必要
40、条件 定理定理 设无向图设无向图G=是哈密顿图，对于任意是哈密顿图，对于任意V1 V且且 V1，均有，均有 p(G V1) |V1| 推论推论 设无向图设无向图G=是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 V 且且V1均有均有 p(G V1) |V1|+1 71 哈密顿图的充分条件哈密顿图的充分条件 定理定理 设设G是是n阶无向简单图，若对于任意不相邻的顶点阶无向简单图，若对于任意不相邻的顶点vi,vj， 均有均有 d(vi)+d(vj) n 1 ( ) 则则G 中存在哈密顿通路中存在哈密顿通路. 推论推论 设设G为为n (n 3) 阶无向简单图，若对于阶无向简单图，若对于G中任意
41、两个中任意两个 不相邻的顶点不相邻的顶点vi,vj，均有，均有 d(vi)+d(vj) n （） 则则G中存在哈密顿回路，从而中存在哈密顿回路，从而G为哈密顿图为哈密顿图. 定理：定理： 设图设图G G(V,E) (V,E) 是具有是具有n n个结点的简单无向图，个结点的简单无向图， 1 1）若）若 u,vu,v V,uV,u v v，有，有 1)()(nvdud 则则G G中存在哈密顿通路。中存在哈密顿通路。 2 2）若）若 u,vu,v V,uV,u v v，有，有 nvdud)()( 则则G G中存在哈密顿回路。中存在哈密顿回路。 哈密顿图的充分条件哈密顿图的充分条件 例例 充分条件非必
42、要条件 考虑考虑7 7天安排天安排7 7门课程，使得同一位老师所任的课程考试不门课程，使得同一位老师所任的课程考试不 安排在连续的两天中。证明：若没有教师担任的课程多于安排在连续的两天中。证明：若没有教师担任的课程多于 4 4门，则可以给出合理的安排。门，则可以给出合理的安排。 例例 证明：构造无向图证明：构造无向图G G (V,E)(V,E) 结点：课程结点：课程 |V|=7|V|=7 边：边：2 2门课程由不同老师担任，则连接门课程由不同老师担任，则连接 寻找一条寻找一条哈密顿路哈密顿路 v v V,deg(v)V,deg(v) 3 3 u,vu,v V deg(v)+ deg(v) V deg(v)+ deg(v) 6=76=7- -1 1 75 判断某图是否为哈密顿图方法判断某图是否为哈密顿图方法 (1) 判断某图是否为哈密顿图至今还是一个难题判断某图是否为哈密顿图至今还是一个难题. (2) 判断某图是否哈密顿图的方法：判断某图是否哈密顿图的方法： 观察法观察法 充分条件充分条件 必要条件必要条件 1. 1. 观察出哈密顿回路观察出哈密顿回路. . ( (周游世界问题周游世界问题) ) a a b b c c d d e e f f g g h h i i j j k k l l mm n n p p q q r r s s t
