图论及其算法

本 书 融 有 向 图 和 无 向 图 为 一 整 体 ， 系 统 地 阐 述 了 图 论 的 基 本 概 念 、 理 论 、 方 法 及 其 算 法 。 内 容 包 括 图 的 基 本 概 念 、 E r 图 与 Hamilton 图 、 图 论 算 法 、 树 及 其 应 用 、 平 面 图 、 独 立 集 与 匹 配 、 网 络 流 和 Petri 网 书 中 附 有 大 量 例 题 和 习 题 ， 而 大 部 分 习 题 详 细 解 答 。 本 选 材 精 炼 全 面 ， 内 容 处 理 恰 当 且 有 新 意 ， 立 论 严 谨 ， 叙 述 条 理 清 晰 ， 语 言 流 畅图论及其算法殷剑宏吴开亚编著中国科学技术大学出版社2003·合肥内容简介本书融有向图和无向图为一整体,系统地阐述了图论的基本概念、理论方法及其算法。内容包括图的基本概念、uler图与 Hamilton图、图论算法树及其应用、乎面图、独立集与匹配、网络流和 Petri网。书中附有大量例题和习题而且大部分习题有详细解答。本书选材精炼全面内容处理恰当且有新意,立论严谨,叙述条理清晰,语吉流畅。本书可用作膏校计算机、电子、信息、管理、数学等专歇本科生必修课教材,也可供相关专业的研究人员、教帅及图论工作者参考图书在版编目CIP数据图论及其算法殷剑宏,吴开亚编著.一合肥:中国科学技术大学出版社2003.7ISHN731201558-1.图…Ⅱ.①殿…②炅…Ⅲ.①图论卤等学校一教材②图论算湫高等学校一教材.O157.5中国版本图书馆CIP数据核字(2003)第022481号中国科学技术大学出版社出版发行〔安徽省合肥市企察路96号,2326)合肥学苑印务有限公司印制合肥飞天图文艺术设计中心照排全国新华书经州开4:850mm×1168mm/32印张:9,25字数:237千2003年7月第1版203年7月第1次印刷印数:1300册SN7-312-01558-1·270定价:18.00元刚言囡论是一门新兴学科,它发展迅速而又应用广泛。图论已广泛地应用于物理、化学运筹学、计算机科学、电子学、信息论、控制论、网终理论、管理科学、社会科学等几乎所有学科领域。另一方面,随着这些学科的发展,特别是计算机科学的快速发展,又大大地促进了图论的发展。因此,国内外许多高等院校,都把图论列为数学、计箅机、电子、信息、管理等专业的必修专业课程。进入21世纪,国内越来越多的高校,为与国际接轨,拓展学生的知识面,增强学生竞争能力,增设了许多新的课程,同时又大大压缩了各门课程的教学学时,因此,在较少的学时内,如何加强学生对基本概念和基本理论的掌握,如何提痛学生的实际应用能力,是我们高校教堩又面临的一个新课趣。正是针对这种实际情况,参考国内外许多优秀图论著作,结合作者的教学经验,对多年讲授的《图论及其算法》讲稿进行修改,形成了水书。在选林与内容编排等方面,不仅凝聚了作者多年的教学经验和教学体会,而且重点体现了既便于学生学习又利于教师教学的思想由于图论是一较新的学科,所以大多数图论作者在其著作、论文、演讲中都习惯使用自己的一套术语和记号,而且许多图论著作只讨沦有向图,或只讨论无向图,或将有向图与无向图分列讨论本教村则把有向图与无向图融为一个整体,在介绍图论的基本概念、术语和结论时,参考国内外大多数作者的叙述,选择最为诵俗且大众化的语言加以描述,且都以定义的形式加以规范,避免了概念的歧义性,为读者特别是初学者,勾画了清晰的图论轮麻从而能轻松地进入图论的系统学习私研究。本教村充分体现了图论在研究离散量的结构和相互润关系的独到之处。在内容安排上,各章之问既相互联系,其备教树的系统性和科学性,同时各章又相对独立,自成体系,给读者的学习提供了极大方便。另外,在介绍图论基本概念和基本理论的同时,还强调了图论算法,因为算法的研究是计算机科学的核心。因而既能为学生学习后继专业课程打下良好的数学基础,又能增强学生抽象思维能力,启迪学生研究算法的智慧,从而达到培养学生创造力的教学目标。运用图论理论解央实际问题,有着非惴独特与聪明之处。要形成图论思维,巧妙运用图论方法,除了深刻理解概念和理论,除了勤奋和激情,还需要智慧和技巧。为此,本教材每章都橢选了适量例题和习题,书未附有习题解答,同学们在认真做题的过程中,将会惊叹图论方法的聪明和技巧,充分体会图论的美妙与魅力本教村贯彻了教育部有关图论课程教学大纲要求,能在大纲规定的教学学时内,达到图论课程的教学目标。而且,学习本教材,只需要具备线性代数及二元关系的初步知识。作者2003年4月28日目次第一章图的基本概念………(1)第一-节图的概念第二节图的顶点度和图的同构■■■■血■山包■44b鲁卜b画山山■山d■■■h■d血(4第三节图的运算(10)第四节路与连通图(13)第五节连通度和二分图·■凸■d喝(20)第六节图的矩阵表示………………(26)习题■■■日dh■卜昏山▲■■·■■■■■■■·d■b■■■■■··p■d■■■bb■■■■噜■■■■通■看d山(36第二章欧拉图与哈密顿图……(42)第一节欧拉图(43)第二节哙密顿郾1啬【■■啬血■■■L■■■司司■■d………(48)第三节并行运箕困论模型与格雷码…………………(54)第四节算法的时间复杂性日即日日日日↓日日4看↓4·B4bb吾 LkBS甲甲(57)第五节最短路问题…(63)第六节旅行推销员问题和中国投递员问题………(75)习题二↓甲■■■■■■__▲q_(85)第三章树及其应用幽■■■昏斷■甲甲甲甲如语·■■■女■■西▲甲q甲(91)第一节树的基本概念………(91)第二节支撑树的计数4bb甲吗甲甲■b44画郾bb晶■b4甲甲(98)笫三节深度优先搜索与广度优先搜索(l04)第四节最小支撑树…………………………………(109)笫五节前缀码……(116〕第六节二叉查找树与决策树…(121)习题三…(126)第四章平面图………………………(130)第一节平面图…(130)第二节库拉图斯基定理与极大平面图…(134)笫三节图的平面性检测…■如■q甲甲山■q■■■【■■『q■■■【鲁普普第四节平面图的着色(146)第五节图着色的应用(151)笫六节边着色……………………………(156)习颞四(i62)第五章独立集与匹配68第一节独立集(168)第二节独立集的应用(174)第三节支配集……(179)笫四节匹配(l85)第五节最大匹配的生成算法……(192)第六节最优匹配习题五(202第六章网络流和 Petri网…………….(207)第一节网络模型(207)第二节最大流算法…(213第三节 Menger定理………(223)第四节最小费用最大流………………(227)第五节 Petri网简介(233习题……………………(240)附录1符号集…(247)附录2习题解答(250)参考文献………(284)第一章图的基本概念图论中所讨论的“图”,不是徽积分解析几何、几何学中讨论的图形,而是客观世界中某些具体事物间联系的一个数学抽象如元关系的关系图,在关系图中,我们不考虑点的位置及连线的长短曲直,而只关心哪些点之间有线相连这种数学抽象就是“图的概念第一节图的概念定义1图( graph}所谓图G是→个三元组:记作G=((G),F(G),9(G),其中(1)v(G)=v1,v2.…,vn,V(G)≠,称为图G的结点集合( vertex set).(2)E(G)-e1,e2,…,em是G的边集合(eeet),其中为{v,v2}或v,划)若;为{v,v2},称g:为以2和v为端点( end vertices}的无向边( undirected edge};若e;为〈v,vn〉,称e为以v,为起点( origh],t为终点 terminus)的有向边( directed(3)φ(G):E-V×V称为关联函数{ incidence function例1已知图G=〈V(G),E(G),9(G),其中V(G)=v1,2,v3,U4,v576E(G)=e1,e2,e3,e4,5;"6,e7,es,ey,en((:E-V×V,且