logo资料库

图论算法及其MATLAB实现.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：1.26M 资料格式：pdf 举报 版权申诉
第1页 / 共33页
第2页 / 共33页
第3页 / 共33页
第4页 / 共33页
第5页 / 共33页
第6页 / 共33页
第7页 / 共33页
第8页 / 共33页
资料共33页，剩余部分请下载后查看
    北京航空航天大学出版社
    MATLAB 开发实例系列图书 图论算法及其 MATLAB实现 王海英 黄 强 李传涛 褚宝增 编著 图
    内 容 简 介 本书系统介绍了图论重要算法的思想及其 MATLAB实现。 全书分为相对独立的9章,每章都是解决一类问题的算法思想及其 MATLAB实现,首先介绍 有关基础知识,然后给出相关著名实际问题及 解 决 此 问 题 的 算 法 思 想,最 后 给 出 MATLAB 实 现。 第1章主要介绍图论的基础知识,同 时 也 给 出 了 可 达 矩 阵 的 计 算,以 及 关 联 矩 阵 和 邻 接 矩 阵 的 相 互转换 等 重 要 算 法 及 其 MATLAB 实 现;第2~8 章 分 别 介 绍 最 短 路、连 通 图、树、Euler 图 和 Hamilton图、匹 配、网 络 中 的 流、最 小 费 用 流 等 相 关 问 题,而 且 均 给 出 了 有 关 问 题 的 解 决 算 法 及 其 MATLAB实现;第9章主要介绍染色问题,本 章 不 仅 介 绍 了 几 种 传 统 的 染 色 思 想,而 且 还 给 出 了 当今研究领域中非常活跃的非传统染色思想,并分别给出其 MATLAB实现。 本书可供数学、计算机科学、工程科学等学科中相关专业的大学生、研究生阅读,也可供相关专 业研究人员参考。 图书在版编目(CIP)数据 图论算法及其 MATLAB 实现/王海英等编著. 北京 :北京航空航天大学出版社,2010.2 ISBN978 7 81124 940 8 Ⅰ.①图… Ⅱ.①王… Ⅲ.①图论算法②计算机辅助 计算—软件包,MATLAB Ⅳ.①0157.5②TP391.75 中国版本图书馆CIP数据核字(2009)第186090号 图论算法及其 MATLAB实现 王海英 黄 强 李传涛 褚宝增 编著 责任编辑 宋淑娟 * * 北京航空航天大学出版社出版发行 北京市海淀区学院路37号(100191) 发行部电话:(010)82317024 传真:(010)82328026 http://www.buaapress.com.cn E-mail:bhpress@263.net 印刷有限公司印装 各地书店经销 2010年2月第1版 2010年2月第1次印刷 印数:4000册 开本:787×1092 1/16 印张:10.25 字数:262千字 ISBN978 7 81124 940 8 定价:24.00元 北京航空航天大学出版社
    前 言 图论算法广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、 管理科学、社会科学等众多学科领域。随着这些学科的发展,特别是计算机科学的快速发展, 又大大促进了图论和其他学科的发展。 图论算法是计算机科学的核心。近几年,随着强有力的 MATLAB 等数学软件的迅速发 展,图论算法在数学和计算机等各学科方面的应用越来越广泛,从而使各学科的研究者越来越 多地重视图论算法及其 MATLAB 实现和典型案例,而市场上又缺少这方面的指导性书籍。 本书将图论的基础知识、图论的著名问题以及相应的 MATLAB 程序代码和简单实例完美 地结合在一起,力求语言简洁易懂,问题广泛有趣,算法科学,实例浅显,增强 MATLAB 实现的 技巧性和操作性。读者可以通过简单案例,把图论的重要算法与 MATLAB 编程完美结合。 本书力求内容丰富,各章 节 相 互 联 系,具 备 指 导 性 书 籍 的 系 统 性、科 学 性、实 用 性 和 引 导 性;同时,各章又相对独立,自成体系,为读者提供极大方便。 本书的创新之处在于,每一章均以著名实际问题为引入点,以图论算法为指导线,运用简 单案例达到与 MATLAB 实现的完美结合,真正让各层次的读者学会运用图论理论解决实际 问题,从而培养读者的图论思维,使读者惊叹图论方法的美妙与魅力。最后还为读者提供了当 今图论标号方面等未解决的问题。 本书将在每一章节中给出著名图论的算法步骤及其一般 MATLAB 程序;同时,紧随每个案 例分析,均给出解决问题的 MATLAB 源程序,这样对于初学者来说,具有很强的编程操作性。 本书是在中国地质大学(北京)王海英多年专业讲义的基础上重新修订编写而成,其中,山 东体育学院体育运动学校的李传涛完成了本书程序的编写工作;中国科学院数学与系统科学 院的黄强完成了本书全部程序的调试、修改和图形绘制等工作,禇宝增教授完成全书的定稿和 校正工作。作者相信,此书将开启图论算法与 MATLAB 完美结合的首页,也将为更多有实际 需求的读者提供更多的指导。 十分感谢中国地质大学(北京)2008年教学研究与教学改革立项的 支 持(项 目 题 目:数 学 知识、数学建模与 MATLAB 等数学软件在实践中相互结合的理论研究)! 感谢北京航空航天 大学出版社的认可、建议和关心! 此外,本文的算法思想均离不开古今中外图论算法研究的完 美理论与应用,感谢这些图论研究者们! 北京航空航天大学出版社联合 MATLAB 中文论坛(http://www.iLoveMatlab.cn)为本 书设立了在线交流版块,地址是http://www.iLoveMatlab.cn/forum-170-1.html,有问必答! 作者会第一时间在 MATLAB 中文论坛勘误,也会根据读者要求陆续上传更多案例和相关知 识链接,还会随着 MATLAB 版本的升级增添必要的内容以满足读者的需求。希望这本不断 “成长”的书能最大限度地解决读者在学习、研究、工作中遇到的与图论相关的问题。 由于水平有限,书中缺陷和错误恳请读者批评指正。最后,再次感谢我们所参考的书籍和 文献的作者! 编 者 2009年10月 前北京航空航天大学出版社
    目 录 ……………………………………………………………………………… ……………………………………………………………… ………………………………………………………………………………………… ………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………… …………………………………………………………………………… …………………………………………………………………………… ………………………………………………………………… ………………………………… ………………………… ………………………………………………………………………………………… ………………………………………………………………………………… ………………………………………………………………………… 第1章 图论的基础知识 1.1 图论的起源 1.2 著名的图论学者———欧拉 1.3 图 1.4 特殊图类 1.5 有向图 1.6 图的矩阵表示 1.6.1 邻接矩阵 1.6.2 关联矩阵 1.7 图论的基本性质和定理 1.8 计算有向图的可达矩阵的算法及其 MATLAB 实现 1.9 关联矩阵和邻接矩阵的相互转换算法及其 MATLAB 实现 习题一 第2章 最短路 2.1 路 2.2 最短路问题 2.3 求连通图最短距离矩阵的算法及其 MATLAB 实现 2.4 求两点间最短路的Dijkstra算法及其 MATLAB 实现 2.4.1 Dijkstra算法 2.4.2 Dijkstra算法的 MATLAB 实现 2.5 求两点间最短路的改进的Dijkstra算法及其 MATLAB 实现 2.5.1 Dijkstra矩阵算法Ⅰ 2.5.2 Dijkstra矩阵算法Ⅱ 2.6 求两点间最短路的 Warshall Floyd算法及其 MATLAB 实现 2.6.1 Floyd算法的基本思想 2.6.2 Floyd算法的基本步骤 2.6.3 Warshall Floyd算法的 MATLAB 实现 2.7 求任意两点间最短路的算法及其 MATLAB 实现 2.8 求从一固定点到其他所有点最短路的算法及其 MATLAB 实现 2.9 求必须通过指定两个点的最短路的算法及其 MATLAB 实现 2.10 求图的两顶点间最短路与次短路的算法及其 MATLAB 实现 2.11 求最大可靠路的算法及其 MATLAB 实现 ………………………………………………………………………………………… ……………………………………………………………………………… ………………………………… ……………………………… ……………………………………………………………………… ………………………………………………… ……………………… ……………………………………………………………… ……………………………………………………………… …………………… …………………………………………………………… …………………………………………………………… ……………………………………… …………………………………… …………………… ……………………… …………………… ………………………………………… 1 1 1 2 3 4 5 5 5 6 6 7 11 12 12 13 14 15 16 16 18 18 18 21 22 22 22 25 27 29 32 34 北京航空航天大学出版社
    …………………………………… ………………………………………………………………………………………… ………………………………………………………………………………… …………………………………………… ……………………………… …………………………………… ………………………………………………………………………………………… ……………………………………………………………………………………… 2.12 求最大期望容量路的算法及其 MATLAB 实现 习题二 第3章 连通图 3.1 判断图的连通性算法及其 MATLAB 实现 3.2 连通图的中心和加权中心的算法及其 MATLAB 实现 3.3 连通无向图一般中心的算法及其 MATLAB 实现 习题三 第4章 树 4.1 树及其性质 4.2 割点、割边、割集 4.3 二元树与 Huffman树 4.3.1 有序二元树 4.3.2 Huffman树 4.4 求 Huffman树及其 MATLAB 实现 4.5 广度优先搜索算法及其 MATLAB 实现 4.6 深度优先搜索算法及其 MATLAB 实现 4.7 求割点算法及其 MATLAB 实现 4.8 生成树及其个数 4.9 求无向图的生成树算法及其 MATLAB 实现 4.10 求有向图的生成树算法及其 MATLAB 实现 4.11 求有向连通图的外向树与内向树数目的算法及其 MATLAB 实现 4.12 最小生成树问题 4.13 求最小生成树的 Kruskal算法及其 MATLAB 实现 4.13.1 Kruskal算法的基本思想 4.13.2 Kruskal算法的 MATLAB 实现 4.14 求最小生成树的Prim 算法及其 MATLAB 实现 4.14.1 Prim 算法的基本思想 4.14.2 Prim 算法的 MATLAB 实现 习题四 第5章 Euler图和 Hamilton图 5.1 Euler图 5.2 “一笔画”问题及其理论 5.3 中国邮递员问题 5.4 Fleury算法及其 MATLAB 实现 5.4.1 Fleury算法的步骤 5.4.2 Fleury算法的 MATLAB 实现 ……………………………………………………………………………… ………………………………………………………………………… ………………………………………………………………… ………………………………………………………………………… ……………………………………………………………………… ………………………………………………… ……………………………………………… ……………………………………………… ……………………………………………………… ………………………………………………………………………… ………………………………………… ……………………………………… ……………… ……………………………………………………………………… ……………………………… ……………………………………………………… ……………………………………………… ………………………………… …………………………………………………………… …………………………………………………… ………………………………………………………………………………………… ………………………………………………………………………………… ………………………………………………………………… ………………………………………………………………………… ……………………………………………………… ……………………………………………………………… …………………………………………………… 36 38 40 40 42 44 46 48 48 50 51 51 51 52 55 57 61 65 67 69 71 73 74 74 74 76 76 77 79 81 81 81 82 82 82 82 ……………………………………………………………… 北京航空航天大学出版社
    …………………………………………………………………………… ………………………………………………………………………… ……………………………………………………… ………………………………………………………………………………………… ………………………………………………………………… ……………………………………………………………………… ……………………………………………………………… ………………………………………………………………………… ………………………………………… ……………………………… …………………………………………………………………………… ……………………………………………………… ……………………………………………………………… …………………………………………………… ……………………………………………………… ………………………………………………………………………… ……………………………………… …………………………………………… ……………… …………………………………… ………………………………………………………………………… ………………………………………………………………………………………… 5.5 Hamilton图 5.6 旅行售货员问题 5.7 改良圈算法及其 MATLAB 实现 习题五 第6章 匹配问题及其算法 6.1 问题起源———婚配问题 6.2 二分图的有关知识 6.3 匹配、完美匹配、最大匹配 6.4 匹配的基本定理 6.5 应用案例———Bernolli Euler错放信笺问题 6.6 寻求图的一个较大基数匹配算法及其 MATLAB 实现 6.7 人员分配问题 6.8 匈牙利算法及其 MATLAB 实现 6.8.1 匈牙利算法基本步骤 6.8.2 匈牙利算法的 MATLAB 实现 6.8.3 案例及其 MATLAB 实现 6.9 最优分配问题 6.10 Kuhn Munkres算法及其 MATLAB 实现 6.10.1 Kuhn Munkres算法的基本思想 6.10.2 利用可行顶点标记求最佳匹配的 Kuhn Munkras算法步骤 6.10.3 Kuhn Munkres算法的 MATLAB 实现 6.10.4 简单实验 习题六 第7章 网络流的算法 7.1 网络、流和割 7.1.1 网络和流 7.1.2 割 7.2 网络的最大流问题 7.3 最大流最小割定理 7.4 Ford Fulkerson标号算法及其 MATLAB 实现 7.4.1 Ford Fulkerson标号算法的基本步骤 7.4.2 Ford Fulkerson 标号算法的 MATLAB 实现 7.4.3 案例及其 MATLAB 实现 7.5 Dinic算法及其 MATLAB 实现 7.5.1 Dinic算法的基本思想 7.5.2 Dinic算法的 MATLAB 实现 7.5.3 案例及其 MATLAB 实现 87 88 89 92 93 93 93 93 94 95 95 97 97 97 98 100 101 101 101 102 102 105 107 108 108 108 109 110 110 111 111 112 113 114 114 115 118 …………………………………………………………………… ………………………………………………………………………… …………………………………………………………………………… ………………………………………………………………………… ………………………………………………………………………………… …………………………………………………………………… …………………………………………………………………… …………………………………… ……………………………………… ……………………………… ……………………………………………………… ……………………………………………………… …………………………………………………………… …………………………………………………… ……………………………………………………… 北京航空航天大学出版社
    ………………………………………… ……………………………………………………………………… ………………………………… ……………………………………………………… ………………………………… ……………………………………………………… ………………………………………………………………………………………… ……………………………………………………………………………… ………………………………………………… ……………………………………………………… ………………………………………………………………………………………… 7.6 容量有上下界的网络及其相关算法 7.7 有供需约束的流及其相关算法 习题七 第8章 最小费用流及 Busacker Gowan迭代算法 8.1 最小费用流问题 8.2 Busacker Gowan迭代算法及其 MATLAB 实现 8.2.1 Busacker Gowan迭代法 8.2.2 Busacker Gowan迭代法的 MATLAB 实现 8.2.3 案例及其 MATLAB 实现 习题八 第9章 图的染色 9.1 染色问题起源 9.2 顶点染色及其算法的 MATLAB 实现 9.2.1 顶点染色以及顶点色数 9.2.2 应用案例:贮藏问题 9.2.3 顶点染色算法的 MATLAB 实现 9.3 边染色算法及其 MATLAB 实现 9.3.1 边染色以及边色数 9.3.2 应用案例:排课问题 9.3.3 边染色算法的 MATLAB 实现 9.4 全染色算法及其 MATLAB 实现 9.4.1 全染色以及全色数 9.4.2 全染色算法与案例 9.5 均匀全染色算法及其 MATLAB 实现 9.5.1 均匀全染色以及均匀全色数 9.5.2 均匀全染色算法的 MATLAB 实现与案例 9.6 邻点可区别全染色算法及其 MATLAB 实现 习题九 ………………………………………………………………………… ……………………………………………… ………………………………………………………… ……………………………………………………………… ……………………………………………… …………………………………………………… ……………………………………………………………… ……………………………………………………………… ………………………………………………… …………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………… …………………………………………………… …………………………………… ……………………………………… ………………………………………………………………………………………… 参考文献 ………………………………………………………………………………………… 121 123 125 126 126 127 127 128 130 132 133 133 134 134 135 135 137 137 138 138 141 141 141 144 144 144 149 152 153 北京航空航天大学出版社
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料