离散数学课件：第5章 图的基本概念1

1、1 图论图论 2图论部分图论部分 n第第5章章 图的基本概念图的基本概念n第第6章章 特殊的图特殊的图n第第7章章 树树 3第第5章章 图的基本概念图的基本概念 5.1 无向图及有向图无向图及有向图5.2 通路通路, 回路和图的连通性回路和图的连通性5.3 图的矩阵表示图的矩阵表示5.4 最短路径最短路径, 关键路径和着色关键路径和着色 45.1 无向图及有向图无向图及有向图无向图与有向图无向图与有向图顶点的度数顶点的度数握手定理握手定理简单图简单图完全图完全图子图子图补图补图 5无向图无向图 多重集多重集: 元素可以重复出现的集合元素可以重复出现的集合无序积无序积: A B=(x,y) |

2、x A y B 定义定义 无向图无向图G=, 其中其中(1) 顶点集顶点集V是非空有穷集合是非空有穷集合, 其其元素称为元素称为顶点顶点(或简称或简称 顶顶)(2) 边集边集E为为V V的的多重子集多重子集，其元素称为其元素称为无向边无向边，简称，简称边边.例如右图 G=中，V=v1, v2, ,v5, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 6有向图有向图定义定义 有向图有向图D=, 其中其中(1)顶点集顶点集V是非空有穷集合是非空有穷集合, 其元素称为其元素称为顶点顶点(2) 边集边集E为为V V的多重

3、子集的多重子集，其，其 元素称为元素称为有向边有向边，简称，简称边边.当用无向边代替当用无向边代替D中有向边中有向边所得的图所得的图称为称为D的的基图基图:如右图D=中， V=a,b,c,dE=,图的数学定义与图形表示图的数学定义与图形表示,在在同构意义下同构意义下一一对应一一对应 7常用术语常用术语一般以一般以 G 表示无向图表示无向图、 D 表示有向图表示有向图, 也常用也常用 G 泛泛指指无向图和有向图无向图和有向图.以以V(G), E(G), V(D), E(D)明确明确G或或D的的顶点集顶点集, 边集边集.n 阶图阶图: n个顶点的图个顶点的图零图零图: E=（没有边的图）（没有边的

4、图）平凡图平凡图: 1 阶零图（只有一个顶点而无边的图）阶零图（只有一个顶点而无边的图）空图空图: V= 8顶点和边的关联与相邻顶点和边的关联与相邻定义定义 若若e=(u,v)为无向图为无向图G=的一条边的一条边, 称顶称顶u,v为为e的的端端点点，e与与u ( v)关联关联. 当当 u v, 则称则称e与与u ( v)的的关联次数关联次数为为1;若若e 仅关联顶仅关联顶u, 称作称作环环, 此时此时e与与u 的的关联次数为关联次数为2; 当当w非非e端点端点, 则则e与与w 的的关联次数为关联次数为0. 无边关联的顶称为无边关联的顶称为孤立点孤立点.定义定义 有无向图有无向图G=, u,v

5、V, e,eE, 若若(u,v) E, 则称则称顶顶u,v相邻相邻; 若若边边e、e 至少有一公共端点至少有一公共端点, 则称则称e,e 相邻相邻.对对有向图有向图，类似定义：若，类似定义：若e= u,v 是有向图的一条边是有向图的一条边, 称称u是是e的的始点始点, v是是e的的终点终点, u邻接邻接到到v, v邻接邻接于于u.9顶点的度数顶点的度数( (无向图无向图) ) 设设G=为无向图为无向图, v V v的度的度(数数) d(v): v作为作为G中边的中边的端点次数之和端点次数之和 悬悬(挂挂)顶点顶点: 度数为度数为1的顶点的顶点 悬悬(挂挂)边边: 与悬挂顶点关联的边与悬挂顶点关

