《第十四部分图的基本概念教学提纲》由会员分享，可在线阅读，更多相关《第十四部分图的基本概念教学提纲（79页珍藏版）》请在金锄头文库上搜索。
1、第十四章图的基本概念,第四部分：图论,七桥问题,问题 寻找走遍哥尼斯堡（Knigsberg）城的7座桥，且只许走过每座桥一次，最后又回到原出发点 求解 1736年瑞士大数学家欧拉（LeonhardEuler）发表了关于“哥尼斯堡七桥问题”的论文（图论的第一篇论文）。他指出从一点出发不重复的走遍七桥，最后又回到原来出发点是不可能的。,图论,图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题,棋盘上马的行走路线问题,在中国象棋中，马走“
2、日”字，即每步从 12 矩形的一个顶点跳到相对的顶点。如图，马从M（3，2）一次只能跳到A、B、C、D、E、F、G、H中的任何一个位置。 问题：马能否从棋盘上任意一点出发，不重复、不遗漏地走遍整个棋盘（即每一点都走到并且只到一次）？,环游世界各国的问题,英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个顶点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线。这条路线就称“哈密顿圈”。一百多年来，对哈密顿问题的研究，促进了图论的发展。,四色猜想,问题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色 用数学语言表示，即：“将平面任意地细分为不相重
3、叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字”,图论,图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的作用,第十四章图的基本概念,第一节：图 第二节：通路、回路、图的连通性 第三节：图的矩阵表示和运算,第一节：图,无序积：设A，B为任意的两个集合，称 a,b | aA且bB 为A与B的无序积，记做A g(2)= a4; g(3)= a2; g(4)= a1; 边的一一对应： g; g; g; g,例 5,例:下面给出二个无向图，试求出同构函数,：1,2,3,4,5,6 a1,
4、a2,a3,a4,a5,a6 边的对应为： g(i,j)(g(i),g(j)ai,aj,同构的性质,两图同构的必要条件： （1）顶点数相等； （2）边数相等； （3）度数相同的顶点数相等。 但这不是充分条件。如下图,完全图,定义14.6：在个顶点的有向图G=中，如果每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称G为有向完全图；在个顶点的无向图G=中，每二个顶点之间均有一条边连接，则称G为无向完全图。,特殊图,定义14.7：所有顶点均具有同样度数的简单无向图为正则图，各顶点的度数均为k时称为k正则图。,子图的定义,定义14.8:设=,=是二个图， (a)若，则称是的子图；
5、(b)若，并且，则称是的真子图； (c)若，,则称是的生成子图（支撑子图）。 (d)若子图G中没有孤立顶点，G由E唯一确定，则称G为由边集E导出的子图。 (e)若在子图G中，对中的任意二顶点u,v，当u,vE时有u,vE，则G由唯一确定，此时称G为由顶点集导出的子图。,例 6,例：图如下 的真子图 生成子图：,E=,导出的子图,由V=a,b,d,e导出的子图,例 7,例 画出4阶3边的所有非同构的无向简单图。 解：由握手定理可知，该无向简单图各顶点度数之和为6，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负数，每个整数均大于等于0且小于等于3，并且奇数的个数为偶
6、数。有三种情况 3，1，1，1； 2，2，1，1； 2，2，2，0 将每种度数列所有非同构的图都画出来即可得所要求的全部非同构图。,补图,定义14.9:设无向简单图G= 有n个顶点，无向简单图H= 也有同样的顶点，而E是由n个顶点的完全图的边删去E所得，则图H称为图G的补图。 自补图：H与G同构,例 8,例：试画出5个顶点三条边和5个顶点七条边的简单无向图。 解： 5个顶点三条边的图,5个顶点七条边的图（为5顶点三条边的补图）,图的操作,关于图的四种操作： （1）删去中的一条边e； （2）删去中的一个顶点（即是删去顶点和与有关联的所有边）。 （3）设边e=(u,v)E，用Ge表示从G中删除e后
7、，将e的两个端点u,v用一个新的顶点w代替，使w关联e以外u,v关联的所有边，称为e的收缩。 （4）设u,vV，用G(u,v)表示在u,v之间加一条边(u,v)，称为新加边。,第十四章图的基本概念,第二节：通路、回路、图的连通性,14.2 通路和回路,定义14.11: 在有向图中，从某一顶点出发经过某些点边交替序列到达终点，此序列称为通路。 而经过的各条边之间没有相同的通路称为简单通路。 如果通路中顶点各不相同且边也各不相同，则称为初级通路或路径。 如果通路的起点和终点重合，称此通路为回路。没有相同边的回路称为简单回路，没有相同边也没有相同点（除起始点和终止点外）的回路称为圈。,14.2 通路
8、和回路,讨论： （1）从一个顶点到某一顶点的通路（若有的话）不一定是唯一的； （2）通路的表示方法： (a)边点序列表示法： 设，为一有向图，viV，则通路可以表示成：（v1,e1,v2,e2,v3,vk-1,en,vk） (b)也可仅用边的序列表示 (c)顶点表示法(在简单图中)：（ v1, v2 , vk） (3)无向图中的以上术语的定义完全类似，不再重复。,例 1,例：给出有向图,求起始于,终止于的通路。 P1=(1,2,3)=(,) P2=(1,2,3,4,3) P3=(1,4,3) P4=(1,2,4,1,2,3) P5=(1,2,4,1,4,3) P6=(1,1,2,3), 可见：
9、 （1）从1到3有无限条通路，中间有回路； （2）上例中的P1 ，P2， P3， P5为简单通路。,通路的性质,定义:通路P中边的条数称为通路P的长度（路长）。长度为0的通路定义为一个单独的顶点。 定理14.5:设图，是中的顶点数（即），如果从v1到v2(v1v2)有一条通路，则从v1到v2有一条长度不大于n-1的通路。 推论:设图，是中的顶点数（即），如果从v1到v2(v1v2)有一条通路，则从v1到v2有一条长度不大于n-1的初级通路（路径）。,通路和回路的性质,定理14.6：在阶图中，从vi到vi如果存在一条回路的话，则从vi到vi一定存在一条长度小于或等于的回路。 推论：在阶图中，从v
10、i到vi如果存在一条简单回路的话，则从vi到vi一定存在一条长度小于或等于的初级回路。,通路和回路,例： 1. 无向完全图Kn（n3）中有几种非同构的圈？ 2. 无向完全图K3的顶点依次标定为a，b，c. 在定义意义下K3中有多少 不同的长度为3的圈？,14.3 图的连通性,定义14.12：设无向图=，且vi,vjV，若从vi到vj存在一条通路的话，则称vi，vj是连通的。一般认为vi到自身是连通的。 由定义可见：连通的概念与vi到vj之间的通路多少、通路长度、是什么样的通路没有任何关系。,14.3 图的连通性,连通性一定满足： （）自反性： vi到vi一定是连通的。 （）可传递性： vi到v
11、j连通，vj到vk连通，那么vi到vk连通。 （）对于有向图而言，既不一定对称，也不一定反对称。 若vi到vj存在一条通路的话，则vj到vi未必存在一条通路。 （连通性对无向图满足自反、对称和可传递性）,连通图,定义14.12：对于无向图中的任何顶点来讲，若任何二个顶点是相互连通的，则称此图是连通的，否则称为非连通图或分离图。,连通分支,定义14.13：设无向图G=，V关于顶点之间的连通关系的商集V/=V1,V2, Vk，Vi为等价类，称导出子图GVi(i=1,2,k)为G的连通分支，连通分支数k常记为p(G)。 一个无向图或者是一个连通图，或者是由若干个连通分支组成,距离,定义14.14:
12、在无向图G=中，从顶点vi到vj最短通路（短程线）的长度，叫做从vi到vj的距离，记为d(vi, vj) 。若从vi到vj不存在通路，则d(vi, vj) = 注意：在无向图中，有以下性质： 1) d(vi, vj) 0 2) d(vi, vi) = 0 3) d(vi, vj)=d(vj, vi) 4) d(vi, vj) +d(vj, vk) d(vi, vk),点割集、割点,定义14.15 设无向图 G= 。若存在 使得p(G-V) p(G)，且有任意的均有p(G-V) =p(G)，则称V为G的点割集。若是单个点，则称割点。 定义14.16 设无向图 G= 。若存在 使得p(G-E) p
13、(G)，且有任意的均有p(G-E) =p(G)，则称E为G的边割集。若是单个边，则称割边或者桥。 点连通度k-连通图 注意：若G是k-连通图，则在G中删除任何k-1个顶点后，所得图一定还是连通的 边连通度 r边-连通图,点连通度、边连通度的关系,对于任何无向图G，有,距离,定义14.19：设有向图=，且vi,vjV，若从vi到vj存在一条通路的话，则称vi可达vj。一般认为vi到自身是可达的。若vi可达vj并且vj可达vi，则称vi,vj相互可达。 定义14.20: 在有向图G=中，从顶点vi到vj最短通路（短程线）的长度，叫做从vi到vj的距离，记为d(vi, vj) 。若从vi到vj不存在
14、通路，则d(vi, vj) =。,连通性,定义14.22：在有向图中，它的基图若是连通的，则称此有向图为弱连通的；若图中任何顶点偶对中至少有一点到另一顶点是可达的，则称此图是单向连通的；如果任两顶点均是互相可达的，则称是强连通的。 讨论定义： （1）强连通的一定是单向连通的和弱连通的； （2）单向连通的一定是弱连通的； （3）弱连通的既可能不是单向连通的，更可能不是强连通的。,连通性,强连通的 单向连通的弱连通的,图的连通性,定理14.8 设有向图D=，Vv1,v2,vn 。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。 证明：充分性显然 必要性（构造性证明） 定理14.9 设D是n
15、阶有向图。D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。,二部图,定义14.23:如果无向图的顶点集V分成两个子集X,Y,(即满足XY=,XY=V),使得G中任意一边的两个端点分属于X和Y,则称G为二部图,X和Y称为互补顶点子集,常记图为G=。 定义:若二部图G=中X的每个顶点与Y的每个顶点都有且只有一条边相关联,称G为完全二部图,记为Km,n,其中|X|=m,|Y|=n。,例4,子集X=a,b,Y=x,y,z,这是一个二部图。,这是完全二部图K2,3。,二部图,此两图均是K3,3因而是同构的 定理14.10:无向图G是二部图的充要条件是G的所有回路的长度均为偶数。,第十四章图的基
16、本概念,第三节：图的矩阵表示和运算,图的矩阵表示,矩阵是研究图的有关性质的最有效的工具之一，可运用图的矩阵运算求出图的通路、回路和其它一些性质。 前面讨论图的图解表示法的优点是直观，但缺点是： （1）在结点较多时，用图表示十分繁杂，甚至没法表示； （2）计算机中难以贮存。 本节讨论用矩阵表示图能较好的克服以上二大缺点。,图的矩阵表示,定义14.23 设无向图G，V=v1,v2,vn，E=e1,e2,em，令mij为顶点vi与边ej的关联次数，则称(mij)nm为G的关联矩阵，记做M(G)。 1） M(G)每列元素之和均为2。 2） M(G)第i行元素之和为vi的度数。 3）各顶点的度数之和等于边数的2倍 4）第j列与第k列相同当且仅当边ej和ek是平行边。 5） 当且仅当vi是孤立点,图的矩阵表示,定义14.24 设有向图D中无环，V=v1,v2,vn，E=e1,e2,em， 令mij 1 vi为ej的始点 0
