离散数学第6章

1 第6章图 2 第6章图 6 1图的基本概念6 2图的连通性6 3图的矩阵表示6 4几种特殊的图 3 6 1图的基本概念 6 1 1无向图与有向图6 1 2顶点的度数与握手定理6 1 3简单图 完全图 正则图 圈图 轮图 方体图6 1 4子图 补图6 1 5图的同构 4 无序对与多重集合 无序对 2个元素构成的集合 记作 a b 无序积 A B x y x A y B 例如A a b c B 1 2 A B B A a 1 b 1 c 1 a 2 b 2 c 2 A A a a a b a c b b b c c c B B 1 1 1 2 2 2 多重集合 元素可以重复出现的集合重复度 元素在多重集合中出现的次数例如S a b b c c c a b c的重复度依次为1 2 3 5 无向图 定义6 1无向图G 其中V 称为顶点集 其元素称为顶点或结点 E是V V的多重子集 称为边集 其元素称为无向边 简称边 有时用V G 和E G 分别表示V和E例如 G 如图所示 其中V v1 v2 v5 E v1 v1 v1 v2 v2 v3 v2 v3 v2 v5 v1 v5 v4 v5 6 有向图 定义6 2有向图D 其中V 称为顶点集 其元素称为顶点或结点 E是V V的多重子集 称为边集 其元素称为有向边 简称边 有时用V D 和E D 分别表示V和E有限图 V E都是有穷集合的图n阶图 n个顶点的图零图 E 的图平凡图 1阶零图 7 顶点和边的关联与相邻 设无向图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相邻 对有向图有类似定义 设ek vi vj 是有向图的一条边 又称vi是ek的始点 vj是ek的终点 vi邻接到vj vj邻接于vi 8 顶点的度数 设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是环 9 顶点的度数 续 设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 10 握手定理 定理6 1任何图 无向图和有向图 的所有顶点度数之和都等于边数的2倍 证图中每条边 包括环 均有两个端点 所以在计算各顶点度数之和时 每条边均提供2度 m条边共提供2m度 推论任何图 无向图和有向图 都有偶数个奇度顶点定理6 2有向图所有顶点的入度之和等于出度之和等于边数证每条边恰好提供1个入度和1个出度 11 图的度数列 设无向图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 12 实例 2 能 例1下述2组数能成为无向图的度数列吗 1 3 3 3 4 2 1 2 2 3 解 1 不可能 有奇数个奇数 13 实例 例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 14 实例 例6 4证明不存在具有奇数个面且每个面都具有奇数条棱的多面体 证用反证法 假设存在这样的多面体 作无向图G 其中V v v为多面体的面 E u v u v V u与v有公共的棱 u v 根据假设 V 为奇数且 v V d v 为奇数 这与握手定理的推论矛盾 15 实例 例6 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 16 简单图 定义6 4在无向图中 关联同一对顶点的2条或2条以上的边 称为平行边 平行边的条数称为重数在有向图中 具有相同始点和终点的2条或2条以上的边称为有向平行边 简称平行边 平行边的条数称为重数含平行边的图称为多重图既无平行边也无环的图称为简单图 17 实例 e5和e6是平行边重数为2不是简单图 e2和e3是平行边 重数为2e6和e7不是平行边不是简单图 18 完全图与正则图 无向完全图 每对顶点之间都有一条边的无向简单图 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 19 实例 K3 K5 3阶有向完全图 2正则图 4正则图 3正则图彼得松图 20 圈图与轮图 无向圈图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 21 方体图 n方体图Qn 是2n阶无向简单图 其中V v v a1a2 an ai 0 1 i 1 2 n E u v u v V u与v恰好有一位数字不同 22 子图 定义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 中的所有边为边集的G的子图称作V 的导出子图 记作G V 设E E且E 以E 为边集 以E 中边关联的所有顶点为顶点集的G的子图称作E 的导出子图 记作G E 23 实例 1 2 3 是 1 的子图 2 3 是真子图 1 是母图 1 3 是 1 的生成子图 2 是 d e f 的导出子图 也是 e5 e6 e7 导出子图 3 是 e1 e3 e5 e7 的导出子图 24 补图 定义6 11设G 为n阶无向简单图 记 V V E 称为G的补图 25 图的同构 定义6 12设G1 G2 为两个无向图 有向图 若存在双射函数f V1 V2 使得对于任意的vi vj V1 vi vj E1 E1 当且仅当 f vi f vj E2 E2 并且 vi vj 与 f vi f vj 的重数相同 则称G1与G2是同构的 记作G1 G2 26 实例 27 实例 例6 6画出4阶3条边的所有非同构的无向简单图解总度数为6 分配给4个顶点 最大度为3 且奇度顶点数为偶数 有下述3个度数列 1 1 1 1 3 2 1 1 2 2 3 0 2 2 2 1 1 1 3 1 1 2 2 0 2 2 2 28 实例 例6 7画出3个以1 1 1 2 2 3为度数列的非同构的无向简单图 29 6 2图的连通性 6 2 1通路与回路初级通路 回路 与简单通路 回路 6 2 2无向图的连通性与连通度连通图 连通分支短程线与距离点割集 割点 边割集 割边 桥 点连通度与边连通度 30 6 2图的连通性 续 6 2 3有向图的连通性及其分类可达性弱连通 单向连通 强连通短程线与距离 31 通路与回路 定义6 13给定图G 无向或有向的 G中顶点与边的交替序列 v0e1v1e2 elvl 若 i 1 i l ei vi 1 vi 对于有向图 ei 则称 为v0到vl的通路 v0和vl分别为通路的起点和终点 l为通路的长度 又若v0 vl 则称 为回路 若通路 回路 中所有边各异 则称为简单通路 简单回路 否则称为复杂通路 复杂回路 若通路 回路 中所有顶点 对于回路 除v0 vl 各异 则称为初级通路或路径 初级回路或圈 长度为奇数的圈称作奇圈 长度为偶数的圈称作偶圈 32 说明 1 表示方法 按定义用顶点和边的交替序列 v0e1v1e2 elvl 用边序列 e1e2 el 简单图中 用顶点序列 v0v1 vl 2 在无向图中 长度为1的圈由环构成 长度为2的圈由两条平行边构成 在无向简单图中 所有圈的长度 3 在有向图中 长度为1的圈由环构成 在有向简单图中 所有圈的长度 2 33 说明 续 3 初级通路 回路 是简单通路 回路 但反之不真 初级通路 非初级的简单通路 初级回路 非初级的简单回路 34 通路与回路 续 定理6 3在n阶图中 若从顶点u到v u v 存在通路 则从u到v存在长度小于等于n 1的初级通路 证若通路中没有相同的顶点 即初级通路 长度必 n 1 若有相同的顶点 删去这两个顶点之间的这一段 仍是u到v的通路 重复进行 直到没有相同的顶点为止 定理6 4在n阶图中 若存在v到自身的简单回路 则一定存在v到自身长度小于等于n的初级回路 35 无向图的连通性与连通分支 设无向图G u v Vu与v连通 若u与v之间有通路 规定u与自身总是连通的 连通图 任意两点都连通的图 平凡图是连通图连通关系R u v V且u与v连通 R是等价关系连通分支 V关于R的等价类的导出子图设V R V1 V2 Vk G的连通分支为G V1 G V2 G Vk 连通分支数p G kG是连通图 p G 1 36 短程线与距离 u与v之间的短程线 u与v之间长度最短的通路 设u与v连通 u与v之间的距离d u v u与v之间短程线的长度若u与v不连通 规定d u v 性质 1 d u v 0 且d u v 0 u v 2 d u v d v u 3 d u v d v w d u w 例如a与e之间的短程线 ace afe d a e 2 d a h 37 点割集与边割集 设无向图G v V e E V V E E 记G v 从G中删除v及关联的边G V 从G中删除V 中所有的顶点及关联的边G e 从G中删除eG E 从G中删除E 中所有边定义6 15设无向图G V V 若p G V p G 且 V V p G V p G 则称V 为G的点割集 若 v 为点割集 则称v为割点 设E E 若p G E p G 且 E E p G E p G 则称E 为G的边割集 若 e 为边割集 则称e为割边或桥 38 实例 说明 Kn无点割集n阶零图既无点割集 也无边割集 若G连通 E 为边割集 则p G E 2若G连通 V 为点割集 则p G V 2 e f 点割集 e f 割点 c d 桥 e8 e9 边割集 e8 e9 e1 e2 e1 e3 e6 e1 e3 e4 e7 39 点连通度与边连通度 定义6 16设无向连通图G G min V V 是G的点割集或使G V 成为平凡图 称为G的点连通度 G min E E 是G的边割集 称为G的边连通度 例如 3 G 3 G 40 点连通度与边连通度 续 说明 1 若G是平凡图 则 G 0 G 0 2 若G是完全图Kn 则 G n 1 G n 1 3 若G中存在割点 则 G 1 若G中存在割边 则 G 1 4 规定非连通图的点连通度和边连通度均为0定理6 5对任何无向图G 有 G G G 41 有向图的连通性及其分类 设有向图D u v V u可达v u到v有通路 规定u到自身总是可达的 u与v相互可达 u可达v且v可达uD弱连通 连通 略去各边的方向所得无向图为连通图D单向连通 u v V u可达v或v可达uD强连通 u v V u与v相互可达 42 实例 强连通 单连通 弱连通 D是强连通的当且仅当D中存在经过所有顶点的回路D是单向连通的当且仅当D中存在经过所有顶点的通路 43 有向图中的短程线与距离 u到v的短程线 u到v长度最短的通路 设u可达v 距离d u到v的短程线的长度若u不可达v 规定d 性质 d 0 且d 0 u vd d d注意 没有对称性 44 6 3图的矩阵表示 6 3 1无向图的关联矩阵6 3 2有向无环图的关联矩阵6 3 3有向图的邻接矩阵有向图中的通路数与回路数6 3 4有向图的可达矩阵 45 无向图的关联矩阵 设无向图G V v1 v2 vn E e1 e2 em 令mij为vi与ej的关联次数 称 mij n m为G的关联矩阵 记为M G mij的可能取值为 0 1 2 例如 46 关联矩阵的性质 6 ej是环 第j列的一个元素为2 其余为0 5 vi是孤立点 第i行全为0 47 无环有向图的关联矩阵 48 实例 49 有向图的邻接矩阵 设有向图D V v1 v2 vn E e1 e2 em 令为顶点vi邻接到顶点vj边的条数 称 n n为D的邻接矩阵 记作A D 简记作A 50 实例 51 有向图中的通路数与回路数 定理6 6设A为n阶有向图D的邻接矩阵 则Al l 1 中元素等于D中vi到vj长度为l的通路 含回路 数 等于vi到自身长度为l的回路数 等于D中长度为l的通路 含回路 总数 等于D中长度为l的回路总数 52 有向图中的通路数与回路数 续 推论设Bl A A2 Al l 1 则Bl中元素等于D中vi到vj长度小于等于l的通路 含回路 数 等于D中vi到vi长度小于等于l的回路数 等于D中长度小于等于l的通路 含回路 数 为D中长度小于等于l的回路数 53 实例 续 说明 在这里 通路和回路数是定义意义下的 v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有15条 其中回路3条 54 有向图的可达矩阵 性质 P D 主对角线上的元素全为1 D强连通当且仅当P D 的元素全为1 设有向图D V v1 v2 vn 令称 pij n n为D的可达矩阵 记作P D 简记为P 55 实例 例6 11 1 v1到v4 v4到v1长为3的通路各有多少条 2 v1到自身长为1 2 3 4的回路各有多少条 3 长为4的通路共有多少条 其中有多少条回路 4 长度小于等于4的回路共有多少条 5 写出D的可达矩阵 并问D是强连通的吗 解 56 实例 续 v1到v4长为3的通路有条 3 v4到v1长为3的通路有条 0 v1到自身长为1 2 3 4的回路各有条 1 长为4的通路共有条 其中有条回路 16 3 长度小于等于4的回路共有条 8 可达矩阵 非强连通 单连通 57 6 4几种特殊的图 6 4 1二部图二部图的充要条件6 4 2欧拉图欧拉回路 通路 及其存在的充要条件6 4 3哈密顿图哈密顿回路 通路 及其存在的必要条件和充分条件6 4 4平面图 58 二部图 定义6 19设无向图G 若能将V分成V1和V2使得V1 V2 V V1 V2 且G中的每条边的两个端点都一个属于V1 另一个属于V2 则称G为二部图 记为 称V1和V2为互补顶点子集 又若G是简单图 且V1中每个顶点均与V2中每个顶点都相邻 则称G为完全二部图 记为Kr s 其中r V1 s V2 59 二部图的判别定理 定理6 7无向图G 是二部图当且仅当G中无奇长度的回路证必要性 设G 是二部图 每条边只能从V1到V2 或从V2到V1 故任何回路必为偶长度 充分性 不妨设G至少有一条边且连通 取任一顶点u 令V1 v v V d v u 为偶数 V2 v v V d v u 为奇数 则V1 V2 V V1 V2 先证V1中任意两点不相邻 假设存在s t V1 e s t E 设 1 2分别是u到s t的短程线 则 1 e 2是一条回路 其长度为奇数 与假设矛盾 同理可证V2中任意两点不相邻 60 实例 非二部图 非二部图 61 实例 例6 12某中学有3个课外活动小组 数学组 计算机组和生物组 有赵 钱 孙 李 周5名学生 问分别在下述3种情况下 能否选出3人各任一个组的组长 1 赵 钱为数学组成员 赵 孙 李为计算机组成员 孙 李 周为生物组成员 2 赵为数学组成员 钱 孙 李为计算机组成员 钱 孙 李 周为生物组成员 3 赵为数学组和计算机组成员 钱 孙 李 周为生物组成员 62 实例 续 解 1 2 有多种方案 3 不可能 63 欧拉图 哥尼斯堡七桥 64 欧拉图 欧拉通路 经过所有顶点且每条边恰好经过一次的通路欧拉回路 经过所有顶点且每条边恰好经过一次的回路欧拉图 有欧拉回路的图说明 上述定义对无向图和有向图都适用规定平凡图为欧拉图欧拉通路是简单通路 欧拉回路是简单回路环不影响图的欧拉性 65 欧拉图判别定理 定理6 8无向图G具有欧拉回路当且仅当G是连通的且无奇度顶点 无向图G具有欧拉通路 但没有欧拉回路当且仅当G是连通的且有2个奇度顶点 其余顶点均为偶度数的 这2个奇度顶点是每条欧拉通路的端点 推论无向图G是欧拉图当且仅当G是连通的且无奇度顶点 66 例6 13 无欧拉通路 欧拉图 欧拉图 有欧拉通路非欧拉图 有欧拉通路非欧拉图 无欧拉通路 67 欧拉图判别定理 续 定理6 9有向图D有欧拉回路当且仅当D是连通的且所有顶点的入度等于出度 有向图D有欧拉通路 但没有欧拉回路当且仅当D是连通的且有一个顶点的入度比出度大1 一个顶点的入度比出度小1 其余的顶点的入度等于出度 推论有向图D是欧拉图当且仅当D是连通的且所有顶点的入度等于出度 68 例6 14 欧拉图 无欧拉通路 无欧拉通路 有欧拉通路无欧拉回路 无欧拉通路 有欧拉通路无欧拉回路 69 周游世界问题 W Hamilton 1859年 70 哈密顿回路与哈密顿通路 哈密顿通路 经过图中所有顶点一次且仅一次的通路 哈密顿回路 经过图中所有顶点一次且仅一次的回路 哈密顿图 具有哈密顿回路的图 说明 哈密顿通路是初级通路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路环与平行边不影响图的哈密顿性 71 哈密顿图的必要条件 定理6 10若无向图G 是哈密顿图 则对于V的任意非空真子集V1均有p G V1 V1 证设C为G中一条哈密顿回路 有p C V1 V1 又因为C G 故p G V1 p C V1 V1 例如当r s时 Kr s不是哈密顿图推论有割点的图不是哈密顿图 72 实例 例6 15证明下述各图不是哈密顿图 a b c c 中存在哈密顿通路 73 实例 例6 16证明右图不是哈密顿图 证假设存在一条哈密顿回路 a f g是2度顶点 边 a c f c 和 g c 必在这条哈密顿回路上 从而点c出现3次 矛盾 此外 该图满足定理6 10的条件 这表明此条件是必要 而不充分的 又 该图有哈密顿通路 74 存在哈密顿回路 通路 的充分条件 定理6 11设G是n n 3 阶无向简单图 若任意两个不相邻的顶点的度数之和大于等于n 1 则G中存在哈密顿通路 若任意两个不相邻的顶点的度数之和大于等于n 则G中存在哈密顿回路 即G为哈密顿图 推论设G是n n 3 阶无向简单图 若 G n 2 则G是哈密顿图当n 3时 Kn是哈密顿图 当r s 2时 Kr s是哈密顿图 定理6 12设D是n n 2 阶有向图 若略去所有边的方向后所得无向图中含子图Kn 则D中有哈密顿通路 75 应用 例6 17有7个人 A会讲英语 B会讲英语和汉语 C会讲英语 意大利语和俄语 D会讲日语和汉语 E会讲德语和意大利语 F会讲法语 日语和俄语 G会讲法语和德语 问能否将他们沿圆桌安排就坐成一圈 使得每个人都能与两旁的人交谈 解 作无向图 每人是一个顶点 2人之间有边 他们有共同的语言 ACEGFDBA是一条哈密顿回路 按此顺序就坐即可 76 6 4 4平面图 平面图与平面嵌入平面图的面及其次数极大平面图极小非平面图欧拉公式库拉图斯基定理平面图的对偶图 77 平面图与非平面图 定义6 22如果能将图G除顶点外边不相交地画在平面上 则称G是平面图 这个画出的无边相交的图称作G的平面嵌入 没有平面嵌入的图称作非平面图 例如下图中 1 4 是平面图 2 是 1 的平面嵌入 4 是 3 的平面嵌入 5 是非平面图 78 平面图的面与次数 设G是一个平面嵌入G的面 由G的边将平面划分成的每一个区域无限面 外部面 面积无限的面 用R0表示有限面 内部面 面积有限的面 用R1 R2 Rk表示面Ri的边界 包围Ri的所有边构成的回路组面Ri的次数 Ri边界的长度 用deg Ri 表示说明 构成一个面的边界的回路组可能是初级回路 简单回路 也可能是复杂回路 甚至还可能是非连通的回路之并 79 实例 例1右图有个面 4 deg R1 deg R2 deg R3 deg R0 1 3 2 8 R1的边界 R2的边界 R3的边界 R0的边界 a bce fg abcdde fg 80 实例 例2右边2个图是同一平面图的平面嵌入 R1在 1 中是外部面 在 2 中是内部面 R2在 1 中是内部面 在 2 中是外部面 说明 1 一个平面图可以有多个不同形式的平面嵌入 它们都同构 2 可以通过变换 测地投影法 把平面图的任何一面作为外部面 81 平面图的面与次数 续 定理6 13平面图各面的次数之和等于边数的2倍证一条边或者是2个面的公共边界 或者在一个面的边界中出现2次 在计算各面的次数之和时 每条边恰好被计算2次 82 极大平面图 定义6 24若G是简单平面图 且在任意两个不相邻的顶点之间加一条新边所得图为非平面图 则称G为极大平面图 例如K1 K2 K3 K4都是极大平面图 1 是K5删去一条边 是极大平面图 2 3 不是 1 83 极大平面图的性质 极大平面图是连通的设G为n n 3 阶简单图 G为极大平面图的充分必要条件是 G每个面的次数均为3 例如 极大平面图 外部面的次数为4非极大平面图 84 极小非平面图 定义6 25若G是非平面图 并且任意删除一条边所得图都是平面图 则称G为极小非平面图 例如K5 K3 3都是极小非平面图下述4个图也都是极小非平面图 85 欧拉公式 定理6 14设G为n阶m条边r个面的连通平面图 则n m r 2证对边数m做归纳证明 m 0 G为平凡图 结论成立 设m k k 0 时结论成立 对m k 1 若G中无圈 则G必有一个度数为1的顶点v 删除v及关联的边 记作G G 连通 有n 1个顶点 k条边和r个面 由归纳假设 n 1 k r 2 即n k 1 r 2 得证m k 1时结论成立 否则 删除一个圈上的一条边 记作G G 连通 有n个顶点 k条边和r 1个面 由归纳假设 n k r 1 2 即n k 1 r 2 得证m k 1时结论也成立 证毕 86