5欧拉图与汉密尔顿图

1、1图的矩阵表示?1. 关联矩阵M(D), M(G) ?2. 邻接矩阵A(D), 邻接矩阵A(G)?3. 用A的幂求不同长度通路 (回路)总数?4. 可达矩阵P(D), 连通矩阵P(G)2无向图关联矩阵?设G=是无向图,V=v1,v2,vn, E=e1,e2,em?关联矩阵关联矩阵(incidence matrix): M(G)=mijn?m,(每个顶点确定一行,每条边确定一列), mij= vi与ej的关联次数2, vi与ej关联，且ej是环mij= 1, vi与ej关联，且ej不是环0, vi不与ej关联?100100111000010011001111)(6543214321eeeeeev

2、vvvGM3无向图关联矩阵(例)123456123411 110 0( )110 0 10000 1 1100 100 1eeeeeevM Gvvv?v1v2v4v3e1e2e3e4e6e54无向图关联矩阵(性质)?每列和为2: ?ni=1mij=2 ( ?ni=1?mj=1mij=2m )?每行和为d(v): d(vi)=?mj=1mij?孤立点:全0行?平行边: 相同两列?环：对应列中只有一个 2其余是0?100100111000010011001111)(6543214321eeeeeevvvvGM?)()()()(21kGMGMGMGM?5有向图关联矩阵?设D=是无环有向图, V=v1

3、,v2,vn, E=e1,e2,em?关联矩阵关联矩阵(incidence matrix): M(D)=m(incidence matrix): M(D)=mijn?m,(每个顶点确定一行 ,每条边确定一列)?1, vi是ej的起点mij= 0, vi与ej不关联-1, vi是ej的终点?110000111100001011000111)(6543214321eeeeeevvvvDM6有向图关联矩阵(例)?110000111100001011000111)(6543214321eeeeeevvvvDMv1v2v4v3e1e2e3e5e4e67有向图关联矩阵有向图关联矩阵(性质性质)?每列和为零

4、: ?ni=1mij=0 ?每行绝对值和为d(v): d(vi)=?mj=1mij, 其中1的个数为d+(v), -1的个数为d-(v)?握手定理: ?ni=1?mj=1mij=0?平行边: 相同两列?110000111100001011000111)(6543214321eeeeeevvvvDM8无向图邻接矩阵?设G=是无向简单图,V=v1,v2,vn ?邻接矩阵(adjacence matrix): ?A(G)=aA(G)=aijn?n, aii=0, 1, vi与vj相邻,i?jaij= 0, vi与vj不相邻v1v2v4v3?0011001011011010)(43214321vvvv

5、vvvvGA9无向图邻接矩阵(性质)?A(G)对称: aij= aji?每行(列)和为顶点度: ?ni=1aij=d(vj)?握手定理: ?ni=1?nj=1aij=?ni=1d(vj)=2mv2v3?0011001011011010)(43214321vvvvvvvvGA10邻接矩阵与通路数?设A(D)=A=aijn?n, ?Ar=Ar-1?A (r?2), Ar=aij (r)n?n, ?定理1: aij (r)=从vi到vj长度为r的通路总数?ni=1?nj=1aij (r)=长度为r的通路总数?ni=1aii (r)=长度为r的回路总数. #整数乘和整数加11用邻接矩阵求通路数(例)?

6、21111101103111122A?21421031432431423A?746643246211664674A?0011001011011010)(43214321vvvvvvvvGAv1v2v4v312邻接矩阵与通路数邻接矩阵与通路数?设Ar=Ar-1?A,(r?2), Ar=a=aij(r)n?n, ?推论1: aii (2)=d(vi). #?推论2: G连通?距离d(vi,vj)=minr|aij(r)?0，i?j. #13连通矩阵连通矩阵?只考虑有无，不考虑有多少条?设G=是无向简单图, V=v1,v2,vn, ?连通矩阵连通矩阵: P(G)=p: P(G)=pijn?n,1,

7、若vi与vj连通pij=0, 若vi与vj不连通14连通矩阵连通矩阵(性质性质)?主对角线元素都是 1: ? vi? V, vi与vi连通?连通图: 所有元素都是1 ?伪对角阵: 对角块是连通分支的连通矩阵?设Br=A+A2+Ar= bij(r)n?n, 则? i?j, pij=1 ?bij(n-1) 0?)()()()(21kGPGPGPGP?15连通矩阵(例)v1v4?100000011000011000000111000111000111Pv3v2v6v516有向图邻接矩阵?设D=是有向图,V=v1,v2,vn ?邻接矩阵邻接矩阵(adjacence matrix): A(D)=a(ad

8、jacence matrix): A(D)=aijn?n, aij= 从vi到vj的边数v1v2v4v3?1100100001000120)(43214321vvvvvvvvDA17有向图邻接矩阵(性质)?每行和为出度: ?nj=1aij=d+(vi) ?每列和为入度: ?ni=1aij=d-(vj)?握手定理: ?ni=1?nj=1aij=?ni=1d-(vj)=m?环个数: ?ni=1aiiv1v2v4v3?1100100001000120)(43214321vvvvvvvvDA18邻接矩阵与通路数?设A(D)=A=aA(D)=A=aijn?n, ?Ar=Ar-1?A (r?2), Ar=

9、a=aij(r)n?n, ?定理2: aij(r)=从vi到vj长度为r的通路总数?ni=1?nj=1aij(r)=长度为r的通路总数?ni=1aii (r)=长度为r的回路总数19用邻接矩阵求通路数(例)v1v2v4v3?1100100001000120)(43214321vvvvvvvvDA?21001100100012002A?32002100110031003A?53003200210043004A?32002100110013202B?64004200220044203B?117007400430087204B20可达矩阵可达矩阵?设D=是有向图,V=v1,v2,vn, ?可达矩阵可

10、达矩阵: P(D)=p: P(D)=pijn?n,1, 从vi可达vjpij= 0, 从vi不可达vj21可达矩阵可达矩阵(性质性质)?主对角线元素都是 1: ? vi? V, 从vi可达vi?强连通图: 所有元素都是1 ?伪对角阵: 对角块是强连通分支的可达矩阵? i?j, pij=1 ? bij (n-1) 0?)()()()(21kDPDPDPDP?22图的运算图的运算?定义14.27 设图G1=, G2=,若 V1V2=? ，则称G1与G2 是不交的. 若 E1E2=? ，则称 E1与E2是不重的. 由定义知，不交的图必然是边不交的，但反之不真。23图的运算?定义14.28 设图G1=

11、, G2=为不含孤立点的两个图（它们同为无向图或同为有向图 ).(1)称以 V1V2为顶点集，以 E1E2 为边集的图为G1与 G2 的并图,记作 G1G2,即G1G2=.24图的运算(2)称以E1- E2为边集,以 E1- E2中边关联的顶点组成的集合为顶点集的图为G1与 G2的差图,记作 G1- G2.(3)称以E1E2为边集,以 E1E2中边关联的顶点组成的集合为顶点集的图为G1与 G2的交图,记作 G1G2.(4)称以E1E2为边集,以 E1E2中边关联的顶点组成的集合为顶点集的图为G1与 G2的交图,记作 G1G2.25图的运算图的运算在定义14.28中应注意以下几点：1.若G1=

