离散数学CH04-图论-基本概念课件

1、离散数学Discrete Mathematics计算机与信息工程学院第4章 图 论内容提要图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2内容提要欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6有趣的图论问题能否从河岸或小岛出发，通过每一座桥，且仅通过一次回到原地？问题 图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这

2、些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。有趣的图论问题均分问题 有3个没有刻度的桶a.b和c。其容积分别为8升，5升和3升。假定a桶中装满了酒，现可将酒均分成两份，除了3个桶以外，没有任何其他测量工具。试问该怎样均分？ （B，C）表示b.c桶装酒的情况有趣的图论问题（0，0）（0，3）（3，0）（5，1）（0，1）（1，0）（1，3）（3，3）（5，0）（2，3）（2，0）（0，2）（5，2）（4，3）（4，0）（5，3）图 有趣的图论问题 解 这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。 集合f，w，s，h中能平安在一起的子集有：f，w，s，

3、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、型。因为它显得太抽象，不便于理解，所以有必要给出另外的回答。下面便是把图作为代数结构的一个定义。4.1 图的基本概念定义1 一个图G定义为一个三元组，记作G=。其中V是个非空有限集合，它的元素称为结点；E也是个有限集合，其元素称为边，而是从E到V中的有序对或无序对的映射。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 在

5、图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

6、(v)。注意：若v点有环，规定该点度因环而增加2。4.1 图的基本概念例4.1 图的基本概念 关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。定理4.1.1 握手定理：图中结点度数的总和等于边数的两倍. 一个图中有10个结点，每个结点的度数为6, 图中有多少条边？结点度数总和：6 10=60因为 2e = 60，所以 e = 30.解：4.1 图的基本概念 在任何有向图中,所有结点入度之和等于出度之和.定理14.1.24.1 图的基本概念证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。 【例

7、】 求解下列各题: （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与v

8、j由一条边(或弧)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称为

9、多重图，并把联结两结点之间的多条边或弧，称为平行边或弧，平行边或弧的条数称为重数。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阶无向完全图中，给每一条边任意确定一个方向，所得到的图称

10、为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个结点

11、但没有边的图称为离散图(零图)，记为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 图

12、的基本概念G1 G2由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。4.1 图的基本概念充要条件一般说来，证明两个图是同构的并非是轻而易举的事情。请证明下面的两个图是同构的。4.1 图的基本概念根据图的同构定义，图同构的必要条件如下： (1) 结点数目相等； (2) 边数相等； (3) 度数相同的结点数目相等。4.1 图的基本概念必要条件但这仅仅是必要条件而不是充分条件。例如，下面的两个图满足上述三个条件，然而并不同构。因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为

13、1的结点邻接。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。4.1 图的基本概念例4.1 图的基本概念例4.1 图的基本概念v1v2v3v4v5v6v1v2v3v4v5v6例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的相对于完全图的补图，简称

14、为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 = 28n = 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 图的基本概念生成子图子图不是子图v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4例4.1 图的基本概念？请画出 4 阶 3 条边的所有非同构的无