图和子图(1).ppt

1、图和子图(1),四川师范大学数学与软件科学学院 周思波,1.1 基本概念,现实世界的许多现象可以用一类图形来描述，这种图形由一个点集和连接这个点集中某些点对的线所构成例如用点表示车站，线表示连接车站与车站的道路；或者用点表示人，连线表示一对朋友在这种图形中，人们主要感兴趣的是：两点是否被一条线所连接，而连线的长短曲直则无关紧要大量的这类事实的数学抽象，产生了图的概念,图的概念,有序三元组GV(G)，E(G)，G称为一个图，其中： ) V(G) 称为顶点集合； ) E(G)V(G)=，E(G)称为边集合； ) G是E(G)到(a,b)|a,bV(G)的映射，称为关联函数 V(G)中的元素称为顶点

2、，E(G)中的元素称为边V(G)所含元素的个数即顶点个数称为图的阶，用|V(G)|表示E(G)所含元素的个数称为G的边数，用|E(G)|表示我们用G(p，q)表添一个阶为p、边数为q的图G，这时也说G是一个(p，q)图,例题,GV(G)， E(G)，G，其中： V(G)=v1,v2,v3,v4，E(G)=e1,e2,e3,e4,e5,e6， G定义为： G(e1)=v2v3，G(e2)=v3v4 G(e3)=v4v4，G(e4)=v2v4 G(e5)=v2v3，G(e6)=v1v3,e1,e6,e5,e4,e3,e2,相关概念,在图G V(G)， E(G)，G中,若eE(G)，u,vV(G)，

3、而G(e)=(u,v) ，则称u和v是e的端点，或e和u,v关联，此时称u和v是邻接的。若两条不同的边ei和ej有一个公共端点，则称是邻接的，不与任何边邻接的边称为孤立边，不与任何边关联的顶点称为孤立点。两端重合的边称为环，端点不同的边称为杆。 若V(G) 和E(G)都是有限集，则称G为有限图。G(0,0)称为空图， E(G)=即G是由孤立点所组成，称为零图。G(1,0)称为平凡图。,简单图和完全图,图中若连接两个相同顶点的边的条数大于1，则说这对顶点间有重边相连同一对顶点间边的条数称为边的重数，既没有环也没有重边的图称为简单图，否则称为伪图，没有环的伪图称为多重图 每对不同的顶点均有边相连的

4、简单图称为完全图n阶完全图记为Kn 定理1.1：Kn有,条边,二分图,图G的顶点集V(G)若能分成两个子集V1和V2，使得G的每条边有一个端点在V1 ，另一个端点在V2中，则G称为二分图或偶图这样一个把V(G)分成两个集合V1 、V2的分划(V1,V2)称为G的一个二分划 设简单二分图G的二分划为(V1 ,V2)，如果V1的每个顶点与V2的每一个顶点都邻接，则G称为完全二分图若| V1 |=m,| V2 |=n,则这样的图记为Km,n 定理1.2 Km,n有mn条边。,补图,G是简单图，如果简单图GC满足， ) V(GC)= V(G) ) V(GC)中两点当且仅当它们在G中不邻接时在GC中邻接

5、 那么GC称为G的补图,G：,GC ：,平面图,在保持图的顶点和边的关联关系不变的情况下，一个图可以作出许多图形如果一个图具有这样的图形，它的边仅在顶点处相交，则称它为平面图 判断图1是否为平面图？,图1：,图2：,恒同和同构,两个图H和G，如果V(H)V(G)，E(H)E(G)且H G，那么H和G就称为是恒同的，恒同的图当然可以用一个图形来表示 GV(G)，E(G)，G 和HV(H)，E(H)，H，若存在1-1对应偶(,)，:V(G) V(H)；:E(G) E(H)，使得当且仅当H(e)=(u) (v)时， G(e)=uv，则说这两个图同构，记为GH,度与正则图,设vV(G)，G中与顶点v关

6、联的边的数目称为v在G中的度(次)，记为dG(v)或d(v) 一个环的端点的度数计为2 如果d(v)是奇数，就说v是奇顶点；如果d(v)是偶数，就说v是偶顶点 如果一个图的每一个顶点都具有相同的度，则称这个图是正则图。每个顶点的度均为k的正则图，称为k-正则图,有关度的定理,定理1.3 图G中各顶点度数之和等于边数的2倍。,推论1.4 任意一个图奇顶点的个数是偶数,推论1.5 正则图的阶与各顶点度数不全为奇数,子图,设H和G是两个图，如果V(H)是V(G)的子集，E(H)是E(G)的子集且H 是 G在E(H)内的导出函数，那么H称为G的子图，此时G称为H的母图，记为,如果 而HG，则说H是G的

