图论算法及其MATLAB实现

前言

　　图论算法广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等众多学科领域。随着这些学科的发展，特别是计算机科学的快速发展，又大大促进了图论和其他学科的发展。　　图论算法是计算机科学的核心。近几年，随着强有力的MATLAB等数学软件的迅速发展，图论算法在数学和计算机等各学科方面的应用越来越广泛，从而使各学科的研究者越来越多地重视图论算法及其MATLAB实现和典型案例，而市场上又缺少这方面的指导性书籍。　　本书将图论的基础知识、图论的著名问题以及相应的MATI.AB程序代码和简单实例完美地结合在一起，力求语言简洁易懂，问题广泛有趣，算法科学，实例浅显，增强MATLAB实现的技巧性和操作性。读者可以通过简单案例，把图论的重要算法与MALLAB编程完美结合。　　本书力求内容丰富，各章节相互联系，具备指导性书籍的系统性、科学性、实用性和引导性；同时，各章又相对独立，自成体系，为读者提供极大方便。　　本书的创新之处在于，每一章均以著名实际问题为引入点，以图论算法为指导线，运用简单案例达到与MATLAB实现的完美结合，真正让各层次的读者学会运用图论理论解决实际问题，从而培养读者的图论思维，使读者惊叹图论方法的美妙与魅力。最后还为读者提供了当今图论标号方面等未解决的问题。　　本书将在每一章节中给出著名图论的算法步骤及其一般MATLAB程序；同时，紧随每个案例分析，均给出解决问题的。MATLAB源程序，这样对于初学者来说，具有很强的编程操作性。　　本书是在中国地质大学（北京）王海英多年专业讲义的基础上重新修订编写而成，其中，山东体育学院体育运动学校的李传涛完成了本书程序的编写工作；中国科学院数学与系统科学院的黄强完成了本书全部程序的调试、修改和图形绘制等工作，褚宝增教授完成全书的定稿和校正工作。作者相信，此书将开启图论算法与MATLAB完美结合的首页，也将为更多有实际需求的读者提供更多的指导。　　十分感谢中国地质大学（北京）2008年教学研究与教学改革立项的支持（项目题目：数学知识、数学建模与MATIAB等数学软件在实践中相互结合的理论研究）！感谢北京航空航天大学出版社的认可、建议和关心！此外，本文的算法思想均离不开古今中外图论算法研究的完美理论与应用，感谢这些图论研究者们！

书籍目录

第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　求两点间最短路的WarshallFloyd算法及其MATLAB实现　　2.6.1　Floyd算法的基本思想　　2.6.2　Floyd算法的基本步骤　　2.6.3　WarshallFloyd算法的MATLAB实现　2.7　求任意两点间最短路的算法及其MATLAB实现　2.8　求从一固定点到其他所有点最短路的算法及其MATLAB实现　2.9　求必须通过指定两个点的最短路的算法及其MATLAB实现　2.10　求图的两顶点间最短路与次短路的算法及其MATLAB实现　2.11　求最大可靠路的算法及其MATLAB实现　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图第6章 匹配问题及其算法第7章 网络流的算法第8章 最小费用流及BusackerGowan迭代算法第9章 图的染色参考文献

作者简介

《图论算法及其MATLAB实现》系统介绍了图论重要算法的思想及其MATLAB实现。全书分为相对独立的9章，每章都是解决一类问题的算法思想及其MATLAB实现，首先介绍有关基础知识，然后给出相关著名实际问题及解决此问题的算法思想，最后给出MATLAB实现。第1章主要介绍图论的基础知识，同时也给出了可达矩阵的计算，以及关联矩阵和邻接矩阵的相互转换等重要算法及其MATLAB实现；第2～8章分别介绍最短路、连通图、树、Euler图和Hamilton图、匹配、网络中的流、最小费用流等相关问题，而且均给出了有关问题的解决算法及其MATLAB实现；第9章主要介绍染色问题，本章不仅介绍了几种传统的染色思想，而且还给出了当今研究领域中非常活跃的非传统染色思想，并分别给出其MATLAB实现。

《图论算法及其MATLAB实现》可供数学、计算机科学、工程科学等学科中相关专业的大学生、研究生阅读，也可供相关专业研究人员参考。

图书封面

---

 图论算法及其MATLAB实现下载

---