12、G2,则G1G2= G1G2= G1(G2),而G1-G2= G2-G1=? ,这就是在图的定义中给出空图的概念的原因 .2.当G1与 G2边不重时,G1G2=? ,G1-G2= G1,G1G2=G1G2.3.两个图的环和可以并、交、差给出 : G1G2=(G1G2)-(G1G2)26第十四章基本要求1.理解与图的定义有关的诸多概念，以及它们之间的相互关系.2.深刻理解握手定理及其推论的内容，并能熟练地应用它们.3.深刻理解简单图、完全图、正则图、子图、补图、二部图等概念及它们的性质和相互关系，并熟练地应用这些性质和关系.4.深刻理解通路与回路的定义及其分类，掌握通路和回路的不同表示方法.5.

13、理解无向图的连通性、连通分支等概念.27第十四章基本要求6.深刻理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的点连通度和边连通度.7. 理解有向图连通性的概念及其分类,掌握判断有向连通图类型的方法.8. 掌握图的矩阵表示，熟练掌握用有向图的邻接矩阵求及各次幂求图中通路与回路数的方法.9. 会求有向图的可达矩阵.欧拉图与哈密顿图欧拉图与哈密顿图1、欧拉图、欧拉图2、哈密尔顿图3、最短路问题与货郎担问题.28欧拉图欧拉图历史背景：哥尼斯堡七桥问题与欧拉图其实，欧拉图是一笔画出的边不重复的回路 .30欧拉图的定义定义15.1 （1）欧拉通路经过图中每条边一次且仅一