7、真子图，记为,设H是G的子图，如果V(H)=V(G)，则H称为G的生成子图。,导出子图,设V是V(G)的非空子集，H是G的一个子图，如果：)V(H)=V；)E(H)=e|eE(G), G(e)=uv，u,vV；) H 是G在E(H)上的导出函数。 那么H称为由V导出的G的子图，记为GV 导出子图GV-V记为G-V，它是从G中删除V中的顶点及与这些顶点相关联的边所得到的子图。若V=v，则把G-v简记为G-v，称为G的删点子图。,同理以E中的端点的全体为集所组成的子图称为由E导出的子图，记为GE。删去边集合E中的边之后得出的导出子图记为G-E G-e,G+e,例,G,G的一个生成子图,G-2,3,

8、G3,4,6,G-e,g,h,Ga,c,e,g,h,子图的运算(并、交、差、环和),G1,G2,G1 G2,G1 G2,G2- G1,G1 G2,通路和回路,图G中一个点边交替的非空有限序列wv0e1v1e2v2envn称为G的一个途径其中vi是顶点，ei是边，对于1in，e的端点是vi-1和vi，v0和vn分别称为途径的起点和终点，而v1,v2,vn-1称为途径的内顶点，整数n称为途径w的长 途径w中若干相连项构成的子序列viei+1vi+1ejvj称为w的(vi,vj)节将序列w逆转后所得途径vnenvn-1v1e1v0记为w-1 在简单图中，途径w可以由它的顶点序列v0e1v1e2v2e

9、nvn所确定因此在简单图中可以用顶点序列表示一个途径,相关概念,若途径的边e1, e2 , , en互不相同，则称之为链，此外，若顶点也互不相同，则称w为通路 对G的两个顶点u和v,如果在G中存在一条(u,v)的通路，则称顶点u与v是连通的如果图G中的任意一对顶点都是连通的，则G称为连通图设G的顶点u与v是连通的，那么G中最短的(u,v)通路的长就称为u与v的距离，记为d(u,v) ,回路,一条具有正的长度且起点、终点重合的途径称为闭途径类似可以定义闭链、闭通路闭通路称为回路(亦称圈)长为K的回路称为K-回路 定理1.7 对于阶数不小于2的图G，当且仅当G不含奇回路时，它才是二分图 证明：充分

10、性易证,下面证必要性。设G是无奇回路的连通图，任取G的一个顶点u并将V(G)作如下的划分(V1,V2)： V1=x|xV(G) ，d(u,x)是偶数 V2=y|yV(G) ，d(u,y)是奇数 然后证明这恰是G的一个二分划。,设v和w是V1的两个顶点，又设P是最短(u,v)-通路，Q是最短(u,w)-通路，以u1记P和Q的最后一个公共顶点，因为P、Q是最短通路，P和Q的(u, u1)-节也是最短的(u, u1)-通路，因此具有相同的长度 又因P和Q的长度是偶数，所以P上(u1,v)-节P1的长度与Q上(u1,w)-节Q1的长度具有相同的奇偶性，由此推出(v,w)通路P1-1Q1的长度为偶数，若

11、v与w邻接，则wv是G的一条奇回路，此与假设矛盾，故V1中任意两点均不邻接，同理V2中任意两个顶点也不邻接，因此G是二分图。,最短通路问题,如果对图G的一条边，赋以一个实数w(e)，称为这条边的权，那么G连同它的边上的权称为赋权图 若G是一个赋权图，H是G的子图，那么H的权是它所有边的权之和，即,如果P是G的一条通路，通路上各边的权也称为该边的长度，通路上各边的长度之和称为通路的长所谓最短通路问题，就是在G中所有(u0,v0)-通路中，寻找一条长度最小的(u0,v0)-通路u0到v0的最短通路长记为d(u0,v0),称作u0到v0的距离。,Dijkstra算法,关于求最短通路问题，Dijkstra算法是最有名的方法之一，它的基本思想是：把G的顶点分为S，T两类，若u0到某个顶点x的最短通路已求出，则将x归入S，其余点归入y，开始S中只有u0，随着程序的运行，我们就把T的元素逐个转入S直到v0也被转入S，程序就结束了使用这一算法不仅可以找出最短的(u0,v0)-通路，而且可以给出u0到其它任何顶点