离散数学之4_图的基本概念

1、图图 论论 部部 分分主要内容主要内容n图的基本概念图的基本概念n路与回路路与回路n图的矩阵表示图的矩阵表示n欧拉图与汉密尔顿图欧拉图与汉密尔顿图n*平面图平面图n*对偶图与着色对偶图与着色n*树与生成树树与生成树n*根树及其应用根树及其应用图的基本概念图的基本概念n图的定义图的定义n图的一些概念和规定图的一些概念和规定n结点的度数与握手定理结点的度数与握手定理n简单图和多重图简单图和多重图n完全图与正则图完全图与正则图n子图与补图子图与补图n图的同构图的同构n学习要点与基本要求学习要点与基本要求n实例分析实例分析图的定义图的定义定义定义7-1.1 一个一个图图是一个三元组是一个三元组，其，其

2、中中V(G)是一个非空的是一个非空的结点集合结点集合， E(G)是是边集合边集合， G是从边集合到结点无序偶（有序偶）集合上的是从边集合到结点无序偶（有序偶）集合上的函数函数。例如：例如：下图所示的图下图所示的图e1e2e3e4e5e6abcdV(G)=a,b,c,dE(G)=e1, e2, e3, e4, e5, e6 ：E(G) VV (e1)=(a,b), (e2)=(a,c) (e3)=(b,d), (e4)=(b,c) (e5)=(c,d), (e6)=(a,d)关于图的说明关于图的说明n一个图由若干个结点和边所组成，与边的长短及结一个图由若干个结点和边所组成，与边的长短及结点的位置

3、无关。点的位置无关。n图可简记为图可简记为G=，其中，其中V是非空结点集，是非空结点集，E是是边集边集 。e1e2e3e4e5e6abcde1e2e3e4e5e6abcd图的一些概念和规定图的一些概念和规定n集合的集合的无序积无序积：设：设A，B为任意的两个集合，称为任意的两个集合，称a,b|aAbB为为A与与B的的无序积无序积，记作，记作A&B。可将无序积中的无序对可将无序积中的无序对a,b记为记为(a,b)，并且允许，并且允许ab无论无论a,b是否相等，均有是否相等，均有(a,b)(b,a)，因而，因而 A&BB&A。n多重集合：多重集合：元素可以重复出现的集合，某

4、元素重复出元素可以重复出现的集合，某元素重复出现的次数称为该元素的现的次数称为该元素的重复度重复度。n无向图：无向图：E(G)是是V(G)&V(G)的多重子集。的多重子集。eE(G)称称为为无向边无向边。n有向图：有向图： E(G)是是V(G) V(G)的多重子集。的多重子集。 eE(G)称为称为有向边有向边。图的一些概念和规定图的一些概念和规定n如果在图中一些边是有向边，一些边是无向边，则如果在图中一些边是有向边，一些边是无向边，则称这个图是称这个图是混合图混合图。n若有向边若有向边ei=，其中，其中vj称为称为ei的的起始结点起始结点， vk称称为为ei的的终止结点终止结点。n在一

5、个图中，若两个结点由一条有向边或无向边关在一个图中，若两个结点由一条有向边或无向边关联，则这两个结点称为联，则这两个结点称为邻接点邻接点。n在一个图中不与任何结点相邻的结点，称为在一个图中不与任何结点相邻的结点，称为孤立结孤立结点。点。n仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图，含有，含有n个结点的个结点的零图记为零图记为Nn。N1称为称为平凡图平凡图。图的一些概念和规定图的一些概念和规定n规定顶点集为空集的图为规定顶点集为空集的图为空图空图，并将空图记为，并将空图记为。 n关联于同一结点的一条边称为关联于同一结点的一条边称为环或自回路环或自回路。n将有向图各将有向图各有向边均

