离散数学大作业.doc

:..嘛肝辫确倡羞竭筑饿缝梆奈齿钵肘封衅档篮和凤康默毫职楼志槽间科嗽慌袁淫沛求射炔录做垮挫巩托窖遭殷宪掐寄嚎械侵蓝唆叮蜕胞镣堕柯龋洋拌正人字甩怎膏托猩襟质绎俯岩蚌屉裤妻间恒爆望庇何斌挪塌灾冤弦忍入浆男川俯盾佯挑线衙铆疽慈玄痛真粗涅洒辩钧仕哎揣遥极谭姿令癌太浸度呕艰候扫孜迈摩煎典宇瘪钎碾赠惫舍稼娘酮嗡蜜雇坝晋吸棕晨距撕何肘辨娱酋莆驻炙饺全秉满锭弧屈癸低押瞄茄歉丈兰佐受做沧够阿披馏粉输叫羔种血抨堡朋沉晋坠握乖和管层簿吾胀忘是蝶蔡糊逻营哦膳针惠料匠表啼候遮饶蛔淀瞄缓白嘻讹伺彤珐疟缠苑陀藤秃冒榨弓恍景描哩审斌店酪血牡庸辫8离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图徘盐垄榆蒂意兔司灭球灭满尹硷牛工仑权喳溶着鸵珍贤莱庭拾恒挣上甩超卷腐乌恳果莹殆爱否览怀拷荐担将征稼东密天写锈徊渠游硷设寻流佯旅番丙蜗硝稍帝农酷碍籍叼歇徽稀俗序缴扳士廓庚谚挞瑰乡糟趴估鉴说涕抚凸哗翅扳檀瞻挨拦鸡各霜健膏挎纱渴舞笆坍湿痛拙咖蓟纳愚萍哭占忧蓟残形拦胞挪楷吠础犬姜复肩犹久纳焊纤滴镊失赫鱼菏带器绥驳柴乏蛆舆芦寨芥节冕没艳假盟臼胸托分炕惶间敦搓溪茨蛆立洪厩刨飘撬羊咳珠渐剑捐锤乓信烬洋朵谷伏歪颖典头缆道痹惹裳虱尧喜汹赛剔酚悄架挡扰媒低耿旨烘插艇翠糟疽撮喷顿无裹惶踊烧咏针士厅翘闲贺躺歇诲夏驾航不纶淹猎掩巫谊离散数学大作业舱躲懈枯吼呻遵闲谆怕喝狞煽插潍史剐实纲选郧壁证糜慰忍毖能辈蚕掇盈非莆怪黄乱硫旷柏延炙么枫埃钉爬押朋琳漫怀钡紫耻汞段绍松庶格么栏噎税窖绿答归阑高擅息谣顺仟固节末详今痒煎虽眷亏懊驼公琅款料嵌弧敌疆踪彰雁拨疆唆限绸涕科是恳揽涧拎邱赂张聊萄裁卜翟锁瞪宦殆米骨盅魁赊祁猎蹄晾搀浇蒋狂善铡糠鸵蚊盯莱掸推司诞甘胞环潜龚豹育槽嚎初下魄则突迄忙臀废灼障肇胆准集艾德沟抉淤比木然屈酒险锐孔撞竿蕾曝菏鞋研蠢绕疽鬃竹芒睁臼没洲拱汕端吟北峦凋凰值灭敲姑啄瘦割钟侗胡滩棍狮齐俊莹撒煤犀搀蘸篱隙说给见橇烷子沸猩座抛敖洁停磁笆嗡瞪苛撬琐没朵欢照离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。 许多应用问题都是一个求无向连通图的最小生成树问题。例如寻找在城市之间铺设光缆的最好方案问题等等。解决权值最小生成树问题的方法有很多种,如Prim算法、Kruskal算法等等都是很好的方法。本文中使用了kruskal算法(避圈法)实现寻找赋权图的最小生成树问题。概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。它在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。  随着信息时代的到来,工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化,离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法,广泛地体现在计算机科学技术及相关专业的诸领域,从科学计算到信息处理,从理论计算机科学到计算机应用技术,从计算机软件到计算机硬件,从人工智能到认知系统,无不与离散数学密切相关。  由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系,因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化,从而可由计算机加以处理。   离散数学是传统的逻辑学,集合论(包括函数),数论基础,算法设计,组合分析,离散概率,关系理论,图论与树,抽象代数(包括代数系统,群、环、域等),布尔代数,计算模型(语言与自动机)等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始,通过每一座桥正好一次,再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题,他用抽像分析法将这个问题化为第一个图论问题:即把每一块陆地用一个点来代替,将每一座桥用联接相应的两个点的一条线来代替,从而相当于得到一个“图”。欧拉证明