6、联的边 G的最大度的最大度 (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是环 10顶点的度数顶点的度数( (有向图有向图) ) 设设D=为有向图为有向图, v V, v的的出度出度d+(v): v作为边的作为边的始点始点次数之和次数之和 v的的入度入度d (v): v作为边的作为边的终点终点次数之和次数之和 v的的度数度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 即即 d(v)= d+(v)+ d-(

7、v) D的的最大出度最大出度 +(D) =max d+(v)|v V 最小出度最小出度 +(D) =min d+(v)|v V 最大入度最大入度 (D) =max d (v)|v V 最小入度最小入度 (D) =min d (v)|v V 最大度最大度 (D) =max d(v)|v V 最小度最小度 (D) =min d(v)|v V 11例例例例 有向图有向图D 如右：如右： d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +(D)=4, +(D)=0, (D)=3, (D)=1, (D)=5, (D) =3. 12图论基本定理图论基

8、本定理握手定理握手定理 定理定理 无向图或有向图中，所有顶点无向图或有向图中，所有顶点度数总和度数总和为为边数边数的的2倍倍；对于有向图，所有顶点；对于有向图，所有顶点入度之和入度之和等于等于出出度之和度之和恰恰等于边数等于边数.证： G的每条边（包括环）均有两端点，因此在计算各顶点度数之和时，每边均提供2度，m条边共提供2m度； 有向图的每条边提供1入度和1出度, 故所有顶点入度之和等于出度之和等于边数. 推论推论 任意无向图或有向图中，任意无向图或有向图中，奇度顶的数目必为奇度顶的数目必为偶数偶数.13图的图的度数列度数列 设无向图设无向图G的顶点集的顶点集V=v1, v2, , vnG的

9、的度数列度数列: d(v1), d(v2), , d(vn)如右图，度数列: 4,4,2,1,3设有向图设有向图D的顶点集的顶点集V=v1, v2, , vnD的的度数列度数列: d(v1), d(v2), , d(vn)D的的出度列出度列: d+(v1), d+(v2), , d+(vn)D的的入度列入度列: d (v1), d (v2), , d (vn)如右图，度数列: 5,3,3,3 出度列: 4,0,2,1 入度列: 1,3,1,214握手定理的握手定理的应用应用例例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗能成为图的度数列吗?解： 不可能. 它们含有奇数个奇

10、数.例例2 已知图已知图G有有 10 条边条边, 4个个 3度顶点度顶点, 其余顶点的其余顶点的度数均小于等于度数均小于等于2, 问问G至少有多少个顶点至少有多少个顶点? 解： 设G有n个顶点. 由握手定理, 43+2(n-4) d(v) =210解得 n815握手定理的应用握手定理的应用(续续)例例3 证明不存在具有奇数个面且每个面都具有奇数证明不存在具有奇数个面且每个面都具有奇数条棱的多面体条棱的多面体.证 用反证法. 假设存在这样的多面体, 作无向图G=, 其中V=v | v为多面体的面, E=(u,v) | u,vV u与v有公共的棱 uv.根据假设, |V|为奇数且vV, d(v)为

11、奇数. 这与握 手定理的推论矛盾.16多重图与简单图多重图与简单图 定义定义 (1) (1) 在无向图中在无向图中, ,如果有如果有2 2条或条或2 2条以上的边关条以上的边关联同一对顶点联同一对顶点, , 则称这些边为则称这些边为平行边平行边, , 平行边的平行边的条数称为条数称为重数重数. .(2)(2)在有向图中在有向图中, ,如果有如果有2 2条或条或2 2条以上的边具有条以上的边具有相同相同的的始点始点和和终点终点, , 则称这些边为则称这些边为有向平行边有向平行边, , 简称简称平行边平行边, , 平行边的条数称为平行边的条数称为重数重数. .(3) (3) 含平行边含平行边的图称

12、为的图称为多重图多重图. .(4) (4) 既既无平行边无平行边也也无环无环的图称为的图称为简单图简单图( (有时直接有时直接称称 单图单图).).简单图是极重要的概念简单图是极重要的概念 17实例实例e5和e6 是平行边，重数为2.非简单图e2和e3 是平行边,重数为2.非简单图注意e6和e7 不是平行边18图的图的同构同构 定义定义 设设G1=, G2=为两个无向图为两个无向图(有有向图向图), 若若存在双射存在双射函数函数 f: V1V2, 使得使得对于任意的对于任意的vi,vj V1, (vi , vj) E1（ E1）当且仅当当且仅当 (f(vi) , f(vj) E2（ E2），）

13、，并且并且, (vi , vj)（）与）与 (f(vi), f(vj)（）的的重数相同重数相同，则称，则称G1与与G2是是同构同构的，记作的，记作G1 G2. 同构实例同构实例 19彼得森图彼得森图例例1 证明下述证明下述2对图是同构的对图是同构的20同构实例同构实例( (续续) )例例2 试画出试画出4阶阶3条边的所有非同构的无向单图条边的所有非同构的无向单图例例3 判断下述每一对图是否同构判断下述每一对图是否同构: (1)度数列不同度数列不同不同构不同构21同构实例同构实例( (续续) )(2)(3)入入(出出)度列不同度列不同不同构不同构度数列相同度数列相同但但不同构不同构(左边不左边不

14、含三角形含三角形,右边有右边有三角形三角形) (1) (2) 22图的同构图的同构( (续续) )说明：说明：图之间的图之间的同构关系同构关系具有具有自反性、对称性自反性、对称性和和传递性传递性.能找到多条同构的能找到多条同构的必要条件必要条件, 但它们都但它们都非充分非充分条件条件: 边数相同，顶点数相同边数相同，顶点数相同 度数列相同度数列相同(不计度数的顺序不计度数的顺序) 对应顶点的关联集及邻域的元素个数相同，等等对应顶点的关联集及邻域的元素个数相同，等等若若不满足必要条件不满足必要条件，则两图，则两图不同构不同构至今没有找到判断两个图同构的多项式时间算法至今没有找到判断两个图同构的多

15、项式时间算法 n阶无向完全图阶无向完全图Kn: 任意两顶均相邻任意两顶均相邻的的n阶无向阶无向单图单图.性质性质: 边数边数m = n(n-1)/2, = = n-1n阶有向完全图阶有向完全图: 任意顶点间均有两条反向任意顶点间均有两条反向的有向边的有向边的的n阶有向阶有向单图单图. 性质性质: 边数边数m=n(n-1), = = 2(n-1), + = + = - = - = n-123完全图完全图 K53阶有向完阶有向完全图全图24子图子图 定义定义 设设G=, G =是两个图是两个图(1) 若若V V且且E E, 则称则称G 为为G的的子图子图, G为为G 的的 母图母图, 记作记作G G(2) 若若V V 或或E E，称，称G 为为G的的真子图真子图(3) 若若G G 并且并且V =V，则称，则称G 为为G的的生成子图生成子图(4) 若若V V 且且V , 而而E 以所有两端点都在以所有两端点都在 V 中中的边构成的边构成，则，则G 称作称作G关于关于V 的导出子图的导出子图，记作，记作 GV (5) 若若E E且且E , 而而V 以所有关联以所有关联E 中边的顶点中边的顶点构成，则构成，则G 称作称作G关于关于E 的导出子图的导出子图, 记作记作 GE 25生成子图实例生成子图实例 K4的所有非同构的生成子图的所有非同构的生成子图