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