离散数学课件6.1.pdf

第6章 图 第6章 图 图论是近年来发展迅速而又应用广泛的一门 新兴学科 它最早起源于一些数学游戏的难题研 究 如1736年欧拉 L Euler 所解决的哥尼斯堡 七桥问题 以及在民间广为流传的一些游戏问题 例如迷宫问题 棋盘上马的行走路线问题等等 这些古老的问题当时吸引了许多学者的注意 从 而在这些问题研究的基础上 又提出了著名的四 色猜想和环游世界各国的问题 第6章 图 图论不断发展 它在解决运筹学 网 络理论 信息论 控制论 博奕论以及计 算机科学等各个领域的问题时 显示出越 来越大的效果 对于这样一门应用广泛的学科 其包 含的内容是丰富的 本篇我们只准备介绍 基本的概念和定理 为今后有关学科及课 程的学习和研究提供方便 第6章 图 6 1 图的基本概念图的基本概念图的基本概念图的基本概念 6 2 图的连通性图的连通性图的连通性图的连通性 6 3 图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示 6 4 几种特殊的图几种特殊的图几种特殊的图几种特殊的图 6 1 图的基本概念 6 1 1 无向图与有向图无向图与有向图无向图与有向图无向图与有向图 6 1 2 顶点的度数与握手定理顶点的度数与握手定理顶点的度数与握手定理顶点的度数与握手定理 6 1 3 简单图简单图简单图简单图 完全图完全图完全图完全图 正则图正则图正则图正则图 圈图圈图圈图圈图 轮图轮图轮图轮图 方体图方体图方体图方体图 6 1 4 子图子图子图子图 补图补图补图补图 6 1 5 图的同构图的同构图的同构图的同构 无序对与多重集合 无序对无序对无序对无序对 2个元素构成的集合个元素构成的集合个元素构成的集合个元素构成的集合 记作记作记作记作 a b 无序积无序积无序积无序积 A E是是是是V E是是是是V V的多重子集的多重子集的多重子集的多重子集 称为称为称为称为边集边集边集边集 其元素称为其元素称为其元素称为其元素称为有有有有 向边向边向边向边 简称简称简称简称边边边边 有时用有时用有时用有时用V D 和和和和E D 分别表示分别表示分别表示分别表示V和和和和E 有限图有限图有限图有限图 V E都是有穷集合的图都是有穷集合的图都是有穷集合的图都是有穷集合的图 n 阶图阶图阶图阶图 n个顶点的图个顶点的图个顶点的图个顶点的图 零图零图零图零图 E 的图的图的图的图 平凡图平凡图平凡图平凡图 1 阶零图阶零图阶零图阶零图 e1 e2 e3 e4 e5 e6 e7 d a b c 顶点和边的关系顶点和边的关系顶点和边的关系顶点和边的关系 设无向图设无向图设无向图设无向图G ek vi vj E 称称称称vi vj为为为为ek的的的的端点端点端点端点 ek与与与与vi vj 关联关联关联关联 若若若若vi vj 则称则称则称则称ek为为为为环环环环 无边关联的顶点称作无边关联的顶点称作无边关联的顶点称作无边关联的顶点称作孤立孤立孤立孤立 点点点点 若若若若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 则称则称则称则称vi vj相邻相邻相邻相邻 边和边的关系边和边的关系边和边的关系边和边的关系 若若若若ek el有一个有一个有一个有一个 公共端点公共端点公共端点公共端点 则称则称则称则称ek el相邻相邻相邻相邻 顶点的度数 设设设设G 为无向图为无向图为无向图为无向图 v V v的度数的度数的度数的度数 度度度度 d v v作为边的端点次数之和作为边的端点次数之和作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点悬挂顶点悬挂顶点 度数为度数为度数为度数为1的顶点的顶点的顶点的顶点 悬挂边悬挂边悬挂边悬挂边 与悬挂顶点关联的边与悬挂顶点关联的边与悬挂顶点关联的边与悬挂顶点关联的边 G的最大度的最大度的最大度的最大度 G max d v v V G的最小度的最小度的最小度的最小度 G min d v v V 例如例如例如例如d v5 3 d v2 4 d v1 4 G 4 G 1 v4是悬挂顶点是悬挂顶点是悬挂顶点是悬挂顶点 e7是悬挂边是悬挂边是悬挂边是悬挂边 e1是环是环是环是环 e1 e2 e3 e4 e5 e6 e7 v5 v1v2 v3 v4 顶点的度数 续 设设设设D 为有向图为有向图为有向图为有向图 v V v的出度的出度的出度的出度d v v作为边的始点次数之和作为边的始点次数之和作为边的始点次数之和作为边的始点次数之和 v的入度的入度的入度的入度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 3 e1 e2 e3 e4 e5 e6 e7 d a b c 握手定理 定理定理定理定理6 1任何图任何图任何图任何图 无向图和有向图无向图和有向图无向图和有向图无向图和有向图 的所有顶点度数之和都的所有顶点度数之和都的所有顶点度数之和都的所有顶点度数之和都 等于边数的等于边数的等于边数的等于边数的2倍倍倍倍 证证证证 图中每条边图中每条边图中每条边图中每条边 包括环包括环包括环包括环 均有两个端点均有两个端点均有两个端点均有两个端点 所以在计算各顶点所以在计算各顶点所以在计算各顶点所以在计算各顶点 度数之和时度数之和时度数之和时度数之和时 每条边均提供每条边均提供每条边均提供每条边均提供2度度度度 m条边共提供条边共提供条边共提供条边共提供2m度度度度 推论推论推论推论 任何图任何图任何图任何图 无向图和有向图无向图和有向图无向图和有向图无向图和有向图 都有偶数个奇度顶点都有偶数个奇度顶点都有偶数个奇度顶点都有偶数个奇度顶点 定理定理定理定理6 2有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数 证证证证每条边恰好提供每条边恰好提供每条边恰好提供每条边恰好提供1个入度和个入度和个入度和个入度和1个出度个出度个出度个出度 图的度数列 设无向图设无向图设无向图设无向图G的顶点集的顶点集的顶点集的顶点集V v1 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 出度列出度列出度列出度列 4 0 2 1 入度列入度列入度列入度列 1 3 1 2 e1 e2 e3 e4 e5 e6 e7 v5 v1v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 d a b c 实例 2 能能能能 例例例例1下述下述下述下述2组数能成为无向图的度数列吗组数能成为无向图的度数列吗组数能成为无向图的度数列吗组数能成为无向图的度数列吗 1 3 3 3 4 2 1 2 2 3 解解解解 1 不可能不可能不可能不可能 有奇数个奇数有奇数个奇数有奇数个奇数有奇数个奇数 实例 例例例例2已知图已知图已知图已知图G有有有有10条边条边条边条边 4个个个个3度顶点度顶点度顶点度顶点 其余顶点的度数均小其余顶点的度数均小其余顶点的度数均小其余顶点的度数均小 于等于于等于于等于于等于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 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 5 a 8 b 1 1 3 至少至少至少至少5个个个个6度顶点度顶点度顶点度顶点 4 和和和和 5 至少至少至少至少6个个个个5度顶点度顶点度顶点度顶点 方法二方法二方法二方法二 假设假设假设假设b9 5 4 由握手定理的推论由握手定理的推论由握手定理的推论由握手定理的推论 a 6 简单图 定义定义定义定义6 4在无向图中在无向图中在无向图中在无向图中 关联同一对顶点的关联同一对顶点的关联同一对顶点的关联同一对顶点的2条或条或条或条或2条以上的条以上的条以上的条以上的 边边边边 称为称为称为称为平行边平行边平行边平行边 平行边的条数称为平行边的条数称为平行边的条数称为平行边的条数称为重数重数重数重数 在有向图中在有向图中在有向图中在有向图中 具有相同始点和终点的具有相同始点和终点的具有相同始点和终点的具有相同始点和终点的2条或条或条或条或2条以上的边称条以上的边称条以上的边称条以上的边称 为为为为有向平行边有向平行边有向平行边有向平行边 简称简称简称简称平行边平行边平行边平行边 平行边的条数称为平行边的条数称为平行边的条数称为平行边的条数称为重数重数重数重数 含平行边的图称为含平行边的图称为含平行边的图称为含平行边的图称为多重图多重图多重图多重图 既无平行边也无环的图称为既无平行边也无环的图称为既无平行边也无环的图称为既无平行边也无环的图称为简单图简单图简单图简单图 实例 e5和和和和e6 是平行边是平行边是平行边是平行边 重数为重数为重数为重数为2 不是简单图不是简单图不是简单图不是简单图 e2和和和和e3 是平行边是平行边是平行边是平行边 重数为重数为重数为重数为2 e6和和和和e7 不是平行边不是平行边不是平行边不是平行边 不是简单图不是简单图不是简单图不是简单图 e1 e2 e3 e4 e5 e6 e7 v5 v1v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 d a b c 完全图与正则图 无向完全图无向完全图无向完全图无向完全图 每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图 n阶无向完全图记作阶无向完全图记作阶无向完全图记作阶无向完全图记作Kn 顶点数顶点数顶点数顶点数n 边数边数边数边数m n n 1 2 n 1 有向完全图有向完全图有向完全图有向完全图 每对顶点之间均有两条方向相反的边的有向每对顶点之间均有两条方向相反的边的有向每对顶点之间均有两条方向相反的边的有向每对顶点之间均有两条方向相反的边的有向 简单图简单图简单图简单图 顶点数顶点数顶点数顶点数n 边数边数边数边数m n n 1 n 1 2 n 1 k 正则图正则图正则图正则图 每个顶点的度数均为每个顶点的度数均为每个顶点的度数均为每个顶点的度数均为k的无向简单图的无向简单图的无向简单图的无向简单图 顶点数顶点数顶点数顶点数n 边数边数边数边数m kn 2 实例 K3K5 3阶有向完全图阶有向完全图阶有向完全图阶有向完全图 2正则图正则图正则图正则图 4正则图正则图正则图正则图 3正则图正则图正则图正则图 彼得松图彼得松图彼得松图彼得松图 K4 圈图与轮图 无向圈图无向圈图无向圈图无向圈图Cn 其中其中其中其中V v1 v2 vn E v1 v2 v2 v3 vn 1 vn vn v1 n 3 有向圈图有向圈图有向圈图有向圈图Cn 其中其中其中其中V v1 v2 vn E n 3 轮图轮图轮图轮图Wn 无向圈图无向圈图无向圈图无向圈图Cn 1内放一个顶点内放一个顶点内放一个顶点内放一个顶点 且与圈图的每个顶且与圈图的每个顶且与圈图的每个顶且与圈图的每个顶 点之间恰有一条边点之间恰有一条边点之间恰有一条边点之间恰有一条边 n 4 方体图 n方体图方体图方体图方体图Qn 是是是是2n阶无向简单图阶无向简单图阶无向简单图阶无向简单图 其中其中其中其中 V v v a1a2 an ai 0 1 i 1 2 n E u v u v V u与与与与v恰好有一位数字不同恰好有一位数字不同恰好有一位数字不同恰好有一位数字不同 01 0001 1011 000 001 010 011 110 100 111 101 子图 定义定义定义定义6 10设设设设G G 是是是是2个图个图个图个图 同为无向图同为无向图同为无向图同为无向图 或或或或 同为有向图同为有向图同为有向图同为有向图 若若若若V V且且且且E E 则称则称则称则称G 为为为为G的的的的子图子图子图子图 G为为为为G 的的的的母图母图母图母图 记作记作记作记作 G G 若若若若G G 且且且且V V 则称则称则称则称G 为为为为G的的的的生成子图生成子图生成子图生成子图 若若若若V V或或或或E E 称称称称G 为为为为G的的的的真子图真子图真子图真子图 设设设设V V且且且且V 以以以以V 为顶点集为顶点集为顶点集为顶点集 以两端点都在以两端点都在以两端点都在以两端点都在V 中的所有中的所有中的所有中的所有 边为边