图论试卷08-09

第1页共3页重庆邮电大学08-09学年度第一学期《图论及其应用》研究生考试试题（A）（时间120分钟）一．填空题（每小题3分，共30分）1、设,,EVG是任意图，其中12{,,,}nVxxx，12{,,,},mEeee则n阶方阵)(ijaA称为G的邻接矩阵。其中ija为。2、图EVVG,,21是二分图的充要条件是：。3、nK(n3)中从任意指定一个顶点出发,有（）个不同的圈。A.n！B.（n-1）！C.（n-2）！D.（n-3）！4、设T是顶点数至少为5的树,则()xT()A.2B.3C.4D.55、带权为1,2,3,4,5,6的最优二叉树的权为()。A.48B.49C.50D.516、若G为长度是奇数的圈，则()xG().7、以0，1为构成元素，写出一个三阶格雷码。8、设连通图G具有欧拉回路的充要条件是。9、写出所有的正凸多面体：。10、设G是任意平面图，则()G应满足的条件。二、(6分)画出4阶3条边的所有非同构的无向简单图。三、(6分)证明：若无向图G中恰有两个奇度顶点，则这两个奇度顶点必然连通。题号一二三四五六七八九总分分数评卷人————密—————————————封————————————线————————————————————————————年级：专业：班级：姓名：学号：—————————————————————————————————————————————————————————————第2页共3页四、(10分)已知完全二分图5,5K,其中112345{,,,,}Vxxxxx，212345{,,,,}Vyyyyy,且5,5K的权矩阵为A，求5,5K的最优匹配，并求出权和。3554122022244100110012133A五、(10分)用普林算法求下图1的一棵最小生成树.六、(10’)画一个四阶五条边的欧拉图，并做出该图的对偶图.七、(10分)通过布尔变量的运算，求下图3的全部极小支配集。V2v5V1v4V3v6图31745102616158abcgfde39第3页共3页八、(6分)证明：5K不是平面图.九、(6分)证明：若,(,1)mnKmn是哈密顿图，则必有.mn十、(6分)若,mnK是树，求,mn应满足的条件.