第6章图的基本概念.ppt

《第6章图的基本概念.ppt》由会员分享，可在线阅读，更多相关《第6章图的基本概念.ppt（42页珍藏版）》请在优知文库上搜索。

1、集合与图论1/42主要内容：主要内容：l 图的基本概念图的基本概念l 树与割集树与割集l 连通度与匹配连通度与匹配l 平面图与图的着色平面图与图的着色l 有向图有向图第二篇第二篇 图论图论集合与图论2/42第六章第六章 图的基本概念图的基本概念主要内容主要内容：l 图论的产生与发展图论的产生与发展l 图图的的基本基本定义定义l 路路、回路回路、连通图、连通图l 补图、偶图补图、偶图l 欧拉图欧拉图l 哈密顿图哈密顿图l 图的矩阵表示图的矩阵表示l 带权图与最短路问题带权图与最短路问题集合与图论3/42 6.1 图论的产生与发展图论的产生与发展 图论是数学的一个分支，它以图为研究对象。图论是数学

2、的一个分支，它以图为研究对象。图是由若干给定的点和连接两点的线所构成。其中，图是由若干给定的点和连接两点的线所构成。其中，用点代表事物，用连接两点的线表示相应两个事物用点代表事物，用连接两点的线表示相应两个事物间具有的特定关系。间具有的特定关系。图论起源于图论起源于18世纪，文字记载最早出现于瑞士世纪，文字记载最早出现于瑞士数学家欧拉数学家欧拉(L.Euler)1736年的论著中，关于解决年的论著中，关于解决哥哥尼斯堡尼斯堡七桥问题。七桥问题。集合与图论4/42 6.1 图论的产生与发展图论的产生与发展哥尼斯堡七桥问题哥尼斯堡七桥问题:ABCD1 234567 一个出发者能否从一个出发者能否从

3、一块陆地出发走遍七座一块陆地出发走遍七座桥桥,而且每座桥恰好走一而且每座桥恰好走一次，最后回到出发点？次，最后回到出发点？陆地用点来表示陆地用点来表示,桥用连接两个点的一桥用连接两个点的一条线段来表示。条线段来表示。A B DC 集合与图论5/42 6.1 图论的产生与发展图论的产生与发展 1936年德国数学家柯尼希年德国数学家柯尼希(D.Knig)著著线复线复形的组合拓朴学形的组合拓朴学作为第一本图论著作问世，前后作为第一本图论著作问世，前后相隔相隔200年。在这期间，德国学者基希霍夫年。在这期间，德国学者基希霍夫(G.R.Kirchhoff)、英国数学家凯莱、英国数学家凯莱(A.Cayle

4、y)、哈、哈密尔顿密尔顿(W.R.Harmilton)和法国数学家若尔当和法国数学家若尔当(M.E.C.Jordan)等人都做出了开创性的工作。等人都做出了开创性的工作。集合与图论6/42 6.1 图论的产生与发展图论的产生与发展 在在20世纪世纪100年间，图论不仅在许多领域，如年间，图论不仅在许多领域，如运筹学、计算机科学等得到了广泛的应用，而且学运筹学、计算机科学等得到了广泛的应用，而且学科本身也获得长足发展，形成了拟阵理论、超图理科本身也获得长足发展，形成了拟阵理论、超图理论以及代数图论、拓朴图论等新分支。论以及代数图论、拓朴图论等新分支。本篇只讨论图论的最基本概念和基本理论及其本篇只

5、讨论图论的最基本概念和基本理论及其典型应用，为大家在今后学习和工作中能够运用这典型应用，为大家在今后学习和工作中能够运用这一有力工具打下良好的基础。一有力工具打下良好的基础。集合与图论7/42 设设V是一个非空集合，是一个非空集合，V的一切二元子集之集合记的一切二元子集之集合记为为P2(V)，即，即P2(V)=AA V,A=2(=x,y|x,y A).定义定义6.2.1 设设V是一个非空集合，是一个非空集合，E P2(V)，二元组，二元组(V,E)称为一个称为一个无向图无向图。V称为称为顶点集顶点集，V中元素称为中元素称为无向图的顶点；无向图的顶点；E称为称为边集边集，E的元素称为的元素称为无

