(图论A)重庆邮电大学研究生考卷.docVIP

重庆邮电大学研究生考卷 学号 姓名 考试方式 班级 2010级 考试课程名称 图论及其算法 考试时间： 年 月 日 题号 一 二 三 四 五 六 七 八 九 十 十一 十二 总分 得分 一、解答题（每题10分，共70分） 1、(10分)画出4阶完全图所有非同构的生成子图。请说明是否有自补图，如果有，有几个？是否有生成树，如果有，有几棵？2、(10分)有向图G如下图所示，计算G的邻接矩阵的前4次幂，回答下列问题。 （1）G中v1到v4的长度为4的通路有几条？ （2）G中v1到v1的长度为4的回路有几条？ （3）G中长度为4的通路总数是多少？其中有多少条是回路？ （4）G中长度小于等于4的通路有几条？其中有多少条是回路？（5）写出G的可达矩阵。 3、 (1)判断命题“任意阶完全图都是欧拉图”的真假，并说明理由(5分) (2)设是分划为的二分图,且,则一定不是哈密顿图(5分) 、（10分）分别用普林算法和克鲁斯卡尔算法求下图最小支撑树，写出详细求解步骤。 （10分）通过布尔变量的运算，求下图的极大独立集。 6、（10分）已知工人做工作的效率为为下面矩阵所示 给出一种工作效率最大的任务分配方案，最大工作效率是多少？ 、(1)如果两个图同构,则其对偶图必定同构,这种说法是否正确?如果正确,请证明,如果不正确,请举反例说明 (5分)(2)求阶完全图的色多项式,并写出(5分)、(10分)有n个人,任意两个人合起来认识其余的n-2个人。 证明：当n≥4时,这n个人能站成一圈,使每一个人的两旁站着自己认识的人、(10分) 设G是带v个顶点，e条边的连通的平面简单图，其中v(3且圈的长度至少为(如果有圈)证明:(1) ; (2)、（10分）证明树是一个二分图完全二分图是树？ 3 页 共 3 页 v7 v2 v5 v6 v4 v3 v11 9 3 e d f g c b a 8 15 16 6 2 10 2 4 7 1