第1页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共18页信科091、092图论及应用2011年12月26日一、(10分)求下图的最小生成树T,并求其权和
√√一二三四五六七八一、(10分)求下图的最小生成树T,并求其权和
2346162743155第2页共18页第1页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共18页二
（10分）用Dijkstra算法求解下图中从到其余各点的最短距离（要求写出详细步骤）三．(10分)有8种化学药品需要空运飞越整个国家
某些药品之间要发生化学反应，所以不能放在同一个容器中
化学药品被标记为c1,c2,…,c8
下面列出的是某种给定的化学药品能够发生反应的其它化学药品：求运送这批化学药品需要的最少容器，并给出这批药品的一种最少分类存储方式
(要求用图论方法求解)第3页共18页第2页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共18页二
（10分）用Dijkstra算法求解下图中从到其余各点的最短距离（要求写出详细步骤）三．(10分)有8种化学药品需要空运飞越整个国家
某些药品之间要发生化学反应，所以不能放在同一个容器中
化学药品被标记为c1,c2,…,c8
下面列出的是某种给定的化学药品能够发生反应的其它化学药品：求运送这批化学药品需要的最少容器，并给出这批药品的一种最少分类存储方式
(要求用图论方法求解)四(10分)证明：在任何图中，奇度点个数为偶数
第4页共18页第3页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第4页共18页四(10分)证明：在任何图中，奇度点个数为偶数
、填空题（每空3分，共30分）1．无向完全图K6有条边
2．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有片树
