离散数学课件6.1

《离散数学课件6.1》由会员分享，可在线阅读，更多相关《离散数学课件6.1（29页珍藏版）》请在金锄头文库上搜索。

1、第6章 图第6章 图图论是近年来发展迅速而又应用广泛的一门 新兴学科。它最早起源于一些数学游戏的难题研 究，如1736年欧拉（L.Euler)所解决的哥尼斯堡 七桥问题。以及在民间广为流传的一些游戏问题： 例如迷宫问题、棋盘上马的行走路线问题等等。 这些古老的问题当时吸引了许多学者的注意，从 而在这些问题研究的基础上，又提出了著名的四 色猜想和环游世界各国的问题。第6章 图图论不断发展，它在解决运筹学，网 络理论，信息论，控制论，博奕论以及计 算机科学等各个领域的问题时，显示出越 来越大的效果。 对于这样一门应用广泛的学科，其包 含的内容是丰富的，本篇我们只准备介绍 基本的概念和定理，为今后有

2、关学科及课 程的学习和研究提供方便。第6章 图 6.1 图的基本概念图的基本概念图的基本概念图的基本概念 6.2 图的连通性图的连通性图的连通性图的连通性 6.3 图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示 6.4 几种特殊的图几种特殊的图几种特殊的图几种特殊的图6.1 图的基本概念 6.1.1 无向图与有向图无向图与有向图无向图与有向图无向图与有向图 6.1.2 顶点的度数与握手定理顶点的度数与握手定理顶点的度数与握手定理顶点的度数与握手定理 6.1.3 简单图简单图简单图简单图、完全图完全图完全图完全图、正则图正则图正则图正则图、圈图圈图圈图圈图、 轮图轮图轮图轮图、方体图方体图方体

3、图方体图 6.1.4 子图子图子图子图、补图补图补图补图 6.1.5 图的同构图的同构图的同构图的同构无序对与多重集合无序对无序对无序对无序对: 2个元素构成的集合个元素构成的集合个元素构成的集合个元素构成的集合, 记作记作记作记作(a,b) 无序积无序积无序积无序积: A E是是是是V E是是是是V V的多重子集的多重子集的多重子集的多重子集, 称为称为称为称为边集边集边集边集, 其元素称为其元素称为其元素称为其元素称为有有有有 向边向边向边向边，简称简称简称简称边边边边. 有时用有时用有时用有时用V(D)和和和和E(D)分别表示分别表示分别表示分别表示V和和和和E有限图有限图有限图有限图:

4、 V, E都是有穷集合的图都是有穷集合的图都是有穷集合的图都是有穷集合的图 n 阶图阶图阶图阶图: n个顶点的图个顶点的图个顶点的图个顶点的图 零图零图零图零图: E=的图的图的图的图 平凡图平凡图平凡图平凡图: 1 阶零图阶零图阶零图阶零图e1e2e3e4e5e6 e7dabc顶点和边的关系顶点和边的关系顶点和边的关系顶点和边的关系设无向图设无向图设无向图设无向图G=, ek=(vi, vj) E, 称称称称vi, vj为为为为ek的的的的端点端点端点端点, ek与与与与vi (vj)关联关联关联关联. 若若若若vi = vj, 则称则称则称则称ek为为为为环环环环. 无边关联的顶点称作无边

5、关联的顶点称作无边关联的顶点称作无边关联的顶点称作孤立孤立孤立孤立点点点点. 若若若若vi vj, 则称则称则称则称ek与与与与vi (vj)的的的的关联次数为关联次数为关联次数为关联次数为1; 若若若若vi = vj, 则称则称则称则称ek与与与与vi 的的的的关联次数为关联次数为关联次数为关联次数为2; 若若若若vi不是边不是边不是边不是边e的端点的端点的端点的端点, 则称则称则称则称e与与与与vi 的的的的关联关联关联关联次数为次数为次数为次数为0. 点和点的关系点和点的关系点和点的关系点和点的关系设设设设vi,vj V, ek,el E,若若若若(vi,vj) E, 则称则称则称则称v