14、次行遍所有顶点的通路. （2）欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路.（3）欧拉图具有欧拉回路的图.（4）半欧拉图具有欧拉通路而无欧拉回路的图.31欧拉图的几点说明?规定平凡图为欧拉图.?欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.?环不影响图的欧拉性. （1） （2） （3） （4） （5） （6） （1） 、 （4）为欧拉图， （2） ， （5）为半欧拉图，（3） ， （6）既不是欧拉图，也不是半欧拉图 . 在（3） ， （6）中各至少加几条边才能成为欧拉图？ N为何值时，无向完全图是欧拉图？为何值时，为半欧拉图？什么样的完全二部图是欧拉图？ 32 33定理15.1

15、无向图G是欧拉图当且仅当G连通且无奇度数顶证 若G为平凡图无问题. 下设G为n阶m条边的无向图必要性 设C为G中一条欧拉回路.（1）G连通显然.（2）? vi? V(G)，vi在C上每出现一次获2度，所以vi为偶度顶点. 由vi的任意性，结论为真. 无向欧拉图的判别法34无向欧拉图的判别法充分性.由于G为非平凡的连通图可知 , G中边数m 1.对m作归纳法.(1)m1时,由G的连通性及无奇度顶点可知 ,G只能是一个环,因而G为欧拉图. (2)设m k(k1)时结论成立,要证明mk+1时,结论也成立. G的连通性及无奇度顶点可知 ,(G)2.无论G是否为简单图,都可以用扩大路径法证明G中必含圈.

16、35设C为G中一个圈，删除C上的全部边，得G的生成子图G ? ,设G ?有s个连通分支G ?1,G ?2, ,G ?s,每个连通分支至多有k条且无奇度顶点,并且设G ?i与C的公共顶点为v*ji, i1,2, ,s,由归纳假设可知,G ?1,G ?2, ,G ? s都是欧拉图，因而都存在欧拉回路C ?i，i1,2, ,s。最后将C还原（即将删除的边重新加上 ），并从C上的某顶点vr开始行遍，每遇到v*ji，就行遍G ?i中的欧拉回路C ?i，i1,2, ,s，最后回到vr，得回路vrv*j1v*j1v*j2v*j2v*jsv*jsvr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它

17、是G中的欧拉回路.故G为欧拉图。从以上证明不难看出：欧拉图是若干个边不重的圈之并， 见示意图 3. 图 3 PLAY3637无向半欧拉图的判别法定理15.2 无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.证 必要性。设G是m条边的n阶无向图，因为 G为半欧拉图,因而G中存在欧拉通路（但不存在欧拉回路）设=vi0ej1vi1 vim-1ejmvim为G中一条欧拉通路， vi0vim.? vV(G)，若v不在的端点出现，显然 d(v)为偶数，若v在端点出现过,则d(v)为奇数,因为只有两个端点且不同,因而G中只有两个奇数顶点 .另外,G的连通性是显然的.38无向半欧拉图的判别法无向半欧拉图的

18、判别法充分性（利用定理（利用定理15.1）设u,v为G中的两个奇度顶点，令G? =G? (u,v)则G?连通且无奇度顶点，由定理15.1知G?为欧拉图，因而存在欧拉回路C，令?=C?(u,v)，则?为G中欧拉通路.39有向欧拉图的判别法定理15.3 有向图D 是欧拉图当且仅当D 是强连通的且每个顶点的入度都等于出度 .定理15.4 有向图D 是半欧拉图当且仅当D 是单向连通的,且D 中恰有两个奇度顶点 ,其中一个的入度比出度大1,另一个的出度比入度大 1,而其余顶点的入度都等于出度 . 40欧拉图的判别法欧拉图的判别法定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并

19、. 41例15.1 设G是非平凡的欧拉图，证明：(1) (G)2.(2) 对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。证 (1) 由定理15.5可知, ? eE(G),存在圈C,e在C中,因而p(G-e)=p(G), 故e不是桥. 由e的任意性(G)2,即G是2边-连通图。(2)? u,vV(G)，uv，由G的连通性可知，u,v之间必存在路径1,设G ?G-E(1),则在G ?中u与v还必连通，否则，u与v必处于G ?的不同的连通分支中，这说明在1上存在G中的桥，这与(1)矛盾。于是在G ?中存在u到v的路径2，显然1与2边不重，这说明u,v处于12形成的简单回路上。 例 设G是欧拉图，但G不是平凡图，也不是一个环，则 ?(G)?2. 证 只需证明G中不可能有桥（如何证明？） （1） （2）