离散数学CH04图论基本概念.ppt

离散数学 Discrete Mathematics,计算机与信息工程学院,第4章 图 论,内容提要,图的基本概念,4.1,连通图,4.3,4.4,图的矩阵表示,路和回路,4.2,内容提要,欧拉图和哈密顿图,4.5,二部图及匹配,4.7,4.8,平面图,树,4.6,有趣的图论问题,能否从河岸或小岛出发，通过每一座桥，且仅通过一次回到原地？,问题,图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如 迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。,有趣的图论问题,图,有趣的图论问题,一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？,有趣的图论问题,解 这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。 集合f，w，s，h中能平安在一起的子集有：f，w，s，h，f，w，s，f，s，h，f，w，h，f，w，f，s，f，h，w，h，f，w，s，h。用顶点表示渡河过程中的状态，状态是二元组：第一元素是集合f，w，s，h在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得图。容易看出，一条路径就是一种渡河方案。,有趣的图论问题,有趣的图论问题,图可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。 一个图是由一些结点和连接两结点间的连线组成,至于连线的长短、曲直及结点的位置是无关紧要的.,4.1 图的基本概念,4.1 图的基本概念,下面表示的是同一个图,什么是图?可用一句话概括 图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象，不便于理解，所以有必要给出另外的回答。下面便是把图作为代数结构的一个定义。,4.1 图的基本概念,定义1 一个图G定义为一个三元组，记作G=。其中V是个非空有限集合，它的元素称为结点；E也是个有限集合，其元素称为边，而是从E到V中的有序对或无序对的映射。,4.1 图的基本概念,由定义可知，图G中的每条边都与图中的无序或有序结点对相联系的。若边eE与无序结点对（vi，vj）相联系，则(e)=（vi，vj），这时边e称为无向边，有时简称为边；若边eE与有序结点对相联系，则(e)=，此时边e称为有向边或弧，vi称为弧e的始结点，vj称为弧e的终结点。,4.1 图的基本概念,【例4.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)=(a,a) 试画出G的图形。,4.1 图的基本概念,【例4.1】 解：G的图形如图所示。,4.1 图的基本概念,定义2 在图G=中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图G称为无向图；如果有些边是有向边，另一些边是无向边，图G称为混合图。,4.1 图的基本概念,4.1 图的基本概念,有向图,无向图,混合图,定义3 在有向图G=中，对任意结点vV，以v为始结点的弧的条数，称为结点v的出度，记为d+(v)；以v为终结点的弧的条数，称为v的入度，记作d-(v)；结点v的出度与入度之和，称为结点的度数(degree)，记为d(v)，显然d(v)=d+(v)+d-(v)。一个度数为0的结点称为孤立结点（ isolated vertex ）。,4.1 图的基本概念,对于无向图G=，结点vV的度数等于联结它的边数，也记为d(v)。 注意：若v点有环，规定该点度因环而增加2。,4.1 图的基本概念,对于无向图G=， 记(G)或=maxd(v)|vV (G)或=mind(v)|vV 它们分别称为图G的最大度和最小度。,4.1 图的基本概念,例,4.1 图的基本概念,关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。 定理4.1.1 握手定理：图中结点度数的总和等于边数的两倍.,一个图中有10个结点，每个结点的度数为6, 图中有多少条边？,？,结点度数总和：6 10=60 因为 2e = 60，所以 e = 30.,解：,4.1 图的基本概念,推论：在任何图中,度数为奇数的结点必定是偶数个.,下面哪些可以作为一个图的度数列 （或称为可图化的）,？,V=v1, v2, , vn为无向图G的顶点集，称d(v1), d(v2), , d(vn)为G的度数列,4.1 图的基本概念,在任何有向图中,所有结点入度之和等于出度之和.,定理14.1.2,4.1 图的基本概念,证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。,【例】 求解下列各题: （1）图G的度数列为2，2，3，5，6，则边数m为多少? （2）图G有12条边，度数为3的顶点有6个，余者度数均小于3，问G至少由几个顶点？ (3) (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗?,4.1 图的基本概念,【例】证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.,4.1 图的基本概念,证:用反证法. 假设存在这样的多面体, 作无向图G=, 其中V=v | v为多面体的面, E=(u,v) | u,vV u与v有公共的棱 uv. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定理的推论矛盾.,4.1 图的基本概念,定义 4:若结点vi与vj由一条边(或弧)e所联结，则称结点vi和vj是边(或弧)e的端结点；同时也称结点vi与vj是邻接结点（adjacent vertices） ，记作vi adj vj；否则为非邻接结点，记作vi nadj vj；也说边(或弧)e关联vi与vj或说结点vi与vj关联边(或弧)e。 关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点与它自身的一条边，称为环。环的方向是无意义的。,4.1 图的基本概念,定义5 在图G=中，如果任何两结点间不多于一条边(对于有向图中，任何两结点间不多于一条同向弧)，并且任何结点无环，则图G称为简单图；若两结点间多于一条边(对于有向图中，两结点间多于一条同向弧)图G称为多重图，并把联结两结点之间的多条边或弧，称为平行边或弧，平行边或弧的条数称为重数。,4.1 图的基本概念,例如，在图 (a)中结点a和b之间有两条平行边，结点b和c之间有三条平行边，结点b上有两条平行边，这两条平行边都是环。图 (a)不是简单图。 在图 (b)中结点v1和v2之间有两条平行边。v2和v3之间的两条边，因为方向不同，所以不是平行边。图 (b)不是简单图。,4.1 图的基本概念,定义6 设G为n阶（结点的个数）简单无向图，若G中的每个结点都与其余的n1个结点相邻接，则称G为n阶无向完全图（Complete graph） 。记为Kn。在n阶无向完全图中，给每一条边任意确定一个方向，所得到的图称为n阶有向完全图。也记为Kn。今后，将n阶无向完全图和n阶有向完全图统称为n阶完全图。 思考n阶完全图Kn的边数是多少？,4.1 图的基本概念,4.1 图的基本概念,n 阶无向完全图Kn 的边数为,因为 Kn 中任意两点间都有边相连， 而 n 个结点中任取两点的组合数(即总边数)为:,n阶有向完全图的边数为？,4.1 图的基本概念,定义7 在无向图G=中，如果每个结点的度是k，即(v)(vVd(v)=k)，则图G称为k度（次）正则图(regular) 。 对于k度（次）正则图G，(G)=(G)=k。,4.1 图的基本概念,正则图边数（由握手定理得）,定义8 离散图（Discrete graph）: 一个具有n个结点但没有边的图称为离散图(零图)，记为Un。仅由一个孤立点构成的图称为平凡图.,4.1 图的基本概念,定义9 给每条边或弧都赋予权的图G=，称为加权图，记为G=，其中W表示各边之权的集合。 加权图在实际中有许多应用，如在输油管系统图中权表示单位时间流经管中的石油数量；在城市街道中，权表示表示通行车辆密度；在航空交通图中，权表示两城市的距离等等。,4.1 图的基本概念,定义10 给定无向图(或有向图)G1=和G2=。若存在双射f：V1V2，使得对任意v，uV1，有(u,v)E1(f(u),f(v)E2，则称G1同构于G2，记为G1 G2。 显然，两图的同构是相互的，即G1同构于G2，G2同构于G1。,4.1 图的基本概念,G1 G2,由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。,4.1 图的基本概念,充要条件,一般说来，证明两个图是同构的并非是轻而易举的事情。请证明下面的两个图是同构的。,4.1 图的基本概念,根据图的同构定义，图同构的必要条件如下： (1) 结点数目相等； (2) 边数相等； (3) 度数相同的结点数目相等。,4.1 图的基本概念,必要条件,但这仅仅是必要条件而不是充分条件。例如，下面的两个图满足上述三个条件，然而并不同构。因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。 寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。,4.1 图的基本概念,例,4.1 图的基本概念,例,4.1 图的基本概念,v1,v2,v3,v4,v5,v6,v1,v2,v3,v4,v5,v6,例,4.1 图的基本概念,例,4.1 图的基本概念,例,4.1 图的基本概念,例,4.1 图的基本概念,例,4.1 图的基本概念,例(续),4.1 图的基本概念,例(续),4.1 图的基本概念,例(续),4.1 图的基本概念,例(续),4.1 图的基本概念,例(续),4.1 图的基本概念,补图、子图和生成子图 定义4.11 设G=V,E是n阶简单无向图，G中的所有结点和所有能使G成为完全图的添加边组成的图称为图G的相对于完全图的补图，简称为G的补图。记为 。 若G ，则称G为自补图。,4.1 图的基本概念,4.1 图的基本概念,在图中，(b)是(a)的补图，(a)与(b)同构，所以(a)是自补图。,？,解,G 是一个有 15 条边的简单图， 有 13 条边，请问 G 中有多少个结点?,共有 15 + 13 = 28 条边，,是一个完全图，它的结点数与 G 相同，设为 n，则,n(n-1)/2 = 28 n = 8,问题,4.1 图的基本概念,定义4.12 设G=V,E与G1=V1,E1是两个图。如果V1V且E1E，则称G1是G的子图，G是G1的母图；如果V1V且E1E，则称G1是G的真子图；如果V1V且E1E则称G1是G的生成子图。,4.1 图的基本概念,包含 G 的所有结点的子图。,生成子图,生成子图,子图,子图,例,4.1 图的基本概念,生成子图,子图,不是子图,v1,v2,v3,v4,例,4.1 图的基本概念,？,请画出 4 阶 3 条边的所有非同构的无向简单图？,问题,4.1 图的基本概念,【例】 画出K4的所有非同构的生成子图。,4.1 图的基本概念,【例】 设G1,G2,G3,G4均是4阶3条边的无向简单图，则它们之间至少有几个是同构的？,4.1 图的基本概念,图的术语 图 无向图 有向图 邻接边 邻接点 孤立点 零图 结点度数与边数的关系 最大度 最小度 平行边 环 简单图 多重图 完全图 完全图的边数与结点数的关系 子图与补图 图的同构 图同构的充要条件和必要条件,本节小结,4.1 图的基本概念,Thank You !,