第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中有片树叶。3设连通无向图G有4个奇顶点，要使G变成欧拉图，在G中至少要加条边。4连通无向图G点数为n，边数为m，若G是平面图，则G有个面。5对下列图，试填下表（是¿×¿¿类图的打〝√〞，否则打〝×〞）。G1能否一笔画G1是否偶图G2是否哈密尔顿图G2是否可平面图6.下图的点色数为_______;边色数为_______。G1G2第5页共18页第4页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第5页共18页、填空题（每空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、用匈牙利算法求下图的最大匹配。第6页共18页第5页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第6页共18页题33、用匈牙利算法求下图的最大匹配。第7页共18页第6页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第7页共18页第8页共18页第7页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第8页共18页第9页共18页第8页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第9页共18页第10页共18页第9页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第10页共18页第11页共18页第10页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第11页共18页第12页共18页第11页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第12页共18页第13页共18页第12页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第13页共18页第14页共18页第13页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第14页共18页第15页共18页第14页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第15页共18页第16页共18页第15页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第16页共18页第17页共18页第16页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第17页共18页第18页共18页第17页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第18页共18页
