资源描述：
《图论讲义第1章-图的概念new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论与网络流理论（GraphTheoryandNetworkFlowTheory）高随祥中科院研究生院专业基础课学时/学分：60/3本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。为学习者将来从事有
2、关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。1内容提要第一章图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。路、圈与连通图；最短路问题。树及其基本性质；生成树；最小生成树。第二章图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。第三章匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。第四章欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。第五章支配集、独立集、覆盖集与团支配集、点独立集
3、、点覆盖集、边覆盖集与团的概念及其求法。第六章图的着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。第七章网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。主要参考书[1]J.A.BondyandU.S.Murty,Graphtheorywithapplications,1976,有中译本（吴望名等译）。[2]B.Bollobas,Moderngraphtheory(现代图论)，科学出版社，2001。[3]蒋长浩，
4、图论与网络流，中国林业出版社，2001。[4]田丰，马仲蕃，图与网络流理论，科学出版社，1987。[5]徐俊明，图论及其应用，中国科技大学出版社，1998。[6]王树禾，图论及其算法，中国科技大学出版社，1994。[7]殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。考核方式：平时成绩＋期末闭卷笔试2第一章图的基本概念§1.1图的基本概念1.图(graph)：一集元素及它们之间的某种关系。具体地说，图是一个二元组(V,E)，其中集合V称为顶点集，集合E是V中元素组成的某些无序对的集合，称为边集。
5、例1.1.1G=(V,E)，其中V={v,v,v,v,v}，E={(v,v),(v,v),(v,v),(v,v),(v,v),(v,v),(v,v)}。1234512233435151555这便定义出一个图。图的顶点集中的元素称为顶点，边集中的元素称为边。在本书中边e=(u,v)也常写为e=uv，顶点u和v称为边e的端点，反过来也称边e连接顶点u和v。图G的顶点数目
6、
7、V称为图G的阶，边的数目
8、
9、E称为图G的边数。本书中一般将图的边数记为ε，将图的阶记为υ。2.图的图示通常，图的顶点可用平面上的一个点来表示
10、，边可用平面上的线段来表示（直的或曲的）。这样画出的平面图形称为图的图示。例如，例1.1.1中图的一个图示为v1e1e6v2e5e2e4e7v5v3e3v4注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。比如下图是例1.1.1中图的另一个图示：v1e6ev54e1v5e3e4e7v3e2v2（2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。3.一些术语和概念设G=(V,E)是一个图，下述概念中顶点均取自V，边均取自E。（1）点与边的关联(inc
11、ident)：如果在图G中点v是边e的一个端点，则称点v与边e在图G中相关联。（2）点与点的相邻(adjacent)：如果图上两点u,v被同一条边相连，则称u,v在图G中相3邻。（3）边与边的相邻：如果图G中两条边有至少一个公共端点，则称这两条边在图G中相邻。（4）环边(loop)：图中两端点重合的边称为环边。（5）重边(multiedge)：设u和v是图G的顶点，图G中连接u和v的两条或两条以上的边称为图G中u、v间的重边。（6）简单图(simplegraph)：既无环边也无重边的图称为简单图。（7）完全
12、图(completegraph)：任意两点间都有一条边的简单图称为完全图，n阶完全图记为Kn.（8）平凡图(trivialgraph):只有一个顶点，没有边的图。（9）空图(emptygraph):边集为空的图。（10）零图(nullgraph):顶点集为空的图。（11）顶点v的度(degree)：图G中顶点v所关联的边的数目（环边计两次）称为顶点v的度，记为dG(v)或d(v)。（12）图G的最大度：Δ(G)=
