图论与网络流理论

《图论与网络流理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论与网络流理论图论与网络流理论（GraphTheoryandNetworkFlowTheory）讲授：高随祥中科院研究生院专业基础课学时/学分：60/3　　本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。为学习者将来从事有关方面的理论研究打

2、下基础，也为进行应用性研究提供一种有力的工具。内容提要第一章图的基本概念　　图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。　　路、圈与连通图；最短路问题。树及其基本性质；生成树；最小生成树。第二章图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。第三章匹配问题　　匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。第四章欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。第五章支配集、独立集、覆盖集与团　支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。第六章图的

3、着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。第七章网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。主要参考书[1]J.A.BondyandU.S.Murty,Graphtheorywithapplications,1976,有中译本（吴望名等译）。[2]B.Bollobas,Moderngraphtheory(现代图论)，科学出版社，2001。[3]蒋长浩，图论与网络流，中国林业出版社，2001。[4]田丰，马仲蕃，图与网络流理论，科学出版社，198

4、7。[5]徐俊明，图论及其应用，中国科技大学出版社，1998。[6]王树禾，图论及其算法，中国科技大学出版社，1994。[7]殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。考核方式：平时成绩＋期末闭卷笔试　　　　　　第一章图的基本概念§1.1图的基本概念1.图(graph)：一集元素及它们之间的某种关系。具体地说，图是一个二元组，其中集合V称为顶点集，集合E是的一个子集（无序对，元素可重复），称为边集。例1.1.1，其中，。这便定义出一个图。2.图的图示　　通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。

5、这样画出的平面图形称为图的图示。例如，例1.1.1中图的一个图示为注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。比如下图是例1.1中图的另一个图示：（2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。3.一些概念和术语（1）点与边的关联(incident)（2）点与点的相邻（adjacent）（3）边与边的相邻（4）边的端点（endvertices）（5）环边(loop)（6）重边(multiedge)（7）简单图(simplegraph)（8）完全图(completegraph)（9）

6、图的顶点数（图的阶）、边数（10）顶点v的度(degree)：d(v)=顶点v所关联的边的数目（环边计两次）。（11）图G的最大度：图G的最小度：（12）正则图(regulargraph)：每个顶点的度都相等的图。（13）图的补图(complement)：设G是一个图，以为顶点集，以为边集的图称为G的补图，记为。定理1.1.1证明：按每个顶点的度来计数边，每条边恰数了两次。推论1.1.1任何图中，奇度顶点的个数总是偶数（包括0）。4.子图子图(subgraph)：如果且，则称图H是G的子图，记为。生成子图(spanningsubgraph):若H是G

7、的子图且，则称H是G的生成子图。点导出子图(inducedsubgraph)：设，以为顶点集，以两端点均在中的边的全体为边集所组成的子图，称为G的由顶点集导出的子图，简称为G的点导出子图，记为.边导出子图(edge-inducedsubgraph)：设，以为顶点集，以两端点均在中的边的全体为边集所组成的子图，称为G的由边集导出的子图，简称为G的边导出子图，记为.5.路和圈途径(walk)：图G中一个点边交替出现的序列。迹(trail)：边不重的途径。路(path):顶点不重复的迹。（注：简单图中的路可以完全用顶点来表示，）闭途径（closedwalk

8、）：起点和终点相同的途径。闭迹(closedtrail)：起点和终点相同的迹，也称为回路（circuit）.