下载文档原格式
图论与网络流理论（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。
图学基础教程习题集答案第一章：图学基本概念1. 图的定义是什么？答案：图是由顶点（或称为节点）和边组成的数学结构，其中边是顶点之间的连接。
2. 什么是有向图？答案：有向图是一种图，其中的边具有方向性，从一个顶点指向另一个顶点。
第二章：图的表示方法1. 邻接矩阵的优缺点是什么？优点：易于实现，可以快速判断任意两个顶点之间是否存在边。
缺点：空间复杂度高，对于稀疏图来说效率较低。
2. 邻接表的优缺点是什么？优点：空间效率高，对于稀疏图特别适用。
缺点：需要额外的时间来检查两个顶点之间是否存在边。
第三章：图的遍历1. 深度优先搜索（DFS）的基本思想是什么？答案：从图中的一个顶点开始，沿着边尽可能深地搜索，直到无法继续，然后回溯到上一个顶点，继续搜索其他路径。
2. 广度优先搜索（BFS）的基本思想是什么？答案：从图中的一个顶点开始，逐层遍历所有可达的顶点，直到所有顶点都被访问过。
第四章：最小生成树1. 最小生成树问题的定义是什么？答案：在无向图中，最小生成树是一棵连接所有顶点的树，且边的总权重最小。
2. Kruskal算法的基本步骤是什么？答案：Kruskal算法通过按权重递增的顺序选择边，确保选择的边不会形成环，直到所有顶点都被连接。
第五章：最短路径问题1. Dijkstra算法的工作原理是什么？答案：Dijkstra算法通过维护一个优先队列，不断地选择距离起点最近的顶点，并更新其邻接顶点的距离。
2. Bellman-Ford算法与Dijkstra算法的主要区别是什么？答案：Bellman-Ford算法可以处理带有负权重边的图，而Dijkstra算法不能。
第六章：图的着色1. 图的着色问题的定义是什么？答案：图的着色问题是指给图中的每个顶点分配一种颜色，使得相邻的顶点颜色不同。
2. 贪心算法在图的着色问题中的应用是什么？答案：贪心算法在图的着色问题中，从顶点集合中选择一个顶点，为其分配一种颜色，然后移动到下一个顶点，并为其分配一种与相邻顶点不同的颜色。
《图论》程序设计目录第一章图的基本概念 2一、图的的定义 2二、图的存储结构 3 第二章图的遍历 5一、深度优先搜索 6二、广度优先搜索8 例、子图划分12 第二章图的生成树14 一、基本概念14 排列方案15 二、图的最小生成树(prim算法) 16 例、机器蛇18 第三章、最短路问题20一、计算单源最短路问题（Dijkstra算法）20二、任意两点间的最短路（floyd算法）23三、最短路径的应用25 例、颜色集28 例计算DAG中的最长路30 例、计算带权有向图的中心31 第四章应用举例32 例、位图32 【例题】士兵排队34 简化图36如果数据元素集合D 中的各元素之间存在任意的前后件关系R ，则此数据结构G=（D ，R ）称为图。
奥林匹克信息学联赛的许多试题，需要用图来描述数据元素间的联系，需要用图的经典算法来解题用结点代表城市，每条边代表连接两个城市间的公路，边长的权表示公路长度。
这种公路网的表现形式就是属于图的数据结构。
第一章 图的基本概念一、图的的定义如果数据元素集合D 中的各元素之间存在任意的前后件关系R ，则此数据结构G=（D ，R ）称为图。
如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为G=（V ，E ），其中V 是结点的有穷（非空）集合，E 为边的集合。
如果元素a 是元素b 的前件，这种前后件关系对应的边用(a ，b)表示，即(a ，b)∈E 。
1、无向图和有向图⑴无向图：在图G=（V ，E ）中，如果对于任意的a ，b∈V，当(a ，b)∈E 时，必有（b ，a ）∈E（即关系R 对称），对称此图为无向图。
在一无向图中用不带箭头的边连接两个有关联的结点。
在具有n 个结点的无向图中，边的最大数目为n*(n+1)/2。
而边数达到最大值的图称为无向完全图。
在无向图中一个结点相连的边数称为该结点的度，无向完全图中，每一个顶点的度为n-1。
⑵有向图：如果对于任意的a ，b∈V，当(a ，b)∈E 时 ，(b ，a)∈E 未必成立，则称此图为有向图。
什么是图的基本概念和特征图是一种数学结构，用于表示多个对象之间的关系。
图由节点（vertex）和边（edge）组成，节点表示对象，边表示节点之间的关系。
图的基本概念和特征包括节点的度、路径、连通性、连通分量等。
1. 节点的度：节点的度是指与该节点相连的边的数量。
对于有向图来说，节点的度分为入度和出度，分别表示指向该节点的边的数量和由该节点指出的边的数量。
节点的度可以用来描述节点的重要性和连接的紧密程度。
2. 路径：路径是指由边连接的一系列节点的序列。
路径的长度是指路径中包含的边的数量。
最短路径是指连接两个节点之间具有最少边数的路径。
路径可以用来描述节点之间的关系和节点之间的可达性。
3. 连通性：图的连通性表示图中任意两个节点之间是否存在路径。
如果图中任意两个节点之间都存在路径，那么图被称为连通图；如果存在某些节点之间不存在路径，那么图被称为非连通图。
连通性可以用来描述图的整体连接情况。
4. 连通分量：连通分量是指图中的最大连通子图。
一个连通分量包含一组相互可达的节点，并且在该连通分量内部的任意两个节点之间都存在路径，而与该连通分量外的节点之间不存在路径。
图可以由多个连通分量组成。
图有以下几种常见的特征：1. 有向图和无向图：根据边的有向性，图可以分为有向图和无向图。
在无向图中，边没有方向，表示节点之间的双向关系；而在有向图中，边有方向，表示节点之间的单向关系。
2. 权重：图的边可以带有权重，用来表示节点之间的距离、成本等。
带权重的图被称为带权图，而不带权重的图被称为无权图。
3. 稀疏图和稠密图：如果图中的边数接近节点数的平方，那么图被称为稠密图；如果图中的边数相对较少，那么图被称为稀疏图。
稠密图和稀疏图在算法设计和空间复杂度上有不同的考虑。
4. 循环和非循环图：如果图中存在一个节点可以通过一系列边回到自身，那么图被称为循环图；如果图中不存在这样的节点，那么图被称为非循环图（也称为无环图）。
5. 连通图和非连通图：根据连通性，图可以分为连通图和非连通图。
电⼦科技⼤学《图论及其应⽤》复习总结--第⼀章图的基本概念⼀、重要概念图、简单图、图的同构、度序列与图序列、偶图、补图与⾃补图、两个图的联图、两个图的积图1.1 图⼀个图G定义为⼀个有序对(V, E)，记为G = (V, E)，其中（1）V是⼀个有限⾮空集合，称为顶点集或边集，其元素称为顶点或点；（2）E是由V中的点组成的⽆序点对构成的集合，称为边集，其元素称为边，且同⼀点对在E中可出现多次。
注：图G的顶点数（或阶数）和边数可分别⽤符号n(G) 和m(G)表⽰。
连接两个相同顶点的边的条数，叫做边的重数。
重数⼤于1的边称为重边。
端点重合为⼀点的边称为环。
1.2 简单图⽆环⽆重边的图称为简单图。
（除此之外全部都是复合图）注： 1.顶点集和边集都有限的图称为有限图。
只有⼀个顶点⽽⽆边的图称为平凡图。
其他所有的图都称为⾮平凡图。
边集为空的图称为空图。
2.n阶图：顶点数为n的图，称为n阶图。
3.(n, m) 图：顶点数为n的图，边数为m的图称为(n, m) 图1.3 邻接与关联：顶点u与v相邻接：顶点u与v间有边相连接(u adj v)；其中u与v称为该边的两个端点。
注：1.规定⼀个顶点与⾃⾝是邻接的。
2.顶点u与边e相关联：顶点u是边e的端点。
3.边e1与边e2相邻接：边e1与边e2有公共端点。
1.4 图的同构设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：u1,v1∈V1,u2,v2∈ V2 ，设u1↔u2，v1↔v2,; u1v1∈E1 当且仅当u2v2∈E2,且u1v1与u2v2的重数相同。
称G1与G2同构，记为：G1≌G2注：1、图同构的两个必要条件： (1) 顶点数相同；(2) 边数相同。
2、⾃⼰空间的理解：通过空间的旋转折叠可以进⾏形态转换1.5 完全图、偶图1、在图论中，完全图是⼀个简单图，且任意⼀个顶点都与其它每个顶点有且只有⼀条边相连接。
