离散数学- 图论 习题课幻灯片.ppt

第7章图论习题课 离散数学 河南工业大学 信息科学与工程学院 1 复习时注意准确掌握每个概念灵活应用所学定理注意解题思路清晰证明问题时 先用反向思维 从结论入手 分析问题 再按正向思维写出证明过程 2 图 通路与回路 图的连通性 欧拉图 汉密尔顿图 无向树及其性质 平面图的基本性质 欧拉公式 平面图的对偶图 地图着色与平面图着色 平面图的判断 图的矩阵表示 无向树及其性质 根树及其应用 无向树及其性质 图论的结构图 3 4 一 无向图与有向图 1 基本概念 有向图与无向图的定义 有向边 无向边 平行边 环 孤立结点关联与邻接 相邻 结点的度数 结点的度 结点的出度 结点的入度 图的最大度 G 最小度 G 零图与平凡图 简单图与多重图 完全图 子图 生成子图 补图 图的同构 2 运用 1 灵活运用握手定理及其推论 2 判断两个图是否同构 3 画出满足某些条件的子图 补图等 5 二 通路 回路 图的连通性 1 基本概念路 回路 迹 通路 圈无向图和有向图中结点之间的可达关系 连通图 连通分支 连通分支数W G 点割集 割点 点连通度k G 边割集 割边 桥 边连通度 G 短程线 距离有向图连通的分类 强连通 单侧连通 弱连通 强分图 单侧分图 弱分图2 运用 1 判断有向图或无向图中通路 回路 的类型 2 求短程线和距离 3 判断有向图连通的类型 6 三 图的矩阵表示 1 基本概念 无向图的邻接矩阵A根据邻接矩阵判断 各结点的度 有向图结点出 入度 由Ak可以求一个结点到另一个结点长度为k的路条数 有向图的可达矩阵P用P可以判定 各结点的度 有向图的强分图 关联矩阵M 是结点与边的关联关系矩阵 用M判定 各结点的度 7 重要定理 握手定理及其推论 推论 任何图 无向的或有向的 中 奇度结点的个数是偶数 无向图 有向图 且 8 1 2 3 多重图 不是 典型题 设图G 其中V a b c d e E分别由下面给出 判断哪些是简单图 哪些是多重图 简单图 9 下列各序列中 可以构成无向简单图的度数序列的有哪些 1 2 2 2 2 2 可以 2 1 1 2 2 3 不可以 3 1 1 2 2 2 可以 4 0 1 3 3 3 不可以 5 1 3 4 4 5 不可以 10 图G如右图所示 以下说法正确的是 A a d 是割边B a d 是边割集C d e 是边割集D a d a c 是边割集 正确答案是 C 对割边 边割集的概念理解到位 定义设无向图G 为连通图 若有边集E1 E 使图G删除了E1的所有边后 所得的子图是不连通图 而删除了E1的任何真子集后 所得的子图是连通图 则称E1是G的一个边割集 若某个边构成一个边割集 则称该边为割边 或桥 如果答案A正确 即删除边 a d 后 得到的图是不连通图 但事实上它还是连通的 因此答案A是错误的 11 设给定图G 如由图所示 则图G的点割集是 应该填写 f c e 定义设无向图G 为连通图 若有点集V1 V 使图G删除了V1的所有结点后 所得的子图是不连通图 而删除了V1的任何真子集后 所得的子图是连通图 则称V1是G的一个点割集 若某个结点构成一个点割集 则称该结点为割点 f c 是不满定义的 因为 f 是 f c 的真子集 而删除 f 后 图是不连通的 12 单向连通 强连通 强连通 下图所示的六个图中 强连通 单向连通 弱连通的分别有哪些 强连通 单向连通 弱连通 13 设图G的邻接矩阵为则G的边数为 A 5B 6C 3D 4 正确答案是 D 当给定的简单图是无向图时 邻接矩阵为对称的 即当结点vi与vj相邻时 结点vj与vi也相邻 所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1 题中给出的邻接矩阵中共有8个1 故有8 2 4条边 度数之和等于2倍的边数 14 1 D是哪类连通图 2 D中v1到v4长度为1 2 3 4的通路各多少条 3 D中长度为4的通路 不含回路 有多少条 4 D中长度为4的回路有多少条 5 D中长度 4的通路有多少条 其中有几条是回路 6 写出D的可达矩阵 有向图D如图所示 回答下列问题 15 有向图D如图所示 回答下列诸问 1 D是哪类连通图 D是强连通图 解答为解 2 6 只需先求D的邻接矩阵的前4次幂 16 2 D中v1到v1长度为1 2 3 4的回路各多少条 答 v1到v1长度为1 2 3 4的回路数分别为1 1 3 5 3 D中长度为4的通路 不含回路 有多少条 答 长度为4的通路 不含回路 为33条 4 D中长度为4的回路有多少条 答 长度为4的回路为11条 5 D中长度 4的通路有多少条 其中有几条是回路 答 长度 4的通路88条 其中22条为回路 6 写出D的可达矩阵 4 4的全1矩阵 17 简单无向图G必有2结点同度数 证 令G v1 vn 若G中没有孤立点 则G中n个结点的度只取n 1个可能值 1 2 n 1 从而G中至少有两个结点的度数相同 否则 G中有孤立点 不妨设vk vn为全部孤立点 则v1 vk 1的度只取k 2个可能值 1 2 k 2 从而此k 1个结点中至少有两个同度数点 18 握手定理及其推论的应用 设无向图G有10条边 3度与4度结点各2个 其余结点的度数均小于3 问G中至少有几个结点 在最少结点的情况下 写出G的度数列 G G 设G的阶数为n 4个结点的度数分别为3 3 4 4 其余n 4个结点的度数均小于或等于2 由握手定理可得2 3 4 n 4 2 14 2n 8 deg vi 2m 20解此不等式可得n 7 即G中至少有7个结点 7个结点时 其度数列为2 2 2 3 3 4 4 4 2 19 1 设n阶图G中有m条边 证明 G 2m n G 2 n阶非连通的简单图的边数最多可为多少 最少呢 1 证明中关键步骤是握手定理 2m deg vi G deg vi G 于是得n G 2m n G G 2m n G 易知2m n为G的平均度数 因而它大于或等于最小度 G 小于或等于最大度 G 2 n阶非连通的简单图的边数最多可为n 1阶连通图加上一个孤立点 所以边数为 n 1 n 2 2 最少为0 20 一个图如果同构于它的补图 则该图称为自补图 1 一个图是自补图 其对应的完全图的边数必为偶数 2 证明 若n阶无向简单图是自补图 则n 4k或n 4k 1 k为正整数 解 1 设图G是自补图 G有e条边 G对应的完全图的边数为A G的补图G 的边数应为A一e 因为G G 故边数相等 e A一e A 2e 因此G对应的完全图的边数A为偶数 2 由1 可知 自补图对应的完全图的边数为偶数 n个结点的完全图Kn的边数为n n 1 2 所以n n 1 2 2m 即n n 1 4m 因而n为4的倍数 即n 4k 或n 1为4的倍数 即n 4k 1 即n 0 1 mod4 21 对于任何一个具有6个结点的简单图 要么它包含一个三角形 要么它的补图包含一个三角形 解 设6个结点的简单图为G 考察G中的任意一个结点a 那么 另外6个结点中的任何一个结点 要么在G中与a邻接 要么在G的补图G 中与a邻接 这样 就可把5个结点分成两类 将那些在G中与a邻接的结点归成一类 而将那些在G 中与a邻接的结点归在另一类 于是必有一类至少含有三个结点 不妨假设其中的三个结点为b c d 如图所示 若边 b c c d b d 中有一条在G 中 那么这条边所关联的两个结点都与a邻接形成一个三角形 若边 b c c d b d 都不在G 中 则 b c c d b d 形成一个三角形 22 a b c d b c d b c d b c d 推论 任何6人的人群中 或者有3人互相认识 或者有3人彼此陌生 当二人x y互相认识 边 x y 着红色 否则着兰色 则6人认识情况对应于K6边有红K3或者有兰K3 a a a 23 证明简单图的最大度小于结点数 证明 设简单图G有n个结点 对任一结点u 由于G没有环和平行边 u至多与其余n 1个结点中每一个有一条边相连接 即deg u n 1 因此 G maxdeg u n 1 24 设G是一个n阶无向简单图 n是大于等于3的奇数 证明图G与它的补图中度数为奇数的结点个数相等 证明 因为G是n阶无向简单图 且n是大于等于3的奇数 故无向图的结点数为奇数 则所对应的n阶完全图中每个结点的度数为n 1即为偶数 利用奇数 奇数 偶数 偶数 偶数 偶数 所以 在G中结点度数为奇数的结点 在其补图中的度数也应为奇数 故G和其补图的奇数结点个数也是相同的 25 P2861 在无向图G中 从结点u到结点v有一条长度为偶数的通路 从结点u到结点v又有一条长度为奇数的通路 则在G中必有一条长度为奇数的回路 证明 设从结点u到结点v长度为偶数的通路是ue1u1e2u2 e2kv 长度为奇数的通路是ue11u11e12u12 e12h 1v 那么路ue1u1e2u2 e2kve12h 1 u12e12u11e11u就是一条回路 它的边数 2k 2h 1 2 h k 1 是奇数 故这条回路的长度是奇数 26 P2862 无向图G恰有的2个奇数度数的结点可达 解1 令u w为G恰有的2个奇度结点 考察u所在的连通分支G 因图G 的奇度点为偶数 故G 至少还有另一奇度点w 但v在G和G 中有相同的度 所以G 恰有2个奇度点而且就是u和w 再由G 的连通性推出u到w可达 解2 反证法设G中的两个奇度结点为u与v 若u与v不连通 即它们之间无路 因而u与v处于G中恰有不同连通分支中 设u在G1中 v在G2中 G1与G2是G的连通分支 由于G中恰有两个奇度结点 因而当作为独立的图时 均有一个奇度结点 这与握手定理的推论相矛盾 27 3 若图G是不连通的 则G的补图G是连通的 证明 若图G 是不连通的 可设图G的连通分支是G V1 G V2 G Vm m 2 由于任意两个连通分支G Vi 与G Vj i j 之间不连通 因此两个结点子集Vi与Vj之间的所有连线都在图G的补图G 中 任取两个结点u和v 有两种情形 a u和v分别属于两个不同结点子集Vi与Vj 由上可知G 包含边 u v 故u和v在G 中是连通的 b u和v属于同 个结点子集Vi 可在另一个结点子集Vj中取一个结点w 由上可知边 u w 及边 v w 均在G 中 故邻接边 u w 和 w v 组成的路连接结点u和v 即u和v在G 中也是连通的 由此可知 当图G不是连通图时 G 必是连通图 28 在具有n个结点的无向简单图G中 若任意2个不同结点的度数之和大于等于n 1 则图G是连通图 证明 反证法设图G不是连通图 不妨设图G有2个连通分支G1和G2 其中G1有k k 1 个结点 G2有n k个结点 在G1中任取一点vi G2中任取一点vj 则 deg vi k 1deg vj n k 1由此可得 deg vi deg vj k 1 n k 1 n 2与题设矛盾 故图G是连通图 29 证明n个结点k条边的简单图G 若k n 1 n 2 2 则图G是连通图 证明 反证法设G的补图为G 边数记为kG 则kG kG n n 1 2 假设G不连通 则G的补图是连通 kG n 1 kG kG kG n 1 利用kG kG n n 1 2 推出kG n 1 n 2 2 和题设矛盾 故图G是连通图 30 渡河问题 一个摆渡人 要把一只狼 一只羊和一捆干草运过河去 河上有一只木船 每次除了人以外 只能带一样东西 另外 如果人不在旁时 狼就要吃羊 羊就要吃干草 问这人怎样才能把它们运过河去 解 用F表示摆渡人 W表示狼 S表示羊 H表示干草 若用FWSH表示人和其它3样东西在河的左岸的状态 这样在左岸全部可能出现的状态为以下16种 FWSHFWSFWHFSHWSHFWFSFHWSWHSHFWSH 这里 表示左岸是空集 即人 狼 羊 干草都已运到右岸去了 利用通路的概念解决一个古老的著名问题 31 根据题意检查一下就可以知道 FWSHFWSFWHFSHWSHFWFSFHWSWHSHFWSH 这16种情况中有6种情况是不允许出现的 它们是 WSH FW FH WS SH F 如FH表示人和干草在左岸 而狼和羊在右岸 这当然是不行的 因此 允许出现的情况只有10种 我们构造一个图 它的结点就是这10种状态 若一种状态可以转移到另一种状态 就在表示它们的两结点间连一条边 这样就画出图 本题就转化为找结点FWSH到结点 的通路 从图中得到两条这样的通路 即有两种渡河方案 32 欧拉路 欧拉回路 欧拉图 判定 有欧拉路的充要条件 无或有两个奇数度的结点 有欧拉回路的充要条件 所有结点度数均为偶数 汉密尔顿路 汉密尔顿回路 汉密尔顿图汉密尔顿图的判定 必要条件 设无向图G 是汉密尔顿图 则对于任意非空子集S 有W G S S 推论设无向图G 是半汉密尔顿图 则对于任意非空子集S 有W G S S 1 充分条件 若简单图G中每对结点的度数和 V n 则G是汉密尔顿图 半汉密尔顿图 若简单图G中每对结点的度数和 V 1 则G是半汉密尔顿图 四 欧拉图与汉密尔顿图 会判定 33 P3112试构造一个欧拉图 其结点数v和边数e满足下述条件 1 v和e的奇偶性相同 2 v和e的奇偶性相反 解 1 2 说明 欧拉图中 结点数和边数的奇偶性既可以相同也可以相反 34 n个结点的有向完全图 哪些是有向欧拉图 为什么 解 n个结点的有向完全图是有向欧拉图 对于n个结点的有向完全图 每个结点的度数均相等 都是偶数2 n 1 且每个结点的入度 出度 所以n个结点的有向完全图是有向欧拉图 无向完全图Kn是几笔画图 为什么 1 当n 1时 Kn为平凡图 2 当n 奇数时 Kn中每个结点度数 n 1为偶数 所以Kn为欧拉图 可以一笔画出 3 当n 偶数时 Kn中每个结点度数 n 1为奇数 对应的有n 2对奇数度结点 因此可以n 2笔画出 35 删除A和B后 形成3个连通分支 即W G S 3 S 2因此 图G不是汉密尔顿图 图G是否是汉密尔顿图 A B 36 7位客人入席 A只会讲英语 B会讲英 汉语 C会讲英 意大利 俄语 D会讲日 汉语 E会讲德 意大利语 F会讲法 日 俄语 G会讲法 德语 能否安排圆桌席位使每位客人与其左右邻不用翻译便可交谈 解 建立无向图模型 结点为客人 会共同语言的2结点相邻接 则问题归结为求此图的一条汉密尔顿回路 不难验证 此图有一条汉密尔顿回路是 A B D F G E C A 按此回路安排席位可以使得每个人都可以和它两边的人直接交谈 汉密尔顿图的应用 B C D E F G A 英 英 法 德 俄 意 日 汉 37 某地有5个风景点 若每个风景点均有2条道路与其他点相通 问游人可否经过每个风景点恰好一次而游完这5处 解 将5个风景点看成是有5个结点的无向图 两风景点间的道路看成是无向图的边 因为每处均有两条道路与其他结点相通 故每个结点的度数均为2 从而任意两个不相邻的结点的度数之和等于4 正好为总结点数减1 故此图中存在一条汉密尔顿路 因此游人可以经过每个风景点恰好一次而游完这5处 38 设图G有n个结点 e条边 证明 若 则G为汉密尔顿图 证明 反证法假设G不是汉密尔顿图 则根据汉密尔顿图的判定定理 知至少存在两个结点的度数之和小于n 则该两个结点所关联的边的数目m1小于n 即m1 n 1 而当其余n 2个结点构成完全图时 其所关联的边数目m2为最大值 即m2 n 2 n 3 2 G的总的边数为m1 m2 从而与题设矛盾 所以 图G为汉密尔顿图 39 将6个人分成3组 每组2个人 去完成3项任务 已知每个人至少与其余5个人中的3个人能互相合作 问 能否使得每组的2个人都能相互合作 请说明理由 解 用v1 v2 v6代表6个人 若vi vj能相互合作 就在vi与vj之间连无向边 得无向图G V E 由已知条件可知 对于任意的vi V deg vi n 2 因此deg vi deg vj n 由定理可知G是汉密尔顿图 因而G中存在汉密尔顿回路 不妨设C vi1vi2vi3vi4vi5vi6vi1为其中一条 在这种回路上相邻两个结点代表的二人能相互合作 40 某工厂生产由6种不同颜色的纱织成的双色布 已知在品种中 每种颜色至少分别和其他5种颜色中的3种颜色搭配 证明可以挑出3种双色布 它们恰有6种不同的颜色 解 用vi表示颜色 i 1 2 6 作无向图G V E 其中V v1 v2 v6 E u v u v V且u v并且u与v搭配 u v V deg u deg v 6 所以G是汉密尔顿图 因而G中存在汉密尔顿回路 不妨设v1v2v3v4v5v6v1为其中一条 在这种回路上每个结点代表的颜色都能与它相邻结点代表的颜色相搭配 于是让v1与v2 v3与v4 v5与v6搭配 织成3种双色布 包含了6种颜色 41 下列命题中 是正确的 1 欧拉图的子图一定是欧拉图2 汉密