《离散数学第9章节图论幻灯片》由会员分享，可在线阅读，更多相关《离散数学第9章节图论幻灯片（169页珍藏版）》请在金锄头文库上搜索。
1、第9章 图 论 9.1 图的基本概念 9.2 路和回路 9.3 连通图 9.4 图的矩阵表示 9.5 欧拉图和汉密尔顿图 9.6 树 9.7 二部图及匹配 9.8 平面图,返回总目录,第9章 图论,图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。随着科学技术的发展，图论在运筹学、网络理论、信息论、控制论和计算机科学等领域都得到广泛的应用。本章首先给出图、简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关
2、联矩阵的定义。最后介绍了欧拉图与哈密尔顿图、树、二部图、平面图和图的着色。,返回章目录,9.1图的基本概念,9.1.1图 两个个体x，y的无序序列称为无序对，记为(x,y)。在无序对(x,y)中，x，y是无序的，它们的顺序可以颠倒，即(x,y)=(y,x)。 定义9.1.1 图G是一个三重组V(G),E(G),G 其中：V(G)是非空结点集。 E(G)是边集。 G是边集到结点的有序对或 无序对集合的函数。,【例9.1】G=V(G),E(G),G 其中：V(G)=a,b,c,d E(G)=e1,e2,e3,e4 G：G(e1)=(a,b) G(e2)=(b,c) G(e3)=(a,c) G(e4
3、)=(a,a) 试画出G的图形。 解：G的图形如图9.1所示。,由于在不引起混乱的情况下，图的边可以用有序对或无序对直接表示。因此，图可以简单的表示为： G=V,E 其中：V是非空的结点集。 E是边的有序对或无序对组成的集合。 按照这种表示法，例9.1中的图可以简记为： G=V,E 其中：V=a,b,c,d E=(a,b), (b,c), (a,c), (a,a),定义9.1.2 若图G有n个结点，则称该图为n阶图。 定义9.1.3 设G为图，如果G的所有边都是有向边，则称G为有向图。如果G的所有边都是无向边，则称G为无向图。如果G中既有有向边，又有无向边，则称G为混合图。 图9.3的(a)是
4、无向图，(b)是有向图，(c)是混合图。,在一个图中，若两个结点由一条边(有向边或无向边)关联，则称其中的一个结点是另一个结点的邻接点。并称这两个结点相互邻接。 在一个图中不与任何结点相邻接的结点，称为孤立点。 在一个图中，如果两条边关联于同一个结点，则称其中的一个边是另一个边的邻接边。并称这两个边相互邻接。关联于同一个结点的一条边叫做环或自回路。在有向图中环的方向可以是顺时针，也可以是逆时针，它们是等效的。 定义9.1.4 由孤立点组成的图叫做零图。由一个孤立点组成的图叫做平凡图。 根据定义9.1.4，平凡图一定是零图。,9.1.2结点的度及其性质 定义9.1.5 设G=V,E是图，vV，与
5、v相关联的边数叫做结点v的度。记为deg(v)。规定，自回路为所在结点增加2度。 在图G=V,E中，度数最大(小)的结点的度叫做图G的最大(小)度，记为(G)(G)。图G的最大度和最小度表示为： (G)=max deg(v) | vV (G)= min deg(v) | vV 在图9.1中， (G)=4，(G)=0。,定理9.1.1 在任何图G=V,E中，所有结点度数的和等于边数的2倍。即： = 2|E| 证明：图的每一条边都和两个结点相关联，为每个相关联的结点增加一度, 给图增加两度。所以所有结点度数的和等于边数的2倍。 推论 在任何图G=V,E中，度数为奇数的结点必为偶数个。,定义9.1.
6、6 设G=V,E是有向图，vV，射入(出)结点v的边数称为结点v的入(出)度。记为deg(v) (deg(v)。 显然，任何结点的入度与出度的和等于该结点的度数，即deg(v)=deg(v)+deg(v)。 定理9.1.2 在有向图中，所有结点入度的和等于所有结点出度的和。 证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。,9.1.3多重图、简单图、完全图和正则图 定义9.1.7 在图G中，连接同一对结点的多条相同边称为平行边。平行边的条数称为该平行边的重数。含平行边的图叫多重图。不含平行边和环的图叫简单图。
7、 例如，在图9.4(a)中结点a和b之间有两条平行边，结点b和c之间有三条平行边，结点b上有两条平行边，这两条平行边都是环。图9.4(a)不是简单图。 又如，在图9.4(b)中结点v1和v2之间有两条平行边。v2和v3之间的两条边，因为方向不同，所以不是平行边。图9.4(b)不是简单图。 简单图不含平行边和环。,定理9.1.3 设G为n阶简单无向图，则(G)n1。 证明：因为G有n个结点，G的任何结点v最多只能与其余的n1结点相邻接；又因为G为简单图，既无平行边，又无环。所以deg(v)n1。由v的任意性，就有 (G) =maxdeg(v) | vVn1。 定义9.1.8 设G为n阶简单无向图
8、，若G中的每个结点都与其余的n1个结点相邻接，则称G为n阶无向完全图。记为Kn。在n阶无向完全图中，给每一条边任意确定一个方向，所得到的图称为n阶有向完全图。也记为Kn。 今后，将n阶无向完全图和n阶有向完全图统称为n阶完全图。,定理9.1.4 n阶完全图Kn的边数为 证明：在Kn中，每个结点都与其余的n1结点相邻接， 即任何一对结点之间都有一条边，故边数应为 定义9.1.9 设G为n阶简单无向图，若G中每个结点都是k 度的，则称G为k次正则图。,9.1.4图的同构 在图论中只关心结点间是否有连线，而不关心结点的位置和连线的形状。因此，对于给定的图而言，如果将图的各结点安排在不同的位置上，并且
9、用不同形状的弧线或直线表示各边，则可以得到各种不同图形。所以，同一图的图形并不惟一。由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。 例如，在图9.6中，(a)和(b)两个图的图形不同，但它们的结构完全相同，是同一个图。 为了描述看起来不同，而其结构完全相同的图，引入了同构的概念。,定义9.1.10 设G1=V1,E1与G2=V2,E2是两个无向图(有向图)，若存在双射函数 f：V1V2，v1V1，v2V1 (v1,v2)E1(v1,v2E1)当且仅当(f(v1),f(v2)E2)(f(v1),f(v2)E2) 并且(v1,v2)(v1,v2)与(f(
10、v1),f(v2)(f(v1),f(v2)的重数相同，则称图G1与图G2同构。记为G1G2。双射函数f称为图G1与图G2的同构函数。,两个图同构必须满足下列条件： 结点数相同。 边数相同。 度数相同的结点数相同。 这三个条件是两个图同构的必要条件，不是充分条件。 一般的，用上述三个必要条件判断两个图是不同构的。 两个图同构，它们的同构函数必须实现同度结点对应 同度结点。,定义9.1.12 设G=V,E与G1=V1,E1是两个图。如果V1V且E1E，则称G1是G的子图，G是G1的母图；如果V1V且E1E，则称G1是G的真子图；如果V1V且E1E则称G1是G的生成子图。,在图9.10中，(b)是(
11、a)的子图、真子图、生成子图。,返回章目录,9.2 路和回路,定义9.2.1 设G=V,E是图，G中的结点与边的交替序列L：v0e1v1e2v2envn叫做v0到vn的路。其中vi-1与vi是ei的端点，i=1,n。v0和vn分别叫做路L的始点和终点。路L中边的条数叫做该路的长度。 例如，在图9.11中， L1：v5e8v4e5v2e6v5e7v3 是从v5到v3的路，v5是始点， v3是终点，长度为4。 L2：v1e1v2e3v3 是从v1到v3的路，v1是始点， v3是终点，长度为2。 在简单图中没有平行边和环，路L：v0e1v1e2v2envn完全由它的结点序列v0v1v2 vn确定。所
12、以，在简单图中的路可以用结点序列表示。,定义9.2.2 设G=V,E是图，L是从 v0到vn的路。若v0=vn，则称L为回路。若L中所有边各异，则称L为简单路。若此时又有v0=vn，则称L为简单回路。若L中所有结点各异，则称L为基本路。若此时又有v0=vn，则称L为基本回路。若L既是简单路，又是基本路，则称L为初级路。若此时又有v0=vn，则称L为初级回路。 在图9.11中，L1是一条简单路。L2是一条简单路、基本路、初级路。,定理9.2.1 在n阶图G中，若从结点vi到vj(vivj)存在一条路，则必存在长度小于等于n-1的路。 证明：设L：vie1v1e2v2ejvj是G中一条从结点vi到
13、vj长度为l的路，路上有l+1个结点。 若ln-1，则定理已证。 否则，ln-1，此时，l+1n，即路L上的结点数l+1大于图G中的结点数n，此路上必有相同结点。设vk和vs相同。于是，此路两次通过同一个结点vk(vs)，所以在L上存在vs到自身的回路Cks。在L上删除Cks上的一切边和除vs以外的一切结点，得路L1：vie1v1ekvsejvj。L1仍为从结点vi到vj的路，且长度至少比L减少1。若路L1的长度小于等于n-1，则定理已证。否则，重复上述过程。由于G有n个结点，经过有限步后，必得到从vi到vj长度小于等于n-1的路。,推论 在n阶图G中，若从结点vi到vj(vivj)存在路，则
14、必存在长度小于等于n-1的初级路。 由定理9.2.1的证明过程知，本推论成立。 类似的可证明下列定理和推论。 定理9.2.2 在n阶图G中，若存在结点vi到自身的回路，则必存在vi到自身长度小于等于n的回路。 推论 在n阶图G中，若存在结点vi到自身的简单回路，则必存在vi到自身长度小于等于n的初级回路。,返回章目录,9.3连通图,9.3.1无向连通图 定义9.3.1 在无向图G中，如果结点u和结点v之间存在一条路，则称结点u和结点v连通。记为uv。规定，G中任意结点v和自身连通，即vv。 在无向图中，如果结点u和结点v连通，即uv，那么，结点v和结点u连通，即vu。所以，无向图结点间的连通是
15、对称的。 设G=V,E是无向图，在图G的结点集V上建立一个二元关系R： R=u,v | uVvVu和v连通 R叫做无向图G的结点集V上的连通关系。 因为R是自反的、对称的、传递的，所以R是V上的等价关系。无向图G的结点集V上的连通关系是等价关系。,设G是图9.14。结点集V上的连通关系为R，以下验证R是V上的等价关系，并找出所有等价类。 R=a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b, c,c,d,d,e,e,e,f,e,g,e,h,f,e, f,f, f,g,f,h,g,e,g,f,g,g,g,h,h,e,h,f, h,g,h,h =a,b,ca,b,cdde,f,g,he,f,g,h,根据定义，R是V上的等价关系。等价类有三个，分别是：a,b,c，d，e,f,g,h。,定义9.3.2 若无向图G中的任何两个结点都是连通的，则称G为连通图。规定，平凡图是连通图。 定义9.3.3 设G=V,E是图 V1V且V1，E1是G中两个端点都在V1中的边组成的集合，图G1=V1,E1叫做G的由V1导出的子图，记为GV1。 E2E且E2，V2是由E2中的边所关联的结点组成的集合，图G2=V2,E2叫做G的由E2导出的子图，记为GE2。 在图9.15中，
