《图论基本概念》PPT课件

《《图论基本概念》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五部分图论本部分主要内容图的基本概念欧拉图、哈密顿图树1绪论图论的历史：图论的第一篇论文是瑞士数学家欧拉（Euler）发表于1736年出版的圣彼得堡科学院刊物中。讨论一个所谓KonigsbergSevenBridgesProblem。2绪论图论的作用：图与计算机：计算机中数据结构，离不开数组、串、各种链接表、树和图，因此图是计算机中数据表示、存储和运算的基础图与网络：最大流问题：假设从城市P到城市Q的一个公路网，公路网中每段公路上每天可以通过的汽车的数量有上限，那么经过该公路网，每天最多可以有多少辆汽车从城市P开到城市Q？最优支撑树问题：某一地区有若

2、干个主要城市，拟修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假设已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？3第十四章图的基本概念主要内容图通路与回路图的连通性图的矩阵表示图的运算预备知识多重集合——元素可以重复出现的集合无序集——AB={(x,y)

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

4、…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}则G=为一无向图5有向图定义14.2有向图D=,只需注意E是VV的多重子集图2表示的是一个有向图，试写出它的V和E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的6相关概念1.图①可用G泛指图（无向的或有向的）②V(G),E(G),

5、V(G)

6、,

7、E(G)

8、③n阶图：n个顶点的图2.有限图3.n阶零图（0条边）与平凡图（1个顶点）4.空图——（运算中出现）5.用ek表示无向边或有向边7

9、相关概念6.顶点与边的关联关系①关联、关联次数②环③孤立点7.顶点之间的相邻与邻接关系88.邻域与关联集①vV(G)(G为无向图)v的关联集②vV(D)(D为有向图)9.标定图与非标定图(顶点和边指定编号的）10.基图（有向图的有向边改为无向边）相关概念9多重图与简单图定义14.3(1)无向图中的平行边及重数关联一对顶点的边多于一条，条数称为重数(2)有向图中的平行边及重数（注意方向性）(3)多重图(4)简单图（无平行边和环）简单图是极其重要的概念10顶点的度数定义14.4(1)设G=为无向图,vV,d(v)——v的度数,简称度(2)

10、设D=为有向图,vV,d+(v)——v的出度d(v)——v的入度d(v)——v的度或度数(3)(G)（最大度）,(G)（最小度）无向图中(4)+(D),+(D),(D),(D),(D),(D)(5)度数为1的点称为悬挂点，关联的边为悬挂边；奇顶点度与偶度顶点11定理14.1设G=为任意无向图，V={v1,v2,…,vn},

11、E

12、=m,则证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.此二定理是欧拉1736年给出，是图论的基本定理握手定理定理14.2设

13、D=为任意有向图，V={v1,v2,…,vn},

14、E

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

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

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

18、V1

19、必为偶数.13图的度数列1.V={v1,v2,…,vn}为无向图G的顶点集，称d(v1),d(v2),…,d(vn)为G的度数列2.V={v1,v2,…,vn}为有向图D的顶点集，D的度数列：d(v

20、1),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)都不是可简单图化的，特别是后者也不是可图化的14图的同构定义14.5设G1=,G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2,对于vi,vjV1,(vi,vj)E1

21、当且仅当(f(vi),f(vj))E2（E1当且仅当