第6章图的基本概念PPT学习教案

1、会计学1第第6章图的基本概念章图的基本概念2/42 6.1 图论的产生与发展 图论是数学的一个分支，它以图为研究对象。图是由若干给定的点和连接两点的线所构成。其中，用点代表事物，用连接两点的线表示相应两个事物间具有的特定关系。 图论起源于18世纪，文字记载最早出现于瑞士数学家欧拉(L.Euler)1736年的论著中，关于解决哥尼斯堡七桥问题。第1页/共41页3/42 6.1 图论的产生与发展哥尼斯堡七桥问题:ABCD1 234567 一个出发者能否从一块陆地出发走遍七座桥,而且每座桥恰好走一次，最后回到出发点？ 陆地用点来表示,桥用连接两个点的一条线段来表示。A B DC 第2页/共41页4/

2、42 6.1 图论的产生与发展 1936年德国数学家柯尼希(D.Knig)著线复形的组合拓朴学作为第一本图论著作问世，前后相隔200年。在这期间，德国学者基希霍夫(G.R.Kirchhoff)、英国数学家凯莱(A.Cayley)、哈密尔顿(W.R.Harmilton)和法国数学家若尔当(M.E.C.Jordan)等人都做出了开创性的工作。第3页/共41页5/42 6.1 图论的产生与发展 在20世纪100年间，图论不仅在许多领域，如运筹学、计算机科学等得到了广泛的应用，而且学科本身也获得长足发展，形成了拟阵理论、超图理论以及代数图论、拓朴图论等新分支。 本篇只讨论图论的最基本概念和基本理论及其

3、典型应用，为大家在今后学习和工作中能够运用这一有力工具打下良好的基础。第4页/共41页6/42 设V是一个非空集合，V的一切二元子集之集合记为P2(V)，即P2(V)=AAV,A=2 (=x,y|x,yA). 定义6.2.1 设V是一个非空集合，EP2(V)，二元组(V,E)称为一个无向图。 V称为顶点集， V中元素称为无向图的顶点；E称为边集，E的元素称为无向图的边。如果u,vE，则称u与v相邻(邻接).6.2 图的基本定义 以V为顶点集，E为边集的无向图(V,E)常用字母G表示，即G=(V,E). 如果V=p，E=q，则称G为一个(p,q)图，即G是一个具有p个顶点q条边的图.第5页/共4

4、1页7/42常用小写的英文字母u,v,w表示图的顶点(带下标);常用小写的英文字母x,y,z表示图的边(带下标)。1、顶点与边的表示方法 如果x=u,v是图G的一条边，则x为这条边的名，u和v称为边x的端点，这时称顶点u和v与边x互相关联，还说x是联接顶点u和v的边，且记为x=uv或x=vu，若x与y是图G的两条边，并且仅有一个公共端点，即xy=1，则称边x与y相邻(邻接).2、顶点与边的关联、边与边相邻(邻接)6.2 图的基本定义第6页/共41页8/42 由定义可知，一个无向图G就是一个非空有限集合V上定义的一个反自反且对称的二元关系E和V构成的关系系统.3、图的关系表示6.2 图的基本定义

5、第7页/共41页9/42 实例 设V=v1, v2, ,v5, E=v1,v2, v2,v3, v2,v5, v1,v5, v4,v5，则 G = (V,E)为一无向图. 将图的每个顶点在平面上用一个点或一个小圆圈表示，并在其旁写上顶点的名(如果顶点已命名)，如果x=u,v是图的一条边，则在代表u和v的两点间连一条线，这样得到的图就叫做一个图的图解. 注意：在画图的图解时，线的交点不是图的顶点.4、图解6.2 图的基本定义第8页/共41页10/42 定义6.2.2 在图中联结一个顶点与其自身的边称为环。允许有环存在的图称为带环图. 在图中如果允许两个顶点之间有两个以上的边存在，这样的边称为平行

6、边 (或多重边)。平行边的条数称为重数. 含平行边的图称为多重图. 带环图 多重图伪图允许有环与平行边存在的图，称为伪图.既不含平行边也不含环的图称为简单图.问题：这里的“图”究竟是如何定义的？第9页/共41页11/421、n阶图n个顶点的图2、有限图顶点数和边数均为有限数的图 (注意：以后所 讲的图都是有限图).3、零图一条边也没有的图(G=(V,E),E= )。 n 阶零图记作Nn，即(n,0)图。 1阶零图N1称为平凡图，即(1,0)图.4、空图规定顶点集为空集的图，记为.第10页/共41页12/425、顶点与边的关联关系 设G = 为图， x=vi,vjE，则称vi，vj为x的端点，

7、x与vi(vj)关联. 若vivj，则称x与vi(vj)的关联次数为1；若vi=vj，则称x与vi(vj)的关联次数为2，并称x为环；如果顶点vm不与边x关联，则称x与vm的关联次数为0.第11页/共41页13/42 如果x=(u,v)是有向图的一条边，则称弧x为起于顶点u终于顶点v的弧，或从u到v的弧，u称为x的起点，v为x的终点。有向图定义6.2.3 设V为一个非空有限集合， AVV (u,u)|uV，二元组D=(V,A)称为一个有向图。V中的元素称为D的顶点，A中元素(u,v)称为D的从u到v的弧或有向边. 如果x=(u,v)与y=(v,u)均为A的弧，则称x与y为一对对称弧. 定义6.

