《离散数学ch》PPT课件

《《离散数学ch》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五部分图论本部分主要内容图的基本概念欧拉图、哈密顿图树平面图支配集、覆盖集、独立集、匹配与着色1第十四章图的基本概念主要内容图通路与回路图的连通性图的矩阵表示图的运算预备知识多重集合——元素可以重复出现的集合无序集——AB={(x,y)

2、xAyB}214.1图定义14.1无向图G=,其中(1)V为顶点集，元素称为顶点(2)E为VV的多重集，其元素称为无向边，简称边实例设V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1

3、,v5),(v4,v5)}则G=为一无向图3有向图定义14.2有向图D=,只需注意E是VV的多重子集图2表示的是一个有向图，试写出它的V和E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的4相关概念1.图①可用G泛指图（无向的或有向的）②V(G),E(G),V(D),E(D)③n阶图2.有限图3.n阶零图与平凡图4.空图——5.用ek表示无向边或有向边6.顶点与边的关联关系①关联、关联次数②环③孤立点7.顶点之间的相邻与邻接关系58.邻域与关联集①vV(G)(G为无向图)v

4、的关联集②vV(D)(D为有向图)9.标定图与非标定图10.基图相关概念6多重图与简单图定义14.3(1)无向图中的平行边及重数(2)有向图中的平行边及重数（注意方向性）(3)多重图(4)简单图在定义14.3中定义的简单图是极其重要的概念7顶点的度数定义14.4(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)

5、,(D),(D)(5)奇顶点度与偶度顶点8定理14.1设G=为任意无向图，V={v1,v2,…,vn},

6、E

7、=m,则证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.本定理的证明类似于定理14.1握手定理定理14.2设D=为任意有向图，V={v1,v2,…,vn},

8、E

9、=m,则9握手定理推论推论任何图(无向或有向)中，奇度顶点的个数是偶数.证设G=为任意图，令V1={v

10、vVd(v)为奇数}V2={v

11、vVd(v)

12、为偶数}则V1V2=V,V1V2=，由握手定理可知由于2m,均为偶数，所以为偶数，但因为V1中顶点度数为奇数，所以

13、V1

14、必为偶数.10例1无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？解本题的关键是应用握手定理.设除3度与4度顶点外，还有x个顶点v1,v2,…,vx，则d(vi)2，i=1,2,…,x，于是得不等式3224+2x得x4,阶数n4+4+3=11.握手定理应用11图的度数列1.V={v1,v2,…,vn}为无向图G的顶点集，称d(v1),d(v2

15、),…,d(vn)为G的度数列2.V={v1,v2,…,vn}为有向图D的顶点集，D的度数列：d(v1),d(v2),…,d(vn)D的出度列：d+(v1),d+(v2),…,d+(vn)D的入度列：d(v1),d(v2),…,d(vn)3.非负整数列d=(d1,d2,…,dn)是可图化的，是可简单图化的.易知：(2,4,6,8,10)，(1,3,3,3,4)是可图化的，后者又是可简单图化的，而(2,2,3,4,5)，(3,3,3,4)都不是可简单图化的，特别是后者也不是可图化的12图的同构定义14.5设G1

16、=,G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2,对于vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(vj))E2（E1当且仅当E2)并且,(vi,vj)（）与(f(vi),f(vj))（）的重数相同，则称G1与G2是同构的，记作G1G2.图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，但它们全不是充分条件：①边数相同，顶点数相同;②度数列相同;

17、③对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构判断两个图同构是个难题13图同构的实例图中(1)与(2)的度数列相同，它们同构吗？为什么？(1)(2)(3)(4)图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.(1)(2)14n阶完全图与竞赛图定义14.6(1)n(n1)阶无向完全图——每个顶点与其余顶点均相邻的无