图论部分习题课课件.ppt

《图论部分习题课课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论部分知识结构图1第十四章习题课无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理；图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示21．数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多的非同构的图来.练习13第十五章习题课欧拉通路、欧拉回路、欧拉图、半欧拉图哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题4练习11.判断下图是否为欧拉图，哈密顿图.如果是，请在图上画出欧拉回路或哈密顿回路；如果不是，请说明理由.不是欧拉图，因为存在奇度点；不是哈密顿图，因为这是一个奇数顶点的偶图.52．某次国际会议8人参加，已知

2、每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？解图是描述事物之间关系的最好的手段之一.做无向图G=,其中V={v

3、v为与会者}，E={(u,v)

4、u,vV且u与v有共同语言，且uv}.易知G为简单图且vV,d(v)4，于是，u,vV,有d(u)+d(v)8，可知G为哈密顿图.服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.练习26第十六章习题课无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法71．设G为n阶无向简单图，n5，证

5、明G或中必含圈.练习1证明思路：G和的边数中至少有一个满足由于n5，得mn.82．设T是2叉正则树，T有t片树叶，证明：T的阶数n=2t1.方法一：(1)n=t+i(i为分支点数)(2)n=m+1（m为T的边数）(3)m=2i（正则2叉树定义）由(2)、(3)得，代入（1）得n=2t1.练习2方法二：(1)2m=2+3(i1)+t(2)n=m+1=i+t由(1)和(2)可解出n=2t1.9第十七章平面图本章的主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图101.证明下图为非平面图.练习111证明证（方法一）下图为原图的子图，它是K3,3的剖分图.（方法二）下图为原图的子

6、图（删除边(a,f)），收缩本图中的(a,e)和(f,g)所得图为K5.12第十八章习题课(点)支配集、点覆盖集、点独立集边覆盖集、匹配（边独立集）二部图中的完美匹配图的点着色、边着色、面着色13练习11.某校计算机系三年级学生在本学期共选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门课至少几天能考完？14解练习1解答解：由已知条件做无向图G=，其中V={C1,C2,…,C6}，E={(Ci,Cj)

7、S(Ci)S(Cj)

8、}，对G进行点着色，Ci与Cj着同色Ci与Cj不相邻没有学生既学Ci又学CjCi与Cj可同时考.于是最少的考试时间为(G)=4.15