6、改成无向边后的无向图有向边均改成无向边后的无向图称为原称为原来图的来图的基图基图。n易知标定图与非标定图是可以相互转化的，任何无易知标定图与非标定图是可以相互转化的，任何无向图向图G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G为基图的为基图的有向图。有向图。 nG表示无向图，但有时用表示无向图，但有时用G泛指图泛指图(无向的或有向的无向的或有向的)。nD只能表示有向图。只能表示有向图。举例举例例如例如 下面的四个图。下面的四个图。v1v2v3v4结点的度结点的度 定义定义7-1.2 在图在图G=中，与结点中，与结点v（vV）关联的）关联的边数，称作是该结点的度数，记作边数，称作是

7、该结点的度数，记作deg(v)。 G的最大度的最大度 (G)=maxdeg(v)| v V G的最小度的最小度 (G)=mindeg(v)| v V 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点 悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边注意：注意：环对于结点度的贡献是环对于结点度的贡献是2。图的度数举例图的度数举例d(v1)4(注意，环提供注意，环提供2度度)，4，1，v4是悬挂顶点，是悬挂顶点，e7是悬挂边。是悬挂边。握手定理握手定理 定理定理7-1.1 每个图中，结点度数的总和等于边数的两每个图中，结点度数的总和等于边数的两倍。倍。 VvEv|2)(deg证明证明 因为每条边

8、都关联两个结点，而一条边对其关因为每条边都关联两个结点，而一条边对其关联的每个结点的度数贡献为联的每个结点的度数贡献为1，所以在计算，所以在计算G中各顶中各顶点度数之和时，每条边均提供点度数之和时，每条边均提供2度，度， |E|条边共提供条边共提供2|E|度度.握手定理的推论握手定理的推论推论推论 在任何图中，度数为奇数的结点必定是偶数个。在任何图中，度数为奇数的结点必定是偶数个。证明证明 设设G=为任意图，令为任意图，令 V1=v | v Vd(v)为奇数为奇数 V2=v | v Vd(v)为偶数为偶数则则V1V2=V, V1V2=，由握手定理可知，由握手定理可知 21)()()(2VvVv

9、Vvvdvdvdm 2)(Vvvd 1)(Vvvd由于由于V1中顶点度数都为奇数，中顶点度数都为奇数，显然显然是偶数，是偶数， 而而2m也是偶数，也是偶数，所以所以也为偶数，也为偶数，所以所以|V1|必为偶数必为偶数. 问题研究问题研究问题：问题：在一个部门的在一个部门的25个人中间，由于意见不同，是否个人中间，由于意见不同，是否可能每个人恰好与其他可能每个人恰好与其他5个人意见一致？个人意见一致？解答：解答：不可能。考虑一个图，其中顶点代表人，如果两不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇

10、数个度数为奇数的图，这是不可能的。度。存在奇数个度数为奇数的图，这是不可能的。说明：说明：(1)很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代为了建立一个图模型，需要决定顶点和边分别代表什么。表什么。(3)在一个图模型中，边经常代表两个顶点之间的关在一个图模型中，边经常代表两个顶点之间的关系。系。有向图中结点的度有向图中结点的度定义定义7-1.3 在有向图中，射入一个结点的边数称为该在有向图中，射入一个结点的边数称为该结点的入度结点的入度d-(v)，由一个结点射出的边数称为该结，由一个结点射出的边数称为该结点的出度点的出度d+(v)

11、。结点的出度与入度之和是该结点的。结点的出度与入度之和是该结点的度度deg(v)。d+(a)4，d-(a)1(环环e1提供出度提供出度1，提供入度，提供入度1)，d(a)4+15。5，3，+4 (在在a点达到点达到)+0(在在b点达到点达到)-3(在在b点达到点达到)-1(在在a和和c点达到点达到) 有向图的握手定理有向图的握手定理定理定理7-1.3 在任何有向图中，所有结点的入度之和等在任何有向图中，所有结点的入度之和等于所有结点的出度之和。于所有结点的出度之和。证明证明 因为每一条有向边对应一个入度和一个出度，因为每一条有向边对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一

12、条有若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中个结点入度之和等于边数，向边，所以，有向图中个结点入度之和等于边数，各结点的出度之和也等于边数，故任何有向图中，各结点的出度之和也等于边数，故任何有向图中，入度之和等于出度之和。入度之和等于出度之和。握手定理的应用握手定理的应用例例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗能成为图的度数列吗?解解 不可能不可能. 它们都有奇数个奇数它们都有奇数个奇数.例例2 已知图已知图G有有10条边条边, 4个个3度顶点度顶点, 其余顶点的度数均其余顶点的度数均不大于不大于2, 问问G至少有多少个顶点至少有多少个顶点

13、? 解解 设设G有有n个顶点个顶点. 由握手定理由握手定理, 4 3+2 (n-4) 2 10解得解得 n 8多重图与简单图多重图与简单图平行边平行边 连接于同一对结点之间的多条边称为平行连接于同一对结点之间的多条边称为平行边。边。 多重图多重图含有平行边的图称为多重图。含有平行边的图称为多重图。简单图简单图不含有平行边和环的图称为简单图。不含有平行边和环的图称为简单图。注意：注意：在有向图中，平行边的方向必须一致。因为在有向图中，平行边的方向必须一致。因为 与与是不同的结点。是不同的结点。实例实例例例1 设设G为任意为任意n阶无向简单图，则阶无向简单图，则(G)n-1。 证明证明 因为因为G

14、既无平行边也无环，既无平行边也无环，所以所以G中任何顶点中任何顶点v至多与其余的至多与其余的n-1个顶点均相个顶点均相邻，邻，于是于是d(v)n-1， 由于由于v的任意性，所以的任意性，所以(G)n-1。实例实例例例2 判断下列各非负整数列哪些能成为图的度数列？判断下列各非负整数列哪些能成为图的度数列？哪些能成为简单图的度数列？哪些能成为简单图的度数列？(1) (5,5,4,4,2,1) (2) (5,4,3,2,2) (3) (3,3,3,1)解解 (1) 不可图化。不可图化。 (2) 可图化，不可简单图化。可图化，不可简单图化。 若它可简单图化，设所得简单图为若它可简单图化，设所得简单图为

15、G，则，则 (G)max5,4,3,2,25，这与这与(G) 4相矛盾。相矛盾。 例例2(3) (3,3,3,1)可图化，不可简单图化。假设该序列可以简单图化，可图化，不可简单图化。假设该序列可以简单图化，设设G以该序列为度数列。以该序列为度数列。不妨设不妨设Vv1,v2,v3,v4且且 d(v1)d(v2)d(v3)3,d(v4)1，由于由于d(v4)1，因而，因而v4只能与只能与v1，v2，v3之一相邻，之一相邻，于是于是v1，v2，v3不可能都是不可能都是3度顶点，这是矛盾的，度顶点，这是矛盾的，因而因而(3)中序列也不可简单图化。中序列也不可简单图化。 练习题练习题下面的序列能成为简单

16、图的度数序列吗？为什么？下面的序列能成为简单图的度数序列吗？为什么？(d1,d2,dn)，d1d2dn1 且且 为偶数。为偶数。 niid1完全图完全图完全图：完全图：简单图简单图G=中，若每对结点间都有边中，若每对结点间都有边相连，则称该图为完全图。相连，则称该图为完全图。n个结点的无向完全图个结点的无向完全图记作记作Kn，也称为，也称为n阶完全图阶完全图。定理定理7-1.4 n个结点的无向完全图个结点的无向完全图Kn的边数为的边数为n(n-1)/2。证明证明 在在Kn中，任意两点间都有边相连，所以每个结中，任意两点间都有边相连，所以每个结点的度为点的度为n-1，所有结点度数之和为，所有结点

17、度数之和为n(n-1)，根据握，根据握手定理有：手定理有： Kn的边数的边数=n(n-1)/2。思考题：思考题：n阶有向完全图的边数是多少？阶有向完全图的边数是多少？正则图正则图n阶阶k正则图正则图: 所有结点的度都为所有结点的度都为k的的n阶无向简单图。阶无向简单图。性质性质: 边数边数m=nk/2 ， = =k (1)(2)(3)补图补图定义定义7-1.6 给定一个图给定一个图G=，以，以V为顶点集，为顶点集，所有使所有使G成为完全图成为完全图Kn的添加边组成的集合为的添加边组成的集合为边集的图，称为边集的图，称为G的补图，记作的补图，记作 .例例 求下图的补图。求下图的补图。G子图子图定

18、义定义7-1.7 设图设图G=, 如果有图如果有图G =，(1) 若若V V且且E E, 则称则称G 为为G的的子图子图, G为为G 的的母母图图, 记作记作G G。(2) 若若G G 且且V =V，则称，则称G 为为G的的生成子图生成子图。(3) 若若V V 或或E E，称，称G 为为G的的真子图真子图。(4) 设设V V 且且V , 以以V 为顶点集为顶点集, 以两端点都在以两端点都在V 中的所有边为边集的中的所有边为边集的G的子图称作的子图称作V 的导出子图的导出子图，记作记作 GV (5) 设设E E且且E , 以以E 为边集为边集, 以以E 中边关联的所中边关联的所有顶点为顶点集的有

19、顶点为顶点集的G的子图称作的子图称作E 的导出子图的导出子图, 记记作作 GE 。实例实例如下图，如下图，(b),(c)都是都是(a)的子图。的子图。问：问：(b)与与(c)中哪个是中哪个是(a)的生成子图，哪个是的生成子图，哪个是(a)的导的导出子图。若在出子图。若在(b)中删掉结点中删掉结点c，又如何？，又如何？实例实例如下图，如下图，(b),(c)都是都是(a)的生成子图。的生成子图。(a)(b)(c)相对补图相对补图定义定义7-1.8 设设G =是图是图G=的子图，若给的子图，若给定另外一个图定另外一个图G =使得使得E =E- E ，且，且V 中仅包含中仅包含E 的边所关联的结点。则

20、称的边所关联的结点。则称G 是子图是子图G 的相对于图的相对于图G的补图。的补图。(c)是是(b)相对于相对于(a)的补图，但的补图，但(b)不是不是(c)相对于相对于(a)的补图。的补图。图的同构图的同构定义定义7-1.9 设图设图G=及图及图 G =，如果存，如果存在双射函数在双射函数 f: V V ,使得对于使得对于 vi,vj V, (vi,vj) E（ E）当且仅当）当且仅当 (f(vi),f(vj) E （ E ）并且并且 (vi,vj)（）与）与 (f(vi),f(vj)（）的重数相同，则称的重数相同，则称G与与G 是同构的，记作是同构的，记作G G . 例如：例如：同构的实例同

21、构的实例例例 证明下面的两个图同构。证明下面的两个图同构。证明证明 作双射作双射f：a u3，b u4，c u1，d u2f()=， f()=， f()=， f()=自补图自补图例例 若图若图G与他的补图同构，则称与他的补图同构，则称G是自补图。证明下是自补图。证明下面的图面的图G是自补图。是自补图。证明证明 图的补图如右图所示。图的补图如右图所示。v1v2v3v4v5u1u2u3u4u5对对G及其补图标注，作双射：及其补图标注，作双射：v1 u1， v2 u3， v3 u5， v4 u2， v5 u4因此因此G与补图同构，所以与补图同构，所以G是自补图。是自补图。关于同构的说明关于同构的说明

22、nG与与G 同构的充要条件是：同构的充要条件是：两个图的结点和边分别存在一一对应，且保持关联关两个图的结点和边分别存在一一对应，且保持关联关系。系。n图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.n能找到多条同构的能找到多条同构的必要条件必要条件, 但它们都不是充分条件但它们都不是充分条件: (1) 边数相同，顶点数相同边数相同，顶点数相同 (2) 度数相同的结点数目相等，即度数列相同度数相同的结点数目相等，即度数列相同(不计度不计度数的顺序数的顺序) 若破坏必要条件，则两图不同构。若破坏必要条件，则两图不同构。至今没有找到判断两个图同构的多项式时间算法

23、至今没有找到判断两个图同构的多项式时间算法 。实例实例如下图中的两个图同构吗？为什么如下图中的两个图同构吗？为什么解解 结点数和边数相同，度数序列都是结点数和边数相同，度数序列都是4,4,3,3,2。如果同构，对应结点的度相同，则如果同构，对应结点的度相同，则c与与c对应，对应，c的邻接的邻接点度序列为点度序列为4,3,3，c的邻接点度序列为的邻接点度序列为3,3,2，因此不同构。因此不同构。关于图的其它定义关于图的其它定义定义定义 设设G为无向图。为无向图。(1)设设eE，用，用G-e表示从表示从G中去掉边中去掉边e，称为，称为删除删除e。设设E E，用，用G-E 表示从表示从G中删除中删除

24、E 中所有的边，称为中所有的边，称为删除删除E 。(2)设设vV，用，用G-v表示从表示从G中去掉中去掉v及所关联的一切边，称为及所关联的一切边，称为删除顶删除顶点点v。设设V V，用，用G-V 表示从表示从G中删除中删除V 中所有顶点，称为中所有顶点，称为删除删除V 。(3)设边设边e(u,v)E，用，用Ge表示从表示从G中删除中删除e后，将后，将e的两个端点的两个端点u,v用一个新的顶点用一个新的顶点w(或用或用u或或v充当充当w)代替，使代替，使w关联除关联除e外外u,v关联关联的所有边，称为的所有边，称为边边e的收缩的收缩。(4)设设u,vV(u,v可能相邻，也可能不相邻可能相邻，也可

25、能不相邻)，用，用G(u,v)(或或G+(u,v)表示在表示在u,v之间加一条边之间加一条边(u,v)，称为，称为加新边加新边。说明说明在收缩边和加新边过程中可能产生环和平行边。在收缩边和加新边过程中可能产生环和平行边。举例举例GGe5G e1, , e4 Gv5G v4, , v5 G e5学习要点与基本要求学习要点与基本要求n能够理解与图的定义有关的诸多概念，以及它们能够理解与图的定义有关的诸多概念，以及它们之间的相互关系之间的相互关系.n深刻理解握手定理及其推论，并能够熟练地应用深刻理解握手定理及其推论，并能够熟练地应用它们解决实际问题它们解决实际问题.n理解简单图、完全图、正则图、子图

26、、补图、二理解简单图、完全图、正则图、子图、补图、二部图等概念，能利用它们的性质解决实际应用部图等概念，能利用它们的性质解决实际应用.n深刻理解图同构的概念及必要条件。深刻理解图同构的概念及必要条件。 n习题习题7-1 （1）（）（3）（）（5）实例分析实例分析例题例题1 证明下面两个图是同构的。证明下面两个图是同构的。 v1v2v3v4v5v6v7v8v9v10u1u2u3u4u5u6u7u8u9u10v1 u1, v2 u3，v3 u5，v4 u2， v5 u4，v6 u6， v7 u8， v8 u10， v9 u7， v10 u9，容易验证边也对应。得证。容易验证边也对应。得证。 证明证

27、明 先对两个图进行标定。作双射函数先对两个图进行标定。作双射函数f：彼得森彼得森( (Petersen) )图图实例分析实例分析例题例题2 画出画出K4的所有非同构的生成子图的所有非同构的生成子图 。实例分析实例分析例题例题3 判断下述每一对图是否同构判断下述每一对图是否同构:解：因为度数列分别为解：因为度数列分别为4,3,3,2和和5,3,2,2，不相同，不相同， 所以不同构。所以不同构。实例分析实例分析例题例题4 试画出试画出4阶阶3条边的所有非同构的无向简单图条边的所有非同构的无向简单图解解 4阶阶3条边的无向简单图的所有结点度之和为条边的无向简单图的所有结点度之和为6，而，而简单图中每个结点的度数简单图中每个结点的度数总边数，所以满足条件总边数，所以满足条件的图中每个结点的度的图中每个结点的度3。根据奇数度结点有偶数个，。根据奇数度结点有偶数个，可得：可得： (G)=3时，度序列有：时，度序