下载文档原格式
目录第一章图的基本概念 (1)二路和连通性 (3)第二章树 (3)第三章图的连通度 (4)第四章欧拉图与哈密尔顿图 (5)一，欧拉图 (5)二．哈密尔顿图 (6)第五章匹配与因子分解 (9)一．匹配 (9)二．偶图的覆盖于匹配 (10)三．因子分解 (11)第六章平面图 (14)二．对偶图 (16)三．平面图的判定 (17)四．平面性算法 (20)第七章图的着色 (24)一．边着色 (24)二．顶点着色 (25)第九章有向图 (30)二有向树 (30)第一章图的基本概念1.点集与边集均为有限集合的图称为有限图。
2.只有一个顶点而无边的图称为平凡图。
3.边集为空的图称为空图。
4.既没有环也没有重边的图称为简单图。
5.其他所有的图都称为复合图。
6.具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。
7.完全偶图：是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n8. 定理1 若n 阶图G 是自补的（即），则n = 0, 1（mod 4）9. 图G 的顶点的最小度。
10. 图G 的顶点的最大度。
11. k-正则图: 每个点的度均为 k 的简单图。
例如,完全图和完全偶图Kn,n 均是正则图。
12. 推论1 任意图中，奇点的个数为偶数。
13.14. 频序列：定理4 一个简单图G 的n 个点的度数不能互不相同。
15. 定理5 一个n 阶图G 相和它的补图有相同的频序列。
16.17.18. 对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1)19. 定义： 联图 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G220. 积图：积图 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u =(u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G 称为G1和G2积图。
图论基本知识对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。
我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。
图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。
图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。
考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。
进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。
本章只给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。
个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。
对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。
图的基本概念图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。
集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。
若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。
根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。
如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。
以后如果没有特殊的说明，所有出现的图都是简单图。
记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。
图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。
几何中的立体图形基本概念一、立体图形的定义与分类1.定义：立体图形是三维空间中的图形，具有长度、宽度和高度。
a)立体几何图形的分类：锥体、柱体、球体、平面立体图形等。
b)根据表面特征分类：直纹立体图形、曲面立体图形等。
二、常见立体图形的基本性质与特征a)定义：底面为平面，顶点在底面上的图形。
i)圆锥：底面为圆，侧面为曲面。
ii)棱锥：底面为多边形，侧面为三角形。
iii)所有锥体的侧面积相等。
iv)锥体的体积与底面半径和高度有关。
b)定义：底面为平行四边形的立体图形。
c)分类：棱柱、圆柱等。
i)柱体的底面积相等。
ii)柱体的体积与底面积和高度有关。
d)定义：所有点与中心点距离相等的立体图形。
πR³。
i)球体的表面积和体积公式为：S=4πR²，V=43ii)球体的直径等于两倍的半径。
4.平面立体图形：a)定义：由平面图形旋转而成的立体图形。
b)分类：圆柱、圆锥、棱柱等。
c)性质：平面立体图形的表面积和体积与平面图形的性质有关。
三、立体图形的计算方法a)圆锥体积公式：V=1πR²h。
3b)棱锥体积公式：V=13Bh ，其中B 为底面积。
c)棱柱体积公式：V=Bh ，其中B 为底面积。
d)圆柱体积公式：V=πR²h 。
e)体积公式：V=43πR³。
f) 表面积公式：S=4πR²。
四、立体图形的实际应用a)应用：漏斗、沙堆等。
b)应用：柱子、烟囱等。
c)应用：球体、地球等。
4. 平面立体图形：a) 应用：各种容器、家具等。
通过以上知识点的学习，学生可以对几何中的立体图形有更深入的了解，并能够运用所学知识解决实际问题。
习题及方法：1.习题：计算一个底面半径为3cm ，高为4cm 的圆锥体的体积。
答案：V=13πR²h=13π×3²×4=12πcm³解题思路：根据圆锥体的体积公式V=13πR²h ，将给定的数值代入公式计算。
图论与网络流理论（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．图的定义：由若干个不同的顶点与连接其中某些顶点的边所组成的图形叫做图。
用G 表示图，用V 表示所有顶点的集合，E 表示所有边的集合，并且记作G=（V ，E ）． 2．同构图：如果两个图G 与G '‘的顶点之间可以建立起一一对应，并且当且仅当G 的顶点v i 与v j 之间有k 条边相连时，G ’的相应顶点j i v v ''与之间也有k 条边相连，就认为G 与G '是相同的，称G 与G '是同构的图． 2．子图：如果对图G E E ,V V )E ,V (G )E ,V (G '⊆'⊆'''='=，则称有与是G 的子图．3．其它有关概念：（1）若在一个图G 中的两个顶点j i v v 与之间有边e 相连，则称点j i v v 与是相邻的，否则就称j i v v 与是不相邻的．（2）如果顶点v 是边e 的一个端点，称点v 与边e 是相邻的．（3）如果顶点本身也有边相连，这样的边称为环．如果连接两个顶点的边可能不止一条，若两个顶点之间有k )2k (≥条边相连，则称这些边为平行边．（4）如果一个图没有环，并且没有平行边，这样的图称为简单图．竞赛中的图论问题涉及到的图一般都是简单图．（5）如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n 个顶点的完全图记为n K ．（6）在图G=(V,E)中，顶点个数|V|和边数|E|都是有限的，则称图G 是有限图；如果|V|或|E|是无限的，则称G 为无限图．1v 2v 4v 3v 1v '2v '3'4v '1v ''2v ''3v ''4v ''1G 2G 3G二．例题精选1．设S 为平面上的一个有限点集（含点数不少于5），若其中若干个点涂红色，其余点涂上兰色，又设任何三个同色点不共线，求证：存在一个同色三角形，且它至少有一条边不含另一种颜色． 证明：无穷递降法2．若平面上有997个点，如果两点连成一条线段，且中点涂成红色，证明：平面上至少有1991个红点，试找到正好是1991个红点的特例．证明：设997个点中M 、N 之间的距离最大，以M 、N 为圆心，2MN为半径作圆，如图，设P 为其它995 个点中的任意一个点，则PM 、PN 的中点R 、Q 都在圆M 、 N 内，且这些点个不相同，所以至少有995×2+1=1991个点．特例：在x 轴上横坐标依次为1，2，3，．．．，997的997个点，满足题设条件．3．正六边形被分为24个全等的三角形，在图中的19个结点处写上不同的数，证明：在24个三角形中，至少有7个三角形，其顶点处的三个数是按逆时针方向递增顺序书写的．证明：（１）正六边形的12（2）一个逆三角形有2条逆边，一个顺三角形有1条逆边；（3）除掉正六边形的边，图中有（24×3-12）÷2=30条边，没条边恰好是一个三角形的一条逆向边．综上，设24个三角形中有m 个逆三角形，n 个顺三角形，则有731224≥⇒⎪⎩⎪⎨⎧≥+=+m n m n m ，得证．RRRBBBMNPR QE 逆三角形顺三角形1231234．在正n 边形中，要求其每条边及每条对角线都染上任一种颜色，使得这些线段中任意两条有公共点的染不同颜色，为此，至少需要多少种颜色？的n 需要n 种颜色．当n=3 当n>3时，作正n 设MN 是另外一条边或对角线，若MN//BC ，则将MN 染成与BC 同色；若BC MN //，过A 引直线直线m//MN ，交圆于K ，则弧KN=弧AM ，所以K 也是正n 边形的顶点，即AK 是由A 出发的边或对角线，将MN 染成与AK 同色，所以n 种颜色足够了．5．某次大型活动有2003人参加，已知他们每个人都至少和其中的一个人握过手，证明：必有一个人至少和其中的两个人握过手． 证明：从5个点开始考虑奇数个点即可． 如图6．现有九个人，已知任意三人中总有两个人互相认识，证明：必有四人互相之间都认识． 证明：9个顶点的简单图，利用抽屉原理7．有n 名选手n 21A ,,A ,A 参加数学竞赛，其中有些选手是互相认识的，而且任何两个不相识的选手都恰好有两个共同的熟人，若已知选手21AA 与是互相认识，但他们没有共同的熟人，证明他们的熟人一样多．M NE P Q∙R∙1A 2A 3A 4A 5A KMNA1A 2A )(2A n )(1A n iA jA 1A 2A )(2A n )(1A n iA jA 'jA 'i A证明：的熟人一一对应与21A A8．有n （n>3）个人，他们之间有些人互相认识，有些人互相不认识，而且至少有一个人没有与其他人都认识，问与其他人都认识的人数的最大值是多少？解：作图G ：用n 个点表示这n 个人，当两人认识，则在两相应顶点之间连一线，否则之间不连线．由于至少有一个人与其他人不认识，所以图G 中至少有两点之间没连线，设21A A 与之间没连线，则图G 的边数最多时，G 为21A A K n -，故最大值为n-2．9．次会议有n 名教授n 21A ,A ,A 参加，证明可以将这n 个人分为两组，使得每一个人A i 在另一组中认识的人数不少于他在同一组中认识的人数．证明：用n 个点n A A A ,,,21 表示这n 名教授，并在相互认识的人之间连一条边，且将同一组间的连线染成红色，不同组之间的线染成蓝色．将这n 个点任意分成两组，只有有限种分法．考虑在两组之间的蓝线条数S ，其中必存在一种分法，使S 达到最大值，此时有i A 在两组内引出的边的条数分别为),,2,1,(,n i l l l l i i i i ='≥'，否则，若对i A 有'<i i l l ，将i A 调到另一组，S 增加了i i l l -'条，矛盾，得证．10．有三所中学，每所有学生n 名，每名学生都认识其他两所中学的n+1名学生，证明：从每所中学可以选出一名学生，使选出来的3名学生互相认识．证：用3n 个顶点表示这些学生，三所中学的学生组成的三个顶点集合分别记为A 、B 、C ，设M 和N 是两所不同学校的学生，而且是互相认识的，则在M 与N 之间连一线，得一个简单图．记A 中的元素x 在B 、C 中的相邻元素个数为k 和l ，则k+l =n+1．设k 与l 中大的记作m(x)，让x 跑遍A ，m(x)的最大值记作A m ，同理记C B m m ,分别为集合B 、C 中的所有元素在另两个集合中相邻元素个数的最大值．记m 是A m ，C B m m ,中最大者，不妨设m=A m ，且的顶点相邻的顶点集和中和使得100,B x B A x ∈数为m ，于是C 中与00,11x C z m n x 与设相邻的顶点数为∈≥-+相邻．如果有中中的一个三角形．若是相邻，则与1000010B G z y x z B y ∆∈每一个y 与中相邻与．因此，相邻的顶点数与都不相邻，则A z m n z B z 000-≤的顶点数1)(1+=--+≥m m n n 与m 的最大性矛盾，得证．三．巩固练习1．有n 个药箱，每个药箱里有一种相同的药，每种药恰好在两个药箱里出现，问有多少种药？)1(21-n n 2．18个队进行比赛，每一轮中每一个队与另一个队比赛一场，并且在其他轮比赛中这两个已赛过的队彼此不再比赛，现在比赛已进行完8轮，证明一定有三个队在前8轮比赛中，彼此之间尚未比赛过．3．某次会议有n 名代表出席，已知任意的四名代表中都有一个人与其余的三个人握过手，证明任意的四名代表中必有一个人与其余的n-1名代表都握过手．4．空间１８个点，任三点不共线，它们的两两连线染上红色或兰色，每条线段仅染一色．试证明其中一定存在一个同色的完全四边形．图论问题（二）用图论解决问题躲基本思路：把要考察的对象作为顶点，把对象之间是否具有我们所关注的某种关系作为顶点连边地条件．这样，就可以把一个具体问题化归成图论问题，用图论的理论和方法进行探讨，即使在图论中没有现成定理直接给出问题的解答，也可以（1）借助图论的分析方法拓宽解题思路；（2）把抽象的问题化为直观问题；（3）把复杂的逻辑关系问题化为简明的数量分析问题。