6、i,vj相邻相邻相邻相邻; 边和边的关系边和边的关系边和边的关系边和边的关系 若若若若ek,el有一个有一个有一个有一个 公共端点公共端点公共端点公共端点, 则称则称则称则称ek,el相邻相邻相邻相邻.顶点的度数设设设设G=为无向图为无向图为无向图为无向图, v V, v的度数的度数的度数的度数(度度度度) d(v): v作为边的端点次数之和作为边的端点次数之和作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点悬挂顶点悬挂顶点: 度数为度数为度数为度数为1的顶点的顶点的顶点的顶点 悬挂边悬挂边悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边与悬挂顶点关联的边与悬挂顶点关联的边 G的

7、最大度的最大度的最大度的最大度 (G)=maxd(v)| v V G的最小度的最小度的最小度的最小度 (G)=mind(v)| v V例如例如例如例如d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是悬挂顶点是悬挂顶点是悬挂顶点是悬挂顶点, e7是悬挂边是悬挂边是悬挂边是悬挂边, e1是环是环是环是环e1 e2 e3e4e5e6e7v5v1v2v3v4顶点的度数(续)设设设设D=为有向图为有向图为有向图为有向图, v V, v的出度的出度的出度的出度d+(v): v作为边的始点次数之和作为边的始点次数之和作为边的始点次数之和作为边的始点次数之和 v的入度的

8、入度的入度的入度d (v): v作为边的终点次数之和作为边的终点次数之和作为边的终点次数之和作为边的终点次数之和 v的度数的度数的度数的度数(度度度度) d(v): v作为边的端点次数之和作为边的端点次数之和作为边的端点次数之和作为边的端点次数之和 d(v)= d+(v)+ d-(v) +(D), +(D), (D), (D), (D), (D) 悬挂顶点悬挂顶点悬挂顶点悬挂顶点, 悬挂边悬挂边悬挂边悬挂边例如例如例如例如d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +=4, +=0, =3, =1, =5, =3e1e2e3e4e5e

9、6 e7dabc握手定理定理定理定理定理6.1任何图任何图任何图任何图(无向图和有向图无向图和有向图无向图和有向图无向图和有向图)的所有顶点度数之和都的所有顶点度数之和都的所有顶点度数之和都的所有顶点度数之和都等于边数的等于边数的等于边数的等于边数的2倍倍倍倍.证证证证 图中每条边图中每条边图中每条边图中每条边(包括环包括环包括环包括环)均有两个端点均有两个端点均有两个端点均有两个端点, 所以在计算各顶点所以在计算各顶点所以在计算各顶点所以在计算各顶点度数之和时度数之和时度数之和时度数之和时, 每条边均提供每条边均提供每条边均提供每条边均提供2度度度度, m条边共提供条边共提供条边共提供条边共

10、提供2m度度度度.推论推论推论推论 任何图任何图任何图任何图(无向图和有向图无向图和有向图无向图和有向图无向图和有向图)都有偶数个奇度顶点都有偶数个奇度顶点都有偶数个奇度顶点都有偶数个奇度顶点定理定理定理定理6.2有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数证证证证每条边恰好提供每条边恰好提供每条边恰好提供每条边恰好提供1个入度和个入度和个入度和个入度和1个出度个出度个出度个出度图的度数列设无向图设无向图设无向图设无向图G的顶点集的顶点集的顶点集的顶点集V=v1,

11、 v2, , vn G的度数列的度数列的度数列的度数列: d(v1), d(v2), , d(vn) 如右图度数列如右图度数列如右图度数列如右图度数列:4,4,2,1,3设有向图设有向图设有向图设有向图D的顶点集的顶点集的顶点集的顶点集V=v1, v2, , vn D的度数列的度数列的度数列的度数列: d(v1), d(v2), , d(vn) D的出度列的出度列的出度列的出度列: d+(v1), d+(v2), , d+(vn) D的入度列的入度列的入度列的入度列: d (v1), d (v2), , d (vn) 如右图度数列如右图度数列如右图度数列如右图度数列:5,3,3,3 出度列出度

