社 版 出 学 大 天 航 空 航 京 北
MATLAB 开发实例系列图书
图论算法及其 MATLAB 实现
版社 王海英 黄 强 李传涛 褚宝增 编著 出
学 大 天 航 空 航 京 北
内容简介
本书系统介绍了图论重要算法的思想及其 MATLAB 实现。 全书分为相对独立的9章,每章都是解决一类问题的算法思想及其 MATLAB 实现,首先介绍 有关基础知识,然后给出相关著名实际问题 及 解 决 此 问 题 的 算 法 思 想,最 后 给 出 MATLAB 实 现。 第1章主要介绍图论的基础知识,同 时 也 给 出 了 可 达 矩 阵 的 计 算,以 及 关 联 矩 阵 和 邻 接 矩 阵 的 相 互转换 等 重 要 算 法 及 其 MATLAB 实 现;第 2~8 章 分 别 介 绍 最 短 路、连 通 图、树、Euler 图 和 Hamilton图、匹 配、网 络 中 的 流、最 小 费 用 流 等 相 关 问 题,而 且 均 给 出 了 有 关 问 题 的 解 决 算 法 及 其 MATLAB 实现;第9章主要介绍染色问 题,本 章 不 仅 介 绍 了 几 种 传 统 的 染 色 思 想,而 且 还 给 出 了 当今研究领域中非常活跃的非传统染色思想,并分别给出其 MATLAB 实现。 本书可供数学、计算机科学、工程科学等 学 科 中 相 关 专 业 的 大 学 生、研 究 生 阅 读,也 可 供 相 关 专 业研究人员参考。
由 于 水 平 有 限 ,书 中 缺 陷 和 错 误 恳 请 读 者 批 评 指 正 。 最 后 ,再 次 感 谢 我 们 所 参 考 的 书 籍 和
文献的作者!
编者 2009 年 10 月
目录
第1章 图论的基础知识………………………………………………………………………… 1
1.1 图论的起源 ……………………………………………………………………………… 1 1.2 著名的图论学者———欧拉 ……………………………………………………………… 1 1.3 图 ………………………………………………………………………………………… 2 1.4 特殊图类 ………………………………………………………………………………… 3 1.5 有向图 …………………………………………………………………………………… 4 1.6 图的矩阵表示 …………………………………………………………………………… 5
社
版
图 书 在 版 编 目 (CIP)数 据
出
学 图论算法及其 MATLAB 实现/王海英等编著. 北京
:北 京 航 空 航 天 大 学 出 版 社 ,2010.2 ISBN978 7 81124 940 8
大 天
航 Ⅰ.①图… Ⅱ.①王… Ⅲ.①图论算法②计算机辅助 空 计算—软件包,MATLAB Ⅳ.①0157.5②TP391.75
社 本书力求内容丰富,各章 节 相 互 联 系,具 备 指 导 性 书 籍 的 系 统 性、科 学 性、实 用 性 和 引 导
性 ;同 时 ,各 章 又 相 对 独 立 ,自 成 体 系 ,为 读 者 提 供 极 大 方 便 。
版 本书的创新之处在于,每一章均以著名实际 问 题 为 引 入 点,以 图 论 算 法 为 指 导 线,运 用 简 出 单案例达到与 MATLAB 实现的完美结合,真 正 让 各 层 次 的 读 者 学 会 运 用 图 论 理 论 解 决 实 际 学 问 题 ,从 而 培 养 读 者 的 图 论 思 维 ,使 读 者 惊 叹 图 论 方 法 的 美 妙 与 魅 力 。 最 后 还 为 读 者 提 供 了 当
又大大促进了图论和其他学科的发展。
图论算法是计算机科学的核心。 近 几 年,随 着 强 有 力 的 MATLAB 等 数 学 软 件 的 迅 速 发
展 ,图 论 算 法 在 数 学 和 计 算 机 等 各 学 科 方 面 的 应 用 越 来 越 广 泛 ,从 而 使 各 学 科 的 研 究 者 越 来 越
2.12 求最大期望容量路的算法及其 MATLAB 实现 …………………………………… 36 习题二 ………………………………………………………………………………………… 38
第3章 连通图 ………………………………………………………………………………… 40
3.1 判断图的连通性算法及其 MATLAB 实现 …………………………………………… 40 3.2 连通图的中心和加权中心的算法及其 MATLAB 实现 ……………………………… 42 3.3 连通无向图一般中心的算法及其 MATLAB 实现 …………………………………… 44 习题三 ………………………………………………………………………………………… 46
航 中国版本图书馆 CIP 数据核字(2009)第186090号
京
北
图论算法及其 MATLAB 实现 王海英 黄 强 李传涛 褚宝增 编著
责任编辑 宋淑娟
* 北京航空航天大学出版社出版发行
北京市海淀区学院路37号(100191) 发行部电话:(010)82317024 传真:(010)82328026 E-mail:bhpress@ 印刷有限公司印装 各地书店经销 * 开本:787×1092 1/16 印张:10.25 字数:262千字
2.4.2 Dijkstra算法的 MATLAB 实现 ………………………………………………… 16 2.5 求两点间最短路的改进的 Dijkstra算法及其 MATLAB 实现 ……………………… 18
2.5.1 Dijkstra矩阵算法Ⅰ ……………………………………………………………… 18 2.5.2 Dijkstra矩阵算法Ⅱ ……………………………………………………………… 18 2.6 求两点间最短路的 Warshall Floyd算法及其 MATLAB 实现 …………………… 21 2.6.1 Floyd算法的基本思想 …………………………………………………………… 22 2.6.2 Floyd算法的基本步骤 …………………………………………………………… 22 2.6.3 Warshall Floyd算法的 MATLAB 实现 ……………………………………… 22 2.7 求任意两点间最短路的算法及其 MATLAB 实现 …………………………………… 25 2.8 求从一固定点到其他所有点最短路的算法及其 MATLAB 实现 …………………… 27 2.9 求必须通过指定两个点的最短路的算法及其 MATLAB 实现 ……………………… 29 2.10 求图的两顶点间最短路与次短路的算法及其 MATLAB 实现 …………………… 32 2.11 求最大可靠路的算法及其 MATLAB 实现 ………………………………………… 34
多地重视图论算法及其 MATLAB 实现和典型案例,而市场上又缺少这方面的指导性书籍。
本书将图论的基础知识、图论的著名问题以及相应的 MATLAB 程序代码和简单实例完美
地结合在一起,力求语言简洁易懂,问题广泛有趣,算法科学,实例浅显,增强 MATLAB 实现的
技巧性和操作性。读者可以通过简单案例,把图论的重要算法与 MATLAB 编程完美结合。
北 需 求 的 读 者 提 供 更 多 的 指 导 。 十分感谢中国地质大学(北京)2008 年 教 学 研 究 与 教 学 改 革 立 项 的 支 持(项 目 题 目:数 学
知识、数学建模与 MATLAB 等数学软件在实践中相互结合的理论研究)! 感谢北京航空航天
大学出版社的认可、建议和关心! 此外,本文的算法思想均离不开古今中外图论算法研究的完
2010年2月第1版 2010年2月第1次印刷 印数:4000册 ISBN978 7 81124 940 8 定价:24.00元
前言
图 论 算 法 广 泛 应 用 于 物 理 、化 学 、运 筹 学 、计 算 机 科 学 、电 子 学 、信 息 论 、控 制 论 、网 络 理 论 、
管理科学、社会科学等众多学科领域。随着这些 学 科 的 发 展,特 别 是 计 算 机 科 学 的 快 速 发 展,
社 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.1 Dijkstra算法 ……………………………………………………………………… 16
作者会第一时间在 MATLAB 中文论坛勘误,也 会 根 据 读 者 要 求 陆 续 上 传 更 多 案 例 和 相 关 知
识链接,还会随着 MATLAB 版本的升级增 添 必 要 的 内 容 以 满 足 读 者 的 需 求。 希 望 这 本 不 断
“成 长 ”的 书 能 最 大 限 度 地 解 决 读 者 在 学 习 、研 究 、工 作 中 遇 到 的 与 图 论 相 关 的 问 题 。
社 4.3.1 有序二元树………………………………………………………………………… 51