8、2.4 不含对称弧的有向图称为定向图. 第12页/共41页14/42 定义6.2.5 设G=(V,E)是一个图，图H=(V1,E1)称为G的一个子图，如果V1是V的非空子集且E1是E的子集. 子 图 定义6.2.6 设G=(V,E)是一个图，如果FE，则称G的子图H=(V,F)为G的生成子图.v1 v2 v3 v6 v5 v4图1v1 v2 v3 v6 v5图2v1 v2 v3 v6 v5 v4图3如果H是G的子图，则说G包含H. 设H是图G的一个子图. 如果HG，则称H是G的真子图。第13页/共41页15/42极大子图 设G的子图H具有某种性质，若G中不存在与H不同的具有此性质且真包含H的图

9、，则称H是具有此性质的极大子图. v1 包含V1并且与V1有边相连的极大子图 v1 v1 第14页/共41页16/42 定义6.2.7 设S为图G=(V,E)的顶点集V的非空子集，则G的以S为顶点集的极大子图称为由S导出的子图，记为. 形式地，=(S,P2(S)E). S的两个顶点在中相邻，当且仅当这两个顶点在G中相邻。导出子图 v1 v2 v3 v6 v5 v4 v1 v2 v3 v6 v4第15页/共41页17/42 设G=(V,E)，uV，由V u导出的子图记成G-u，从图的图解上看，G-u的图解是从G的图中去掉顶点u及与u关联的边所得到的图解.子图的表示方法 设x是G的一条边，则G的生

10、成子图(V,E x)简记为G-x. 如果u和v是G的两个不相邻的顶点，则图(V,Eu,v) 简记成G+uv，它是在G的图解中，把u与v间联一条线而得到的图.第16页/共41页18/42 v1 v2 v3 v4 v5 v1 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5图G图G-v2图G-v4,v5图G+v2,v4实例第17页/共41页19/42顶点的度数定义6.2.8 (1) 设G=为无向图, vV， 称v作为边的端点的次数之和为v的度数，简称为度，记作degv. (2) G的最大度 G的最小度(3) 奇度顶点与偶度顶点.(4) 度为零的顶点称为孤立顶点.显然，对

