资 源 简 介
图论语网络最优化算法是重庆大学 龚劬老师编写的，里面的讲解比较全面。特色的图论书籍,本书的编写力求突出下述特点:1.理论与算法并重。去掉经典专著中那些冗长而晦涩的论证,保留那些简洁、有特色能体现典型数学思想和方法的论证;强调算法的基本思想和计算机实现。2.突出理论与算法的应用,反映本学科的最新应用成果。本书段虞荣教授细心审阅,并提出了许多重要建议,在此表示衷心的感谢。由于作者水平有限,错误、缺陷在所难免,恳请读者指正编者2009年6月教师信息反馈表为了更好地为教师服务,提高教学质量,我社将为您的教学提供电子和网络支持。请您填好以下表格并经系主任签字盖章后寄回,我社将免费向您提供相关的电子教案、网络交流平台或网络化课程资源。书名:版次书号:所需要的教学资料:您的姓名:您所在的校(院)、系:校(院)系您所讲授的课程名称:学生人数:人年级学时:您的联系地址家)邮政编码:联系电话(手机)E-mail:(必填)您对本书的建议:系主任签字盖章请寄:量庆市沙坪坝正街174号重庆大学(A区)量庆大学出版社教材推广部邮编:400030电话023-65112084023-65112085网址:htt://www.cqup.com,cnE-mail:ixk@cup.com.cn第1章图与网络的基本概念“日“·4·日"······卓·1.1绪论●p●单自命■■b自自…………-12一些基本概念睿·■自ψ●聊章血■晶■自■■b■■■D唱鲁■唱■會口■會■31.3图的矩阵表示…4图在计算机中的存储●■●1.5算法及其计算复杂性11习题116第2章树……182.1路径与连通182.2有向图的连通性…自·◆·↓吾··◆··导●■p↓看图的搜索24树及其性质2.5生成树算法●●单命●鲁◆自自·唱自●262.6有向树∴………30习题235第3章连通性383.1连通度■■■■p啁口■bD■p。看口■咖曾383.2割边、割集割点403.3块与块划分423.4可靠网络的设计…………………44习题3■口■鲁即■曾甲咖自p申b即尹◆■46第4章路径算法481最短路径问题·■●■画●■画●自●bb◆申■●自bP●·●最自备■…484.2最短路径问题的一些扩展●■■■……………544.3最优路径……564.4关键路径………………………594.5最短路径算法的应用…鲁●看■罪聊罪■聊看·即看甲甲■申自习题4自郾凸自■■■自●■。■■D看■p晷。鲁罪聊■罪聊罪罪曝即即即■申自●·咖◆鲁p申●■●最72第5章匹配765.1匹配的概念765.2匹配基本定理………………775.3二部图的最大匹配825.4二部图的最大权匹配…855.5一般图的最大匹配…5.6一般图的最大权匹配…………955.7匹配的应用…101习题5…104第6章行遄性问题1086.1欧拉图甲聊聊号章即甲罩……1086.2中国邮递员问题1106.3有向欧拉图6.4中国邮递员问题的应用与推广………1206.5哈米尔顿图命41246.6有向哈米尔顿图1286.7哈米尔顿圈的寻迹1296.8流动推销员问题……………1326.9TSP的近似算法…………1346.10TSP的分枝定界法…1456.11旅行推销员问题的应用…………151习题6@●■鲁………………152第7章平面图1577.1平面图的概念1577.2欧拉公式…………………………………………1587.3平面图的对偶图血會■p『p·。自由看即…15974库拉托夫斯基定理1617.5可平面性算法…16276图的交叉和厚度…………………………167习题7………16第8章图的着色…………1728.1边色数………………1728.2时间表问题1748.3支配集与独立集……17784支配数、覆盖数和独立数的计算18085支配集与独立集的应用1818.6点色数1838.7色多项式…18488色数的应用和算法……………186习题8第9章网络流问题▲日自自如···鲁■看·日●号罪甲·日自;司·······●日甲日日日t1939.1流与截集…1939.2最大流最小截集定理d曲■p自即●■959.3ford和 fulkerson标记法……1964 Digits法…a·apa日中4:·1999.5最大流问题的应用与推广…2039.6最小费用流…2089.7有向图的中国邮递员问题210习题9●自·鲁●1由p●4●212参考文…………………………………215第章图与网络的基本概念1.1绪论自然界与人类社会有许多问题,如果用图形的方式来描述和分析,不仅形象直观,而且清晰,效果很好。图论通过由点和边组成的图形来描述具有某种二元关系的系统,并根据图的性质进行分析,提供研究各种系统的巧妙方法。例如,事物关系、物质结构、电气网络、通信网络城市规划、交通运输信息传递及工作调配等都可用点和边连接起来的图,即图论中的图来模拟。图论中的图有别于解析几何与微积分中的图,在那里,点的位置、边的长度和斜率是它的重要部分,而在图论中,这些都不重要,重要的是点与点之间的连接关系。下面举几个用图论方法建模的典型例子。例1.1七桥问题。18世纪东普鲁士歌尼斯堡被普列格尔河分为4块它们通过7座桥相互连接起来(见图1.1(a)),问能否从某块陆地出发,经每座桥一次而且仗一次,回到出发点?CB(b)图1.11736年,Eler研究这一问题,发表了图论的首篇论文。他把A,B,C,D4块陆地抽象成4个点,而每座桥用连接相应两点的一条线表示,于是得到图1.1(b),A,B,C,D任何一个点作为出发点都必然先“出”后“回”,最后以“出”告终,才能行遍与该点相连的桥,所以不可能回到原来的出发点。此问题用图1.1(b)来表达更简捷、更清晰,更利于问题的解决。图论与网络最优化算法例1.2人狼、羊、菜渡河问题。个摆渡人F希望用一条小船把一只狼W、一头羊G和一篮白菜C从一条河的南岸渡到北岸去,而船小只能容纳F,W,G,C中的两个,决不能在无人看守的情况下,留下狼和羊在起或羊和白菜在一起应怎样渡河才能将狼、羊、白菜都运过去?首先考虑在人狼羊菜渡河的过程中河南岸状态的变化情况,最初的状态是人、狼、羊、菜,最终的状态成空状态,中间的状态为人狼、羊、菜的不同组合。可用小圆圈(顶点)表示河南岸的各个状态,两顶点连线当且仅当两状态经一次摆渡相互转移人、狼、羊、莱的任意不同的组合共有:C+C4+C4+C+C=16,其中狼、羊、菜,狼、羊,羊、菜不允许,从而人,人狼,人菜3种情况也不会出现。余下共有10个允许状态,其状态转移关系如图12所示。O表示空状态。FWGCFWGFWGFGCwC图1.2问题归结为在图中,寻求从顶点“FWGC”到顶点“O”的路线,将图改画为图1.3。FGCFWGCWCFWCFGFG图13易见,共有两种过河方案,它们等优。这一问题用图形来描述,不仅形象直观,而且每一步都非常严密所有可能的摆渡情况都在图中表现出来,符合逻辑思维和分析的规律。问题怎样解,有多少种解法解法是否最优都清楚地呈现出来,使人们对这一问趣的解,有了清晰完整的概念。例1.3化学药品存放问题。某公司生产几种化学药品a,b,C,d,e,,g,其中某些化学药品不相容,为了安全,公司要把不相容的药品放在不同格中,问至少应将仓库划分为多少格可用顶点表示各个化学药品,两顶点连线当且仅当两种药品不相容,便可得一个图C,如图14所示。问题转化为图的正常点着色,图G的点色数便是所求的最少格数。图1.4图的正常点着色即是为每个顶点赋一色,使凡有连线的两顶点异色,点色数即是使图得到正常点着色的最少色数。因此,可把具有相同颜色的顶点代表的药品放在第1章图与网络的基本概念九人A同一格,这样便能使不相容的药品分格放。上面的例子,只是用几个具体问题说明如何用图来描述和分析问题,当然不能勾勒出图论研究问题的全貌,但从中可以看到,这些问题可看做一些事物以及它们之间存在的某种关系,图论就是研究事物以及它们之间联系的一门学科。在许多实例中,事物可用图的顶点表示,它们之间的相互联系可用顶点间的连线,即边表示,这种方法形象直观。任何一个能用二元关系描述的系统,不管它们是数学的、物理的或社会学的等等都可用图论提供数学模型。因此图论模型具有广泛的适用性,如计算机科学、运筹学通信科学、电网络分析、量子物理、结构化学建筑学经济学、语言学生物学社会学遗传学、法律学人类学及定理证明等。1.2一些基本概念1.2.1图的概念定义1.1有序三元组G=(V,E,ψ)称为一个图,其中:①V={v1,v2,…,Un}是有穷非空集,称为顶点集。②E称为边集,其中的元素叫做边。③是从边集E,到v中的有序的或无序的元素偶对的集合的映射,称为关联函数。为了直观,可如下画一个图的图解,把V的元素用不重合的几何点表示,位置随意选择。当(e)=u(或(u,t))时,u与v之间连线,连线可直可曲,表示边e,若是有序偶对(L,y),则还须在上述线上画上箭头指向v例14设G=(V,E,),其V={1,v2,3,4},E={61,e2,e3,e4},v(e1)=v;n2;(E2)=v1v3;(e3)=1"3;y(e)=v1l4v(es)=v33G的图解如图1.5所示。应该指出,通常把图G写成(V,E)或简写成G。图与其图解不是一回事,但它们是同构的。下面可把图解看成就是原来那个图。定义1.2在图G=(V,E)中,与V中的有序偶对应的边E(v(e)=(v1,n2)),称为图G的有向边(或弧),而与V中的顶点的无序偶v1v,相对应的边,称为图G的无向边。每一条边都是无向边的图,称为无向图;每一条边都是有向边的图称为有向图;一些边是无向边,一些边是有向边的图称为混合图。图1.5是一个无向图,图1.6是一个有向图。通常把满足y(e)=w的边e写成e=M图1.5图1.6下面列出一些术语:①若y(e)=,称e与顶点L,相关联。②若ψe)=,称u与t相邻
