武汉纺织大学考试试卷模板

1信科091、092图论及应用2011年12月26日一、(10分)求下图的最小生成树T,并求其权和.2346162743155√√一二三四五六七八一、(10分)求下图的最小生成树T,并求其权和.2二.（10分）用Dijkstra算法求解下图中从1v到其余各点的最短距离（要求写出详细步骤）三．(10分)有8种化学药品需要空运飞越整个国家。某些药品之间要发生化学反应，所以不能放在同一个容器中。化学药品被标记为c1,c2,…,c8。下面列出的是某种给定的化学药品能够发生反应的其它化学药品：1256:,,cccc2357:,,cccc3247:,,cccc43678:,,,ccccc512678:,,,,cccccc61458:,,,ccccc723458:,,,,cccccc84567:,,,ccccc求运送这批化学药品需要的最少容器，并给出这批药品的一种最少分类存储方式。(要求用图论方法求解)3四(10分)证明：在任何图中，奇度点个数为偶数。4、填空题（每空3分，共30分）1．无向完全图K6有条边。2．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有片树叶。3设连通无向图G有4个奇顶点，要使G变成欧拉图，在G中至少要加条边。4连通无向图G点数为n，边数为m，若G是平面图，则G有个面。5对下列图，试填下表（是类图的打〝√〞，否则打〝×〞）。G1G2G1能否一笔画G1是否偶图G2是否哈密尔顿图G2是否可平面图6.下图的点色数为_______;边色数为_______。5题33、用匈牙利算法求下图的最大匹配。678910111213141516