图论基本概念.pptx
《图论基本概念.pptx》由会员分享,可在线阅读,更多相关《图论基本概念.pptx(52页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1绪论图论的作用:l图与计算机:计算机中数据结构,离不开数组、串、各种链接表、树和图,因此图是计算机中数据表示、存储和运算的基础 l图与网络:最大流问题:假设从城市P到城市Q的一个公路网,公路网中每段公路上每天可以通过的汽车的数量有上限,那么经过该公路网,每天最多可以有多少辆汽车从城市P开到城市Q?最优支撑树问题:某一地区有若干个主要城市,拟修建高速公路把这些城市连接起来,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假设已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总成本最小?第1页/共52页2第十四章 图的基本概念主要内容l图l
2、通路与回路l图的连通性l图的矩阵表示l图的运算预备知识l多重集合元素可以重复出现的集合l无序集AB=(x,y)|xAyB第2页/共52页314.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=为一无向图第3页/共52页4有向图定义14.2 有向图D=,只需注意E是VV 的多重子集图2表示的是一个有向图,试写出它的V 和 E 注意:图的数学定义与图形表
3、示,在同构(待叙)的意义下是一一对应的第4页/共52页5相关概念1.图 可用G泛指图(无向的或有向的)V(G),E(G),|V(G)|,|E(G)|n阶图:n 个顶点的图2.有限图3.n 阶零图(0条边)与平凡图(1个顶点)4.空图(运算中出现)5.用 ek 表示无向边或有向边第5页/共52页6相关概念6.顶点与边的关联关系 关联、关联次数 环 孤立点7.顶点之间的相邻与邻接关系第6页/共52页78.邻域与关联集 v V(G)(G为无向图)v 的关联集 v V(D)(D为有向图)9.标定图与非标定图(顶点和边指定编号的)10.基图(有向图的有向边改为无向边)相关概念第7页/共52页8多重图与简
4、单图定义14.3 (1)无向图中的平行边及重数 关联一对顶点的边多于一条,条数称为重数(2)有向图中的平行边及重数(注意方向性)(3)多重图(4)简单图(无平行边和环)简单图是极其重要的概念 第8页/共52页9顶点的度数定义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的点称为悬挂点,关联的边为悬挂边;奇顶点度与偶度顶点第9页/共52页10定理定理14.1 设设G=为任意
5、无向图,为任意无向图,V=v1,v2,vn,|E|=m,则则证 G中每条边(包括环)均有两个端点,所以在计算G中各顶点度数之和时,每条边均提供2度,m 条边共提供 2m 度.此二定理是欧拉此二定理是欧拉17361736年给出,是图论的基本定理年给出,是图论的基本定理握手定理定理14.2 设D=为任意有向图,V=v1,v2,vn,|E|=m,则第10页/共52页11握手定理推论推论 任何图(无向或有向)中,奇度顶点的个数是偶数.证 设G=为任意图,令 V1=v|vV d(v)为奇数 V2=v|vV d(v)为偶数 则V1V2=V,V1V2=,由握手定理可知由于2m,均为偶数,所以 为偶数,但因为
6、V1中顶点度数为奇数,所以|V1|必为偶数.第11页/共52页12图的度数列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)都不是可简单图化的,特别是后者也不是可图化的
7、第12页/共52页13图的同构定义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.l图之间的同构关系具有自反性、对称性和传递性.l能找到多条同构的必要条件,但它们全不是充分条件:边数相同,顶点数相同;度数列相同;对应顶点的关联集及邻域的元素个数相同,等等 若破坏必要条件,则两图不同构l判断两个图同构是个难题第13页/共52页14图同构的实例图中(1)与(2)
8、的度数列相同,它们同构吗?为什么?(1)(2)(3)(4)图中,(1)与(2)不同构(度数列不同),(3)与(4)也不同构.(1)(2)第14页/共52页15n 阶完全图与竞赛图定义14.6(1)n(n1)阶无向完全图每个顶点与其余顶点均相邻的无向简单图,记作 Kn.简单性质:边数(2)n(n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质:(3)n(n1)阶竞赛图基图为Kn的有向简单图.简单性质:边数 第15页/共52页16n 阶 k 正则图(1)为K5,(2)为3阶有向完全图,(3)为4阶竞赛图.(1)(2)(3)定义14.7 n 阶k正则图=k 的无向简单图简单
9、性质:边数(由握手定理得)Kn是 n 1正则图,彼得松图(见书上图14.3(1)所示,记住它)第16页/共52页17子图定义14.8 G=,G=(1)GG G为G的子图,G为G的母图(2)若GG且V=V,则称G为G的生成子图(3)若VV或EE,称G为G的真子图(4)V(VV且V)的导出子图,记作GV(5)E(EE且E)的导出子图,记作GE第17页/共52页18例2 画出K4的所有非同构的生成子图实例第18页/共52页19补图定义14.9 设G=为n阶无向简单图,以V为顶点集,以所有使G成为完全图Kn的添加边组成的集合为边集的图,称为G的补图,记作 .若G ,则称G是自补图.相对于K4,求上面图
10、中所有图的补图,并指出哪些是自补图.问:互为自补图的两个图的边数有何关系?第19页/共52页2014.2 通路与回路定义14.11 给定图G=(无向或有向的),G中顶点与边的交替序列 =v0e1v1e2elvl,vi1,vi 是 ei 的端点.(1)通路与回路:为通路;若 v0=vl,为回路,l 为回路长 度.(2)简单通路与回路:所有边各异,为简单通路,又若v0=vl,为简单回路(3)初级通路(路径)与初级回路(圈):中所有顶点各异,则称 为初级通路(路径),又若除v0=vl,所有的顶点各不相同且所有的边各异,则称 为初级回路(圈)(4)复杂通路与回路:有边重复出现第20页/共52页21几点
11、说明表示法 定义表示法 只用边表示法 只用顶点表示法(在简单图中)混合表示法环(长为1的圈)的长度为1,两条平行边构成的圈长度为 2,无向简单图中,圈长3,有向简单图中圈的长度2.不同的圈(以长度3的为例)定义意义下 无向图:图中长度为l(l3)的圈,定义意义下为2l个 有向图:图中长度为l(l3)的圈,定义意义下为l个 同构意义下:长度相同的圈均为1个试讨论l=3和l=4的情况第21页/共52页22通路与回路的长度定理14.5 在n 阶图G中,若从顶点vi 到vj(vivj)存在通路,则从vi 到 vj 存在长度小于或等于n1 的通路.推论 在 n 阶图G中,若从顶点vi 到 vj(vivj
12、)存在通路,则从vi 到vj 存在长度小于或等于n1的初级通路(路径).定理14.6 在一个n 阶图G中,若存在 vi 到自身的回路,则一定存在vi 到自身长度小于或等于 n 的回路.推论 在一个n 阶图G中,若存在 vi 到自身的简单回路,则一定存在长度小于或等于n 的初级回路.第22页/共52页2314.3 图的连通性无向图的连通性(1)顶点之间的连通关系:G=为无向图 若 vi 与 vj 之间有通路,则 vivj 是V上的等价关系 R=|u,v V且uv(2)G的连通性与连通分支 若u,vV,uv,则称G连通 V/R=V1,V2,Vk,称GV1,GV2,GVk为连通分 支,其个数 p(G
13、)=k (k1);k=1,G连通第23页/共52页24短程线与距离(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)第24页/共52页25无向图的连通度1.删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2.点割集与边割集 点割集与割点定义14.16 G=,VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集定义14.17 G
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本概念
限制150内