11、(p,q)图的每个顶点v，有0degvp-1. v1 带环图degmin)(vGVvdegmax)(vGVv第18页/共41页20/42 定理6.2.1(Euler定理或握手定理) 设G=(V,E)是一个具有p个顶点q条边的图，则G中各顶点度的和等于边的条数q的两倍，即: 证 G中每条边均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，q 条边共提供 2q 度.注意：此定理对伪图也成立。握手定理qvVv2deg第19页/共41页21/42推论6.2.1 任一图中，度为奇数的顶点的数目必为偶数. 证 设G=(V,E)，令度为奇数的顶点的集合为V1，则V2=V V1为度为偶数的顶点之

12、集;VvVuVvquvv212degdegdeg从而21deg2degVuVvuqv偶数也就是V1个奇数相加是偶数，V1的个数必为偶数.由定理6.2.1有握手定理推论第20页/共41页22/42 定义6.2.9 图G称为r度正则图，如果 (G)=(G)=r，即G的每个顶点的度都等于r. 3度正则图也叫做三次图. 一个具有p个顶点的p-1度正则图称为p个顶点的完全图,记为Kp. 在Kp中，每个顶点与其余各顶点均相邻，所以Kp有p(p-1)/2条边.r-正则图推论6.2.2 每个三次图均有偶数个顶点.0度正则图就是零图.第21页/共41页23/42例6.2.1 证明：在至少有两个人的团体里，总存在

13、两个人，使得他们在这个团体里恰有相同个数的朋友.证 设此团体里共有n个人，n2，若用点表示人，两人互为朋友时就在相应点间联一条线，这样便得到了具有n个顶点的图G，每个人的朋友数就是G中相应顶点的度， 要证明G中必有两个顶点有相同的度.例题第22页/共41页24/42例题例6.2.2 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, , vx， 则 d(vi) 2，i =1, 2, , x，于是得不等式 32 24+2x得 x 4, 阶数 n 4+4+3=11. 第23页/共4

14、1页25/42例题例6.2.3 9阶无向图G中，每个顶点的度数不是5就是6. 证明G中至少有5个6度顶点或至少有6个5度顶点. 证 关键是利用握手定理的推论. 方法一：穷举法设G中有x个5度顶点，则必有(9x)个6度顶点，由握手定理推论可知，(x,9x)只有5种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求. 方法二：反证法否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是 9 阶图矛盾. 第24页/共41页26/42 定义6.2.10 设G=(V,E)，H=(U,F)是两个无向图. 如果存在一个一一对应 :VU，使得uv

15、E当且仅当(u)(v)F，则称G与H同构，记为G H. u1 u2 u3 u6 u5 u4 v1 v5 v2 v6 v4 v3图的同构第25页/共41页27/42 定义6.2.10 设G1=, G2=为两个图，若存在双射函数f:V1V2, 对于vi,vjV1, vi,vjE1 当且仅当f(vi),f(vj)E2并且vi,vj 与 f(vi),f(vj) 的重数相同，则称G1与G2是同构的，记作G1G2. 图的同构图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，但它们全不是充分条件： 边数相同，顶点数相同; 度数序列相同; 对应顶点的关联集的元素个数相同，等等. 若破坏必要

16、条件，则两图不同构.判断两个图同构是个难题.第26页/共41页28/42 设G=(V,E)，H=(U,F)是两个图， V=v1,v2,.,vp，U=u1,u2,.,up，p3. 如果对每个i，G-viH-ui，则GH. 乌拉姆(S.M.Ulam)猜想 第27页/共41页29/42图的同构实例图中(3)与(4)的度数列相同，它们同构吗？为什么？图中，(1)与(2)不同构(度数列不同). (3) (4) 第28页/共41页30/42实例例6.2.4 画出K4的所有非同构的生成子图.第29页/共41页31/426.3 路、圈、连通图 定义6.3.1 设G=(V,E)是一个图，G的一条通道是G的顶点和

17、边的一个交错序列 v0,x1,v1,x2,v2,x3,.,vn-1,xn,vn,其中xi=vi-1vi，i=1,2,.,n，n称为通道的长，这样的通道常称为v0-vn通道，并简记为v0v1v2.vn. 当v0=vn时，则称此通道为闭通道. 定义6.3.2 如果图中一条通道上的各边互不相同，则称此通道为图的迹，如果一条闭通道上的各边互不相同，则此闭通道称为闭迹. 定义6.3.3 如果图中一条通道上的各顶点互不相同，则称此通道为路或路径，如果闭通道上各顶点互不相同，则称此闭通道为圈，或回路.第30页/共41页32/42 例6.3.1 分析通道与闭通道，迹与闭迹，路与圈之间的关系. v3 v2 v1

18、 v5 v4 v1v2v5v2v3是一条长为4的v1-v3的通道.v1v2v5v4v2v3是一条长为5的迹.v1v2v5v3是一条长为3的路.v2v4v5v2是圈.v2v4v5v2v3v2是闭通道，但不是闭迹.例题第31页/共41页33/42 定理6.3.1 在n 阶图G中，若从顶点vi 到vj（vivj）存在通道，则从vi 到 vj 存在长度小于或等于n1 的通道. 推论1 在 n 阶图G中，若从顶点vi 到 vj（vivj）存在通道，则从vi 到vj 存在长度小于或等于n1的路. 定理6.3.2 在一个n 阶图G中，若存在 vi 到自身的闭通道，则一定存在vi 到自身长度小于或等于 n 的

19、闭通道. 推论2 在一个n 阶图G中，若存在 vi 到自身的闭迹，则一定存在长度小于或等于n 的回路.第32页/共41页34/42 任给一条路径，若此路径的始点或终点与路径外的某个顶点相邻，就将它扩到路径中来，继续这一过程，直到最后得到的路径的两个端点不与路径外的顶点相邻为止。 最后总能得到一条极大路径.称如此构造一条极大路径的方法为“扩大路径法”。这是一种涉及路径和圈的构造证明中常用的方法. 设G=(V,E)为 n 阶无向图， 为G中一条路径。若的始点和终点都不与路径外的顶点相邻，则称 是一条极大路径.第33页/共41页35/42 (1) (2) (4) (3)第34页/共41页36/42

20、定理6.3.3 设G=(V,E)是至少有一个顶点不是弧立顶点的图，如果uV，degu为偶数，则G中有圈.证 令P是G中的一条最长的路(或极大路径)， P=v1v2.vn, degv12，除v2外，必有某个顶点u和v1相邻，那么u必在P中； 所以u必是v2,.,vn中的某个vi，i3，于是P=v1v2.viv1是G的一个圈.如果u不在P中，P1=uv1v2.vn是一条更长的路;通道与回路的性质第35页/共41页37/42证 设 = v0v1vl 是由初始路径 0 用扩大路径法的得到的极大路径，则 l （为什么？）. 因为v0 不与 外顶点相邻，又 d(v0) ，因而在 上除 v1外，至少还存在 1个顶点与 v0 相邻. 设 vx 是离 v0 最远的顶点，于是 v0v1vxv0 为 G 中长度 +1 的圈. 第36页/共41页38/42 定义6.3.4 设G=(V,E)是图，如果G中任两个不同顶点间至少有一条路联结，则称G是一个连通图.连通图 定义6.3.5 图G的极大连通子图称为G的一个支或连通分支.例6.3.3 考虑下图的连通分支数并理解极大的含义. 连通分支数是10，极大连通子图可理解为含有某一点的极大连通子图.第37页/共41页39/42 定理6.3.4 设G=(V,E)是一个图，在V上定义二元关系R如下:u,vV，u