图论算法及其MATLAB实现[1]

MATLAB开发实例系列图书图图论算法及其MATLAB实现王海英黄强李传涛褚宝增编著内容简介本书系统介绍了图论重要算法的思想及其MATLAB实现。全书分为相对独立的9章,每章都是解决一类问题的算法思想及其MATLAB实现,首先介绍有关基础知识,然后给出相关著名实际问题及解决此问题的算法思想,最后给出MATLAB实现。第1章主要介绍图论的基础知识,同时也给出了可达矩阵的计算,以及关联矩阵和邻接矩阵的相互转换等重要算法及其MATLAB实现;第2~8章分别介绍最短路、连通图、树、Euler图和Hamilton图、匹配、网络中的流、最小费用流等相关问题,而且均给出了有关问题的解决算法及其MATLAB实现;第9章主要介绍染色问题,本章不仅介绍了几种传统的染色思想,而且还给出了当今研究领域中非常活跃的非传统染色思想,并分别给出其MATLAB实现。本书可供数学、计算机科学、工程科学等学科中相关专业的大学生、研究生阅读,也可供相关专业研究人员参考。图书在版编目(CIP)数据图论算法及其MATLAB实现/王海英等编著.北京:北京航空航天大学出版社,2010.2ISBN9787811249408Ⅰ.①图…Ⅱ.①王…Ⅲ.①图论算法②计算机辅助计算—软件包,MATLABⅣ.①0157.5②TP391.75中国版本图书馆CIP数据核字(2009)第186090号图论算法及其MATLAB实现王海英黄强李传涛褚宝增编著责任编辑宋淑娟*北京航空航天大学出版社出版发行北京市海淀区学院路37号(100191)发行部电话:[phone]传真:(010)[e-mail]印刷有限公司印装各地书店经销*开本:787×10921/16印张:10.25字数:262千字2010年2月第1版2010年2月第1次印刷印数:4000册ISBN9787811249408定价:24.00元前前言图论算法广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等众多学科领域。随着这些学科的发展,特别是计算机科学的快速发展,又大大促进了图论和其他学科的发展。图论算法是计算机科学的核心。近几年,随着强有力的MATLAB等数学软件的迅速发展,图论算法在数学和计算机等各学科方面的应用越来越广泛,从而使各学科的研究者越来越多地重视图论算法及其MATLAB实现和典型案例,而市场上又缺少这方面的指导性书籍。本书将图论的基础知识、图论的著名问题以及相应的MATLAB程序代码和简单实例完美地结合在一起,力求语言简洁易懂,问题广泛有趣,算法科学,实例浅显,增强MATLAB实现的技巧性和操作性。读者可以通过简单案例,把图论的重要算法与MATLAB编程完美结合。本书力求内容丰富,各章节相互联系,具备指导性书籍的系统性、科学性、实用性和引导性;同时,各章又相对独立,自成体系,为读者提供极大方便。本书的创新之处在于,每一章均以著名实际问题为引入点,以图论算法为指导线,运用简单案例达到与MATLAB实现的完美结合,真正让各层次的读者学会运用图论理论解决实际问题,从而培养读者的图论思维,使读者惊叹图论方法的美妙与魅力。最后还为读者提供了当今图论标号方面等未解决的问题。本书将在每一章节中给出著名图论的算法步骤及其一般MATLAB程序;同时,紧随每个案例分析,均给出解决问题的MATLAB源程序,这样对于初学者来说,具有很强的编程操作性。本书是在中国地质大学(北京)王海英多年专业讲义的基础上重新修订编写而成,其中,山东体育学院体育运动学校的李传涛完成了本书程序的编写工作;中国科学院数学与系统科学院的黄强完成了本书全部程序的调试、修改和图形绘制等工作,禇宝增教授完成全书的定稿和校正工作。作者相信,此书将开启图论算法与MATLAB完美结合的首页,也将为更多有实际需求的读者提供更多的指导。十分感谢中国地质大学(北京)2008年教学研究与教学改革立项的支持(项目题目:数学知识、数学建模与MATLAB等数学软件在实践中相互结合的理论研究)!感谢北京航空航天大学出版社的认可、建议和关心!此外,本文的算法思想均离不开古今中外图论算法研究的完美理论与应用,感谢这些图论研究者们!北京航空航天大学出版社联合MATLAB中文论坛()为本书设立了在线交流版块,地址是有问必答!作者会第一时间在MATLAB中文论坛勘误,也会根据读者要求陆续上传更多案例和相关知识链接,还会随着MATLAB版本的升级增添必要的内容以满足读者的需求。希望这本不断“成长”的书能最大限度地解决读者在学习、研究、工作中遇到的与图论相关的问题。由于水平有限,书中缺陷和错误恳请读者批评指正。最后,再次感谢我们所参考的书籍和文献的作者!编者2009年10月目录第1章图论的基础知识1…………………………………………………………………………1.1图论的起源1………………………………………………………………………………1.2著名的图论学者———欧拉1………………………………………………………………1.3图2…………………………………………………………………………………………1.4特殊图类3…………………………………………………………………………………1.5有向图4……………………………………………………………………………………1.6图的矩阵表示5……………………………………………………………………………1.6.1邻接矩阵5……………………………………………………………………………1.6.2关联矩阵5……………………………………………………………………………1.7图论的基本性质和定理6…………………………………………………………………1.8计算有向图的可达矩阵的算法及其MATLAB实现6…………………………………1.9关联矩阵和邻接矩阵的相互转换算法及其MATLAB实现7…………………………习题一11…………………………………………………………………………………………第2章最短路12…………………………………………………………………………………2.1路12…………………………………………………………………………………………2.2最短路问题13………………………………………………………………………………2.3求连通图最短距离矩阵的算法及其MATLAB实现14…………………………………2.4求两点间最短路的Dijkstra算法及其MATLAB实现15………………………………2.4.1Dijkstra算法16………………………………………………………………………2.4.2Dijkstra算法的MATLAB实现16…………………………………………………2.5求两点间最短路的改进的Dijkstra算法及其MATLAB实现18………………………2.5.1Dijkstra矩阵算法Ⅰ18………………………………………………………………2.5.2Dijkstra矩阵算法Ⅱ18………………………………………………………………2.6求两点间最短路的WarshallFloyd算法及其MATLAB实现21……………………2.6.1Floyd算法的基本思想22……………………………………………………………2.6.2Floyd算法的基本步骤22……………………………………………………………2.6.3WarshallFloyd算法的MATLAB实现22………………………………………2.7求任意两点间最短路的算法及其MATLAB实现25……………………………………2.8求从一固定点到其他所有点最短路的算法及其MATLAB实现27……………………2.9求必须通过指定两个点的最短路的算法及其MATLAB实现29………………………2.10求图的两顶点间最短路与次短路的算法及其MATLAB实现32……………………2.11求最大可靠路的算法及其MATLAB实现34…………………………………………若您对此书内容有任何疑问,可以凭在线交流卡登录中文论坛与作者交流。22.12求最大期望容量路的算法及其MATLAB实现36……………………………………习题二38…………………………………………………………………………………………第3章连通图40…………………………………………………………………………………3.1判断图的连通性算法及其MATLAB实现40……………………………………………3.2连通图的中心和加权中心的算法及其MATLAB实现42………………………………3.3连通无向图一般中心的算法及其MATLAB实现44……………………………………习题三46…………………………………………………………………………………………第4章树48………………………………………………………………………………………4.1树及其性质48………………………………………………………………………………4.2割点、割边、割集50…………………………………………………………………………4.3二元树与Huffman树51…………………………………………………………………4.3.1有序二元树51…………………………………………………………………………4.3.2Huffman树51………………………………………………………………………4.4求Huffman树及其MATLAB实现52…………………………………………………4.5广度优先搜索算法及其MATLAB实现55………………………………………………4.6深度优先搜索算法及其MATLAB实现57………………………………………………4.7求割点算法及其MATLAB实现61………………………………………………………4.8生成树及其个数65…………………………………………………………………………4.9求无向图的生成树算法及其MATLAB实现67…………………………………………4.10求有向图的生成树算法及其MATLAB实现69………………………………………4.11求有向连通图的外向树与内向树数目的算法及其MATLAB实现71………………4.12最小生成树问题73………………………………………………………………………4.13求最小生成树的Kruskal算法及其MATLAB实现74………………………………4.13.1Kruskal算法的基本思想74………………………………………………………4.13.2Kruskal算法的MATLAB实现74………………………………………………4.14求最小生成树的Prim算法及其MATLAB实现76…………………………………4.14.1Prim算法的基本思想76……………………………………………………………4.14.2Prim算法的MATLAB实现77……………………………………………………习题四79…………………………………………………………………………………………第5章Euler图和Hamilton图81………………………………………………………………5.1Euler图81…………………………………………………………………………………5.2“一笔画”问题及其理论81…………………………………………………………………5.3中国邮递员问题82…………………………………………………………………………5.4Fleury算法及其MATLAB实现82………………………………………………………5.4.1Fleury算法的步骤82………………………………………………………………5.4.2Fleury算法的MATLAB实现82……………………………………………………图论算法及其MATLAB实现若您对此书内容有任何疑问,可以凭在线交流卡登录中文论坛与作者交流。35.5Hamilton图87…………………………………………………