下载文档原格式
第一章 图形理论图形理论有明确的起始点，由瑞士数学家尤拉(Leonhard Euler, 1707-1783)于1736年发表的论文开始。
其研究的主要论点，乃在于解决当时的热门问题，即有名K önigsgerg 的七桥问题。
1.1 定义与例题定义1.1：令 V 为非空集合，且E V V ⊆⨯. 序对(),V E 称为(V 上)有向图(directedgraph or digraph)，其中 V 为顶点(vertex)或节点(node)的集合，E 为边(edge)的集合。
我们记(),G V E =表示此图形。
图1.1为{}, , , , V a b c d e =上有向图的例子，其中()()()(){}, , , , , , , E a a a b a d b c =。
边的方向由边上的有向箭头表示，如图所示对任意边，如(), b c ，我们说此边接合(incident)顶点, b c ；称b 邻接至(adjacent to) c ；或c 邻接自(adjacent from) b 。
此外， b 称为边的原点(origin)或源点(source)， c 称为终点(terminus or terminating vertex)。
边(), a a 为一个循环(loop)， 且顶点e 不与任何边接合，称为孤立点(isolated)。
若不考虑边的方向，此图称为无向图(undirected)。
定义1.2：令, x y 为无向图(), G V E =的顶点(不一定相异)。
G 中的X Y -路(x y -walk)是指选自G 的顶点及边的有限交错序列。
01122311,,,,,,...,,,,n n n n x x e x e x e e x e x y --==其中由顶点 1x 开始，终止于顶点y ，n 个边{}1,,1i i i e x x i n -=≤≤路的长度(length)是指该条路的边数n 。
图论与网络流理论（Graph Theory and Network Flow Theory）高随祥中科院研究生院专业基础课学时/学分：60/3本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。
主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。
为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。
内容提要第一章 图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。
路、圈与连通图；最短路问题。
树及其基本性质；生成树；最小生成树。
第二章 图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。
第三章 匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。
第四章 欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。
第五章 支配集、独立集、覆盖集与团支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
第六章图的着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。
第七章网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。
主要参考书[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。
[2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。
[3] 蒋长浩，图论与网络流，中国林业出版社，2001。
