最新离散数学屈婉玲第九章PPT学习课件.ppt

《最新离散数学屈婉玲第九章PPT学习课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章图的基本概念主要内容图通路与回路图的连通性图的矩阵表示预备知识多重集合——元素可以重复出现的集合无序集——AB={(x,y)

2、xAyB}214.1图定义9.1无向图G=,其中(1)V为非空有穷集,称为顶点集，其元素称为顶点(2)E为VV的多重有穷集,称为边集,其元素称为无向边,简称边例无向图G=,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}有向图定义9.2有向图D=,其中(1)V为非空有穷集,称为顶点集，其元素称为顶点(2)

3、E为VV的多重有穷集,称为边集,其元素称为有向边,简称边例有向图D=,其中V={a,b,c,d}E={,,,,,,}注意：图的集合表示与图形表示之间的对应4相关概念1.无向图和有向图通称图.记顶点集V(G),边集E(G).2.图的阶,n阶图.3.n阶零图Nn,平凡图N1.4.空图.5.标定图与非标定图.6.有向图的基图.7.无向图中顶点与边的关联及关联次数,顶点与顶点、边与边的相邻关系.8.有向图中顶点与边的关联,顶点与顶点、边与边的相邻关系.9.环,孤立点.5多重图与简单图定义9.3无向图中关联同一

4、对顶点的2条和2条以上的边称为平行边.有向图中2条和2条以上始点、终点相同的边称为平行边.平行边的条数称为重数.含平行边的图称为多重图,不含平行边和环的图称为简单图.定义9.4设G=为无向图,vV,称v作为边的端点的次数之和为v的度数,简称度,记作d(v).设D=为有向图,vV,称v作为边的始点的次数之和为v的出度,记作d+(v);称v作为边的终点的次数之和为v的入度,记作d(v);称d+(v)+d(v)为v的度数,记作d(v).6顶点的度数设G=为无向图,G的最大度(G)=max{d(v)

5、vV}G的最小度(G)=min{d(v)

6、v

7、V}设D=为无向图,D的最大度(D)=max{d(v)

8、vV}D的最小度(D)=min{d(v)

9、vV}D的最大出度+(D)=max{d+(v)

10、vV}D的最小出度+(D)=min{d+(v)

11、vV}D的最大入度(D)=max{d(v)

12、vV}D的最小入度(D)=min{d(v)

13、vV}悬挂顶点:度数为1的顶点,悬挂边:与悬挂顶点关联的边.偶度(奇度)顶点:度数为偶数(奇数)的顶点7实例d(v1)=4,d(v2)=4,d(v3)=2,d(v4)=1,d(v5)=3.=4,=1.v4是悬挂点,e7是悬挂边.d+(a)=4,d(a)=1,

14、d(a)=5,d+(b)=0,d(b)=3,d(b)=3,d+(c)=2,d(c)=1,d(c)=3,d+(d)=1,d(d)=2,d(d)=3,+=4,+=0,=3,=1,=5,=3.8定理9.1在任何无向图中,所有顶点的度数之和等于边数的2倍.证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.握手定理定理9.2在任何有向图中，所有顶点的度数之和等于边数的2倍;所有顶点的入度之和等于所有顶点的出度之和,都等于边数.推论任何图(无向或有向)中，奇度顶点的个数是偶数.证由握手定理,所有顶点的度数之和是偶数,而

15、偶度顶点的度数之和是偶数,故奇度顶点的度数之和也是偶数.所以奇度顶点的个数必是偶数．9例1无向图G有16条边，3个4度顶点，4个3度顶点，其余均为2度顶点度，问G的阶数n为几？解本题的关键是应用握手定理.设除3度与4度顶点外，还有x个顶点,由握手定理,162=32=34+43+2x解得x=4,阶数n=4+4+3=11.握手定理应用定理9.3设G为任意n阶无向简单图，则(G)n1．10图的同构定义9.5设G1=,G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2,使得vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(v

16、j))E2（E1当且仅当E2)并且,(vi,vj)（）与(f(vi),f(vj))（）的重数相同，则称G1与G2是同构的，记作G1G2.例图同构的实例(1)(2)(3)(4)(1)与(2),(3)与(4),(5)与(6)均不同构.(5)(6)说明:1.图的同构关系具有自反性、对称性和传递性.2.判断两个图同构是个难题12图同构的实例所有4阶3条边非同构的简单无向图所有3