离散数学大作业.doc

蒃薁离散数学大作业薅肀艿虿莄莄题目赋权图的最小生成树算法蚀学院膇班级莇学生姓名蒄学号肁指导老师衿膆薄赋权图的最小生成树算法蒂摘要芇一个有n个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。 袅许多应用问题都是一个求无向连通图的最小生成树问题。例如寻找在城市之间铺设光缆的最好方案问题等等。解决权值最小生成树问题的方法有很多种,如Prim算法、Kruskal算法等等都是很好的方法。本文中使用了kruskal算法(避圈法)实现寻找赋权图的最小生成树问题。蚄虿概述羈离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。它在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。 蚃 蚄随着信息时代的到来,工业革命时代以微积分为代表的连续数学占主流的地位已经发生聿了变化,离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法,广泛地体现在计算机科学技术及相关专业的诸领域,从科学计算到信息处理,从理论计算机科学到计算机应用技术,从计算机软件到计算机硬件,从人工智能到认知系统,无不与离散数学密切相关。 蒆 由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系,因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化,从而可由计算机加以处理。 蚆  离散数学是传统的逻辑学,集合论(包括函数),数论基础,算法设计,组合分析,离散概率,关系理论,图论与树,抽象代数(包括代数系统,群、环、域等),布尔代数,计算模型(语言与自动机)等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。螄图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始,通过每一座桥正好一次,再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题,他用抽像分析法将这个问题化为第一个图论问题:即把每一块陆地用一个点来代替,将每一座桥用联接相应的两个点的一条线来代替,从而相当于得到一个“图”。欧拉证明了这个问题没有解,并且推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。 蒀1859年,英国数学家汉密尔顿发明了一种游戏:用一个规则的实心十二面体,它的20个顶点标出世界著名的20个城市,要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路,即“绕行世界”。用图论的语言来说,游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题,从而引起广泛的注意和研究。 膈在一个具有几个顶点的连通图G中,如果存在子图G'包含G中所有顶点和一部分边,且不形成回路,则称G'为图G的生成树,代价最小生成树则称为最小生成树。 蒅许多应用问题都是一个求无向连通图的最小生成树问题。例如:要在n个城市之间铺设光缆,主要目标是要使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同;另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。生成树和最小生成树有许多重要的应用。 袄袁最小生成树:蚆在一给定的无向图G=(V,E)中,(u,v)代表连接顶点u与顶点v的边(即),而w(u,v)代表此边的权重,若存在T为E的子集(即)且为无循环图,使得的w(T)最小,则此T为G的最小生成树。其中芄羃最小生成树其实是最小权重生成树的简称。许多应用问题都是一个求无向连通图的最小生成树问题。羈【例】图G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价)。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。 莈最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有