6、向无向图的边。图的边。如果如果u,v E，则称，则称u与与v相邻相邻(邻接邻接).6.2 图的基本定义图的基本定义 以以V为顶点集，为顶点集，E为边集的无向图为边集的无向图(V,E)常用字母常用字母G表示，即表示，即G=(V,E).如果如果V=p，E=q，则称，则称G为一个为一个(p,q)图图，即，即G是是一个具有一个具有p个顶点个顶点q条边的图条边的图.集合与图论8/42常用小写的英文字母常用小写的英文字母u,v,w表示图的顶点表示图的顶点(带下标带下标);常用小写的英文字母常用小写的英文字母x,y,z表示图的边表示图的边(带下标带下标)。1 1、顶点与边的表示方法、顶点与边的表示方法 如果

7、如果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 图的基本定义图的基本定义集合与图论9/42 由定义可知，一个无向图由定义可知，一个无向图G就是一个非空有限就是一个非空有

8、限集合集合V上定义的一个反自反且对称的二元关系上定义的一个反自反且对称的二元关系E和和V构成的关系系统构成的关系系统.3、图的关系表示、图的关系表示6.2 图的基本定义图的基本定义集合与图论10/42 实例实例 设设V=v1,v2,v5,E=v1,v2,v2,v3,v2,v5,v1,v5,v4,v5，则，则 G=(V,E)为一无向图为一无向图.将图的每个顶点在平面上用一个点或一个小圆圈将图的每个顶点在平面上用一个点或一个小圆圈表示，并在其旁写上顶点的名表示，并在其旁写上顶点的名(如果顶点已命名如果顶点已命名)，如，如果果x=u,v是图的一条边，则在代表是图的一条边，则在代表u和和v的两点间连的

9、两点间连一条线，这样得到的图就叫做一个图的一条线，这样得到的图就叫做一个图的图解图解.注意：在画图的图解时，线的交点不是图的顶点注意：在画图的图解时，线的交点不是图的顶点.4、图解、图解6.2 图的基本定义图的基本定义集合与图论11/42 定义定义6.2.2 在图中在图中联结一个顶点与其自身的边称联结一个顶点与其自身的边称为为环环。允许有环存在的图称为。允许有环存在的图称为带环图带环图.在图中在图中如果允许两个顶点之间有两个以上的边如果允许两个顶点之间有两个以上的边存存在，这样的边称为在，这样的边称为平行边平行边(或或多重边多重边)。平行边的条数平行边的条数称为称为重数重数.含平行边的图称为含

10、平行边的图称为多重图多重图.带环图带环图 多重图多重图伪图伪图允许有环与允许有环与平行边平行边存在的图，称为存在的图，称为伪图伪图.既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图.问题：这里的问题：这里的“图图”究竟是如何定义的？究竟是如何定义的？集合与图论12/42相关概念相关概念1、n阶图阶图n个顶点的图个顶点的图2、有限图有限图顶点数和边数均为有限数的图顶点数和边数均为有限数的图 (注意注意：以后所以后所 讲的图都是有限图讲的图都是有限图).3、零图零图一条边也没有的图一条边也没有的图(G=(V,E),E=)。n 阶零图记作阶零图记作Nn，即，即(n,0)图。图。1

11、阶零图阶零图N1称为平凡图，即称为平凡图，即(1,0)图图.4、空图空图规定顶点集为空集的图，记为规定顶点集为空集的图，记为.集合与图论13/42相关概念相关概念5、顶点与边的关联关系、顶点与边的关联关系 设设G=为图，为图，x=vi,vj E，则称，则称vi，vj为为x的端点，的端点，x与与vi(vj)关联关联.若若vivj，则称，则称x与与vi(vj)的关联次数为的关联次数为1；若若vi=vj，则称则称x与与vi(vj)的关联次数为的关联次数为2，并称，并称x为为环环；如果顶点；如果顶点vm不与边不与边x关联，则称关联，则称x与与vm的关联次数为的关联次数为0.集合与图论14/42 如果如

