《图论基本概念》PPT课件

1,第五部分图论,本部分主要内容图的基本概念欧拉图、哈密顿图树,2,绪论,图论的历史：图论的第一篇论文是瑞士数学家欧拉（Euler）发表于1736年出版的圣彼得堡科学院刊物中。讨论一个所谓KonigsbergSevenBridgesProblem。,3,绪论,图论的作用：图与计算机：计算机中数据结构，离不开数组、串、各种链接表、树和图，因此图是计算机中数据表示、存储和运算的基础图与网络：最大流问题：假设从城市P到城市Q的一个公路网，公路网中每段公路上每天可以通过的汽车的数量有上限，那么经过该公路网，每天最多可以有多少辆汽车从城市P开到城市Q？最优支撑树问题：某一地区有若干个主要城市，拟修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假设已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,4,第十四章图的基本概念,主要内容图通路与回路图的连通性图的矩阵表示图的运算预备知识多重集合元素可以重复出现的集合无序集AB=(x,y)|xAyB,5,14.1图,定义14.1无向图G=,其中(1)V为顶点集，元素称为顶点Vertex(2)E为VV的多重集，其元素称为无向边，简称边Edge实例设V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)则G=为一无向图,6,有向图,定义14.2有向图D=,只需注意E是VV的多重子集图2表示的是一个有向图，试写出它的V和E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的,7,相关概念,1.图可用G泛指图（无向的或有向的）V(G),E(G),|V(G)|,|E(G)|n阶图：n个顶点的图2.有限图3.n阶零图（0条边）与平凡图（1个顶点）4.空图（运算中出现）5.用ek表示无向边或有向边,8,相关概念,6.顶点与边的关联关系关联、关联次数环孤立点7.顶点之间的相邻与邻接关系,9,8.邻域与关联集vV(G)(G为无向图),v的关联集,vV(D)(D为有向图),9.标定图与非标定图(顶点和边指定编号的）10.基图（有向图的有向边改为无向边）,相关概念,10,多重图与简单图,定义14.3(1)无向图中的平行边及重数关联一对顶点的边多于一条，条数称为重数(2)有向图中的平行边及重数（注意方向性）(3)多重图(4)简单图（无平行边和环）简单图是极其重要的概念,11,顶点的度数,定义14.4(1)设G=为无向图,vV,d(v)v的度数,简称度(2)设D=为有向图,vV,d+(v)v的出度d(v)v的入度d(v)v的度或度数(3)(G)（最大度）,(G)（最小度）无向图中(4)+(D),+(D),(D),(D),(D),(D)(5)度数为1的点称为悬挂点，关联的边为悬挂边；奇顶点度与偶度顶点,12,定理14.1设G=为任意无向图，V=v1,v2,vn,|E|=m,则,证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.,此二定理是欧拉1736年给出，是图论的基本定理,握手定理,定理14.2设D=为任意有向图，V=v1,v2,vn,|E|=m,则,13,握手定理推论,推论任何图(无向或有向)中，奇度顶点的个数是偶数.证设G=为任意图，令V1=v|vVd(v)为奇数V2=v|vVd(v)为偶数则V1V2=V,V1V2=，由握手定理可知由于2m,均为偶数，所以为偶数，但因为V1中顶点度数为奇数，所以|V1|必为偶数.,14,图的度数列,1.V=v1,v2,vn为无向图G的顶点集，称d(v1),d(v2),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)都不是可简单图化的，特别是后者也不是可图化的,15,图的同构,定义14.5设G1=,G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2,对于vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(vj)E2（E1当且仅当E2)并且,(vi,vj)（）与(f(vi),f(vj)（）的重数相同，则称G1与G2是同构的，记作G1G2.,图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，但它们全不是充分条件：边数相同，顶点数相同;度数列相同;对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构判断两个图同构是个难题,16,图同构的实例,图中(1)与(2)的度数列相同，它们同构吗？为什么？,(1)(2)(3)(4),图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.,(1)(2),17,n阶完全图与竞赛图,定义14.6(1)n(n1)阶无向完全图每个顶点与其余顶点均相邻的无向简单图，记作Kn.简单性质：边数(2)n(n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质：(3)n(n1)阶竞赛图基图为Kn的有向简单图.简单性质：边数,18,n阶k正则图,(1)为K5，(2)为3阶有向完全图，(3)为4阶竞赛图.,(1)(2)(3),定义14.7n阶k正则图=k的无向简单图简单性质：边数（由握手定理得）Kn是n1正则图，彼得松图（见书上图14.3(1)所示，记住它）,19,子图,定义14.8G=,G=(1)GGG为G的子图，G为G的母图(2)若GG且V=V，则称G为G的生成子图(3)若VV或EE，称G为G的真子图(4)V（VV且V）的导出子图，记作GV(5)E（EE且E）的导出子图，记作GE,20,例2画出K4的所有非同构的生成子图,实例,21,补图,定义14.9设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.若G,则称G是自补图.相对于K4,求上面图中所有图的补图，并指出哪些是自补图.问：互为自补图的两个图的边数有何关系？,22,14.2通路与回路,定义14.11给定图G=（无向或有向的），G中顶点与边的交替序列=v0e1v1e2elvl，vi1,vi是ei的端点.(1)通路与回路：为通路；若v0=vl，为回路，l为回路长度.(2)简单通路与回路：所有边各异，为简单通路，又若v0=vl，为简单回路(3)初级通路(路径)与初级回路(圈)：中所有顶点各异，则称为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所有的边各异，则称为初级回路(圈)(4)复杂通路与回路：有边重复出现,23,几点说明,表示法定义表示法只用边表示法只用顶点表示法（在简单图中）混合表示法环（长为1的圈）的长度为1，两条平行边构成的圈长度为2，无向简单图中，圈长3，有向简单图中圈的长度2.不同的圈（以长度3的为例）定义意义下无向图：图中长度为l（l3）的圈，定义意义下为2l个有向图：图中长度为l（l3）的圈，定义意义下为l个同构意义下：长度相同的圈均为1个试讨论l=3和l=4的情况,24,通路与回路的长度,定理14.5在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n1的初级通路（路径）.定理14.6在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路.推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于或等于n的初级回路.,25,14.3图的连通性,无向图的连通性(1)顶点之间的连通关系：G=为无向图若vi与vj之间有通路，则vivj是V上的等价关系R=|u,vV且uv(2)G的连通性与连通分支若u,vV，uv，则称G连通V/R=V1,V2,Vk，称GV1,GV2,GVk为连通分支，其个数p(G)=k(k1)；k=1，G连通,26,短程线与距离,(3)短程线与距离u与v之间的短程线：uv，u与v之间长度最短的通路u与v之间的距离：d(u,v)短程线的长度d(u,v)的性质：d(u,v)0,uv时d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w),27,无向图的连通度,1.删除顶点及删除边Gv从G中将v及关联的边去掉GV从G中删除V中所有的顶点Ge将e从G中去掉GE删除E中所有边2.点割集与边割集点割集与割点定义14.16G=,VVV为点割集p(GV)p(G)且有极小性v为割点v为点割集定义14.17G=,EEE是边割集p(GE)p(G)且有极小性e是割边（桥）e为边割集,28,点割集与割点,例3v1,v4，v6是点割集，v6是割点.v2,v5是点割集吗？e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥，e7,e9,e5,e6是边割集吗？,几点说明：Kn中无点割集，Nn中既无点割集，也无边割集，其中Nn为n阶零图.若G连通，E为边割集，则p(GE)=2，V为点割集，则p(GV)2,29,点连通度与边连通度,定义14.18G为连通非完全图点连通度(G)=min|V|V为点割集规定(Kn)=n1若G非连通，(G)=0若(G)k，则称G为k-连通图定义14.19设G为连通图边连通度(G)=min|E|E为边割集若G非连通，则(G)=0若(G)r，则称G是r边-连通图图中，=1，它是1-连通图和1边-连通图,30,几点说明,(Kn)=(Kn)=n1G非连通，则=0若G中有割点，则=1，若有桥，则=1若(G)=k,则G是1-连通图，2-连通图，k-连通图，但不是(k+s)-连通图，s1若(G)=r,则G是1-边连通图，2-边连通图，r-边连通图，但不是(r+s)-边连通图，s1,之间的关系.定理7.5(G)(G)(G)请画出一个0，证明D中存在长度max+,+1的圈.,为D中长度+1的有向圈,练习3,50,(1)D中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？(3)D是哪类连通图?(4)D中v1到v4长度为1,2,3,4的通路各多少条？其中几条是非初级的简单通路？(5)D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型.(6)D中长度为4的通路（不含回路）有多少条？(7)D中长度为4的回路有多少条？(8)D中长度4的通路有多少条？其中有几条是回路？(9)写出D的可达矩阵.,4有向图D如图所示，回答下列诸问：,练习4,51,解答,(1)D中有3种非同构的圈，长度分别为1,2,3，请画出它们的图形.(2)D中有3种非圈的非同构的简单回路，它们的长度分别为4,5,6.请画出它们的图形来.(3)D是强连通的（为什么？）为解(4)(8)，只需先求D的邻接矩阵的前4次幂.,52,(4)v1到v4长度为1,2,3,4的通