12、列出度列出度列:4,0,2,1 入度列入度列入度列入度列:1,3,1,2e1 e2 e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6 e7dabc实例(2) 能能能能例例例例1下述下述下述下述2组数能成为无向图的度数列吗组数能成为无向图的度数列吗组数能成为无向图的度数列吗组数能成为无向图的度数列吗? (1) 3,3,3,4; (2) 1,2,2,3解解解解(1)不可能不可能不可能不可能. . . . 有奇数个奇数有奇数个奇数有奇数个奇数有奇数个奇数. . . .实例例例例例2已知图已知图已知图已知图G有有有有10条边条边条边条边, 4个个个个3度顶点度顶点度顶点度顶点, 其余顶

13、点的度数均小其余顶点的度数均小其余顶点的度数均小其余顶点的度数均小 于等于于等于于等于于等于2, 问问问问G至少有多少个顶点至少有多少个顶点至少有多少个顶点至少有多少个顶点? 解解解解 设设设设G有有有有n个顶点个顶点个顶点个顶点. 由握手定理由握手定理由握手定理由握手定理, 4 3+2 (n-4) 2 10 解得解得解得解得n 8例例例例3已知已知已知已知5阶有向图的度数列和出度列分别为阶有向图的度数列和出度列分别为阶有向图的度数列和出度列分别为阶有向图的度数列和出度列分别为3,3,2,3,3和和和和 1,2,1,2,1, 求它的入度列求它的入度列求它的入度列求它的入度列解解解解2,1,1,

14、1,2实例例例例例5设设设设9阶无向图的每个顶点的度数为阶无向图的每个顶点的度数为阶无向图的每个顶点的度数为阶无向图的每个顶点的度数为5或或或或6, 证明它至少有证明它至少有证明它至少有证明它至少有 5个个个个6度顶点或者至少有度顶点或者至少有度顶点或者至少有度顶点或者至少有6个个个个5度顶点度顶点度顶点度顶点.证证证证 讨论所有可能的情况讨论所有可能的情况讨论所有可能的情况讨论所有可能的情况. 设有设有设有设有a个个个个5度顶点和度顶点和度顶点和度顶点和b个个个个6度顶点度顶点度顶点度顶点 (1)a=0, b=9; (2)a=2, b=7; (3)a=4, b=5; (4)a=6, b=3;

15、 (5)a=8, b=1 (1)(3) 至少至少至少至少5个个个个6度顶点度顶点度顶点度顶点, (4)和和和和(5) 至少至少至少至少6个个个个5度顶点度顶点度顶点度顶点方法二方法二方法二方法二 假设假设假设假设b9-5=4. 由握手定理的推论由握手定理的推论由握手定理的推论由握手定理的推论, a 6简单图定义定义定义定义6.4在无向图中在无向图中在无向图中在无向图中, 关联同一对顶点的关联同一对顶点的关联同一对顶点的关联同一对顶点的2条或条或条或条或2条以上的条以上的条以上的条以上的边边边边, 称为称为称为称为平行边平行边平行边平行边, 平行边的条数称为平行边的条数称为平行边的条数称为平行边的条数称为重数重数重数重数在有向图中在有向图中在有向图中在有向图中, 具有相同始点和终点的具有相同始点和终点的具有相同始点和终点的具有相同始点和终点的2条或条或条或条或2条以上的边称条以上的边称条以上的边称条以上的边称为为为为有向平行边有向平行边有向平行边有向平行边, 简称简称简称简称平行边平行边平行边平行边, 平行边的条数称为平行边的条数称为平行边的条数称