12、果x=(u,v)是有向图的一条边，则称弧是有向图的一条边，则称弧x为起于为起于顶点顶点u终于顶点终于顶点v的弧，或从的弧，或从u到到v的弧，的弧，u称为称为x的的起起点点，v为为x的的终点终点。有向图有向图定义定义6.2.3 设设V为一个非空有限集合，为一个非空有限集合，A V V(u,u)|u V，二元组二元组D=(V,A)称为一个称为一个有向图有向图。V中的元素称为中的元素称为D的的顶点，顶点，A中元素中元素(u,v)称为称为D的从的从u到到v的的弧弧或或有向边有向边.如果如果x=(u,v)与与y=(v,u)均为均为A的弧，则称的弧，则称x与与y为一为一对对对称弧对称弧.定义定义6.2.4

13、 不含对称弧的有向不含对称弧的有向图称为图称为定向图定向图.集合与图论15/42 定义定义6.2.5 设设G=(V,E)是一个图，图是一个图，图H=(V1,E1)称为称为G的的一个一个子图子图，如果，如果V1是是V的非空子集且的非空子集且E1是是E的子集的子集.子子 图图 定义定义6.2.6 设设G=(V,E)是一个图，如果是一个图，如果F E，则称，则称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的一个子

14、图的一个子图.如果如果H G，则称，则称H是是G的的真子图真子图。集合与图论16/42极大子图极大子图 设设G的子图的子图H具有某种性质，若具有某种性质，若G中不存在与中不存在与H不不同同的具有此性质且真包含的具有此性质且真包含H的图，则称的图，则称H是具有此性质的是具有此性质的极大子图极大子图.v1 包含包含V1并并且与且与V1有有边相连的边相连的极大子图极大子图 v1 v1 集合与图论17/42 定义定义6.2.7 设设S为图为图G=(V,E)的顶点集的顶点集V的非空子的非空子集，则集，则G的以的以S为顶点集的极大子图称为由为顶点集的极大子图称为由S导出的子导出的子图图，记为，记为.形式地

15、，形式地，=(S,P2(S)E).S的两个顶点在的两个顶点在中相邻，当且仅当这两个顶中相邻，当且仅当这两个顶点在点在G中相邻。中相邻。导出子图导出子图 v1 v2 v3 v6 v5 v4 v1 v2 v3 v6 v4集合与图论18/42 设设G=(V,E)，u V，由，由V u导出的子图导出的子图记记成成G-u，从图的图解上看，从图的图解上看，G-u的图解是从的图解是从G的图中去掉的图中去掉顶点顶点u及与及与u关联的边所得到的图解关联的边所得到的图解.子图的表示方法子图的表示方法 设设x是是G的一条边，则的一条边，则G的生成子图的生成子图(V,E x)简记为简记为G-x.如果如果u和和v是是G

16、的两个不相邻的顶点，则图的两个不相邻的顶点，则图(V,Eu,v)简记成简记成G+uv，它是在，它是在G的图解中，把的图解中，把u与与v间联一条线而得到的图间联一条线而得到的图.集合与图论19/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实例实例集合与图论20/42顶点的度数顶点的度数定义定义6.2.8(1)设设G=为无向图为无向图,v V，称称v作为边的端点作为边的端点的次数之和为的次数之和为v的的度数度数，简称为度，记作，简称为度，记作degv.(2)G的的最大度最大度 G的的最小度最小度(3)奇度顶点与偶度顶点奇度顶点与偶度顶点.(4)度为零的顶点称为度为零的顶点称为孤立顶点孤立顶点.显然，对显然，对(p,q)图的每个顶点图的每个顶点v，有，有0degvp-1.v1 带环图带环图degmin)(vGVvdegmax)(vGVv集合与图论21/42 定理定理6.2.1(Euler定理或握手定理定理或握手定理)设设G=(V,E)是一个具有是一个具有p个顶点个顶