离散数学-耿素云PPT(第5版)5.1.ppt

《离散数学-耿素云PPT(第5版)5.1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1图论2图论部分第5章图的基本概念第6章特殊的图第7章树3第5章图的基本概念5.1无向图及有向图5.2通路,回路和图的连通性5.3图的矩阵表示5.4最短路径,关键路径和着色45.1无向图及有向图无向图与有向图顶点的度数握手定理简单图完全图子图补图5无向图多重集合:元素可以重复出现的集合无序积:AB={(x,y)

2、xAyB}定义无向图G=,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为VV的多重子集，其元素称为无向边，简称边.例如,G=,其中V={v1,v2,…,v5},E={(v1,v1),(

3、v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}6有向图定义有向图D=,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为VV的多重子集，其元素称为有向边，简称边.D的基图:用无向边代替有向边如D=,其中V={a,b,c,d}E={,,,,,,}图的数学定义与图形表示,在同构意义下一一对应7无向图与有向图(续)通常用G表示无向图,D表示有向图,也常用G泛指无向图和有向图.V(G),E(G),

4、V(D),E(D):G和D的顶点集,边集.n阶图:n个顶点的图零图:E=平凡图:1阶零图空图:V=8顶点和边的关联与相邻定义设e=(u,v)是无向图G=的一条边,称u,v为e的端点,e与u(v)关联.若uv,则称e与u(v)的关联次数为1;若u=v,则称e为环,此时称e与u的关联次数为2;若w不是e端点,则称e与w的关联次数为0.无边关联的顶点称作孤立点.定义设无向图G=,u,vV,e,eE,若(u,v)E,则称u,v相邻;若e,e至少有一个公共端点,则称e,e相邻.对有向图有类似定义.设e=u,v

5、是有向图的一条边,又称u是e的始点,v是e的终点,u邻接到v,v邻接于u.9顶点的度数设G=为无向图,vV,v的度数(度)d(v):v作为边的端点次数之和悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=max{d(v)

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

7、vV}例如d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环10顶点的度数(续)设D=为有向图,vV,v的出度d+(v):v作为边的始点次数之和v的入度d(v):

8、v作为边的终点次数之和v的度数(度)d(v):v作为边的端点次数之和d(v)=d+(v)+d-(v)D的最大出度+(D)=max{d+(v)

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

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

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

12、vV}最大度(D)=max{d(v)

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

14、vV}11例例d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+(D)=4,+(D)=0,(D)=3,(D)=1,

15、(D)=5,(D)=3.12图论基本定理——握手定理定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.证G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.有向图的每条边提供一个入度和一个出度,故所有顶点入度之和等于出度之和等于边数.推论任意无向图和有向图的奇度顶点个数必为偶数.13图的度数列设无向图G的顶点集V={v1,v2,…,vn}G的度数列:d(v1),d(v2),…,d(vn)如右图度数列:4,4,2,1,3设有向图

16、D的顶点集V={v1,v2,…,vn}D的度数列:d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)如右图度数列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,214握手定理的应用例1(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗?解不可能.它们都有奇数个奇数.例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n

17、815握手定理的应用(续)例3证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法.假设存在这样的多面体,作无向图G=,其中V={v

18、v为多面体的面},E={(u,v)

19、