《图论部分习题课ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论部分习题课ppt课件.ppt（15页珍藏版）》请在三一办公上搜索。
1、1,图论部分知识结构图,2,第十四章 习题课,无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理；图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示,3,1数组2, 2, 2, 2, 3, 3能简单图化吗？若能，画出尽可能多的非同构的图来.,练习1,4,第十五章 习题课,欧拉通路、欧拉回路、欧拉图、半欧拉图哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题,5,练习1,1.判断下图是否为欧拉图，哈密顿图. 如果是，请在图上画出欧拉回路或哈密顿回路；如果不是，请说明理由.,不是欧拉图，因为存在奇度点；不是哈密顿图，因为这是一个奇数
2、顶点的偶图.,6,2某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？,解 图是描述事物之间关系的最好的手段之一. 做无向图G=, 其中 V=v| v为与会者， E=(u,v) | u,vV且u与v有共同语言，且u v. 易知G为简单图且vV, d(v)4，于是，u,vV, 有d(u)+d(v) 8，可知G为哈密顿图. 服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.,练习 2,7,第十六章 习题课,无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、最佳前缀码、波兰符号
3、法、逆波兰符号法,8,1设G为n 阶无向简单图，n5，证明G 或 中必含圈.,练习1,证明思路： G 和 的边数中至少有一个满足 由于n5，得mn.,9,2设T 是2叉正则树，T 有t 片树叶， 证明：T的阶数 n=2t1.,方法一：(1) n = t+i (i为分支点数)(2) n = m+1 （m为T的边数）(3) m = 2i （正则2叉树定义）由(2)、(3)得 ，代入（1）得n = 2t1.,练习2,方法二：(1) 2m = 2+3(i1)+t(2) n = m+1 = i+t由(1) 和(2) 可解出n = 2t1.,10,第十七章 平面图,本章的主要内容平面图的基本概念欧拉公式平
4、面图的判断平面图的对偶图,11,1. 证明下图为非平面图.,练习1,12,证明,证 （方法一）下图为原图的子图，它是K3,3的剖分图.,（方法二） 下图为原图的子图（删除边(a,f)），收缩本图中的(a,e)和(f,g)所得图为K5.,13,第十八章 习题课,(点)支配集、点覆盖集、点独立集边覆盖集、匹配（边独立集）二部图中的完美匹配图的点着色、边着色、面着色,14,练习1,1. 某校计算机系三年级学生在本学期共选6门选修课Ci, i=1, 2, , 6. 设S(Ci)为选Ci课的学生集. 已知 S(Ci)S(C6) , i=1, 2, , 5， S(Ci)S(Ci+1) , i=1, 2, 3, 4， S(C5)S(C1) . 问这6门课至少几天能考完？,15,解,练习1解答,解：由已知条件做无向图G=，其中 V=C1, C2, , C6， E=(Ci,Cj)| S(Ci)S(Cj)，对G进行点着色， Ci与Cj着同色 Ci与Cj不相邻 没有学生既学Ci又学Cj Ci与Cj可同时考. 于是最少的考试时间为(G)=4.,
