目 录 第一章图的基本概念.1 §1.1图和简单图.1 §1.2子图与图的运算.5 S1.3路与图的连通性.10 S14最短路及其算法 §1.5图的代数表示及其特征 .15 51.6极图.20 §1.7交图与团图.26 习题1.29 第二章树.31 §2】树的概念与性质.31 §2.2树的中心与形心.33 §2.3生成树.35 §2.4最小生成树.40 习题2.43 第三章图的连通度.45 §3.1割边，割点和块.46 §3.2连通度.50 §33应用.55 §3.4图的宽距离和宽直径 .58 习题3.65 第四章Euler图与Hamilton图.69 §41Eler图.69 S42高效率计算机鼓轮的设计.71 §4.3中国邮递员问题.73 S4.4 Hamilton图.78 S4.5度极大非Hamilton图.84 S4.6旅行售货员问题.87 §4.7超Hamilton图.89 S4.8E图和H图的联系.94
目录 S4,9无限图中的Euler,Hamilton问题.96 习题4 .97 第五章匹配与因子分解.100 §5.1匹配.100 S5.2偶图的匹配与覆盖.101 §5.3 Tutte定理与完美匹配.104 §5.4因子分解.105 $5.5最优匹配与匈牙利算法 .111 §5.6匹配在矩阵理论中的应用 .116 习题5.117 第六章平面图.119 S6.1平面图119 S6.2一些特殊平面图及平面图的对偶图.127 §6.3平面图的判定及涉及平面性的不变量.134 6.4平面性算法. .138 习题6.143 第七章图的着色.147 §7.1图的边着色.147 §7.2顶点着色.152 7.3与色数有关的几类图.157 §7.4完美图. 163 S7.5着色的计数与色多项式. 166 S7.6Li5t着色.173 §7.7全着色.176 §7.8着色的应用.185 习题7.187 第八章Ramsey定理 .191 S8.1独立集和覆盖 .191 §8.2 Ramsey定理.195 S8.3广义Ramsey数.202 S84应用.205 习题8.206 第九章有向图. 209 S9.1有向图及其连通性. 209 S9.2有向树.217
目录 §93有向路与有向圈 .225 S9.4生成树的计数.232 89.5运输网络与最大流.240 S9.6求最大流的算法及最大流问题的推广.244 $9.7网络流与Menger定理.253 习题9.256 第十章图、群与矩阵 .260 §10.1图的特征值与谱.260 §10.2图的自同构群.267 S10.3图的对称性与强正则图.275 §10.4 Cayley图.281 10.5循环图.286 S10.6 Cayley图的Hamilton性. 291 习题10.295 主要参考文献.298
第一章图的基本概念 历史上，图论曾经被很多数学家各自独立地建立过，因为图论本身就 是应用数学的一部分，所以这种情况并不是偶然的巧合.事实上，最早是 Euler的著作中出现了这样的文字，虽然，他所考虑的原始问题似乎是 个颇为无聊的七桥问题，然而这个问题确实有其深刻的实际背景.后来， Kirechoff对电网络的研究导致他发展了图论的基本概念和关于图中的 树的定理；同时，Cayler则是为了有机化学中的同分异构物的计数问题而 考虑到树.随着Hamilton问题和四色猜想的出现，更大大地推动了图论 的发展。本章介绍图和描述图的局部结构的一些基本概念和术语.这里 的名词和概念较多，但它们都是基本的.此外，我们还要初步介绍完全子 图、极图理论、交图、团图和图的一些有用的运算.这些对以后的讨论是 非常重要的，希望读者能熟练地掌握， §1.1图和简单图 我们所讨论的图(graph)与人们通常所熟悉的图，例如圆、椭圆、函数 图表等是很不相同的.图论中所谓的图是指某类具体事物和这些事物之 间的联系。如果我们用点表示具体事物，用连线表示两个具体事物之间 的联系.那么，一个图就是由一个表示具体事物的点的集合和表示事物 之间联系的一些线的集合所构成 定义1一个图G定义为一个有序对(V,E),记为G=(V,E),其中 (1)V是一个非空集合，称为顶点集或点集，其元素称为顶点或点 V|表示顶点数： (2)E是由V中的点组成的无序点对构成的集合，称为边集，其元素 称为边，且同一点对在E中可出现多次. 图G的顶点集也记为V(G),边集也记为E(G).顶点集和边集都有 限的图称为有限图.只有一个顶点而无边的图称为平凡图.其他所有的 图都称为非平凡图.边集为空的图称为空图.图G的顶点数（或阶数）和 边数可分别用符号n(G)和m(G)表示.连接两个相同顶点的边的条数， 称为边的重数.重数大于1的边称为重边.端点重合为一点的边称为环 既没有环也没有重边的图称为简单图。其他所有的图都称为复合图
第一章图的基本概念 边记为uw,也可记uv为e,即e=um.此时称u和v是e的端点，并称 u和v相邻，u(或)与e相关联.若两条边有一个共同的端点，则称这两 条边相邻.若用小圆点代表点，连线代表边，则可将一个图用“图形”来 表示 一、图的同构 定义2设有两个图G=(V1,E)和G2=(V2,E2),若在其顶点集 合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：设 12,+h,∈V1,2∈V2;w∈E,当且仅当h∈E2,且 山)的重数与的重数相同，则称两图同构，记为G二G2, 例如在图1-1中的G和G2就是同构的， 图1-1 不难证明，图的同构关系是一个等价关系。所有的图的集合，按照同 构关系可划分为一些等价类，以所有等价类为元素构成的集合称为商集， 尽管商集中的元素是一个集合，但这个集合中的任两个图均有相同的结 构，差异只是顶点和边的名称不同.因此在图的图形表示中我们可以不 给图的点和边标上符号，称这样的图为非标定（号）图，否则称为标定（号） 图.非标定图实际上是代表一类相互同构的图。不误解时我们也不严格 区分标定图与非标定图。 二、完全图，偶图，补图 每两个不同的顶点之间都有一条边相连的简单图称为完全图.在同 构意义下，n个顶点的完全图只有一个，记为K,所谓偶图（或二部图）是 指具有二分类(X,Y)的图，它的点集可以分解为两个（非空）子集X和Y, 使得每条边的一个端点在X中，另一个端点在Y中：完全偶图是指具有 二分类(X,Y)的简单偶图，其中X的每个顶点与Y的每个顶点相连.若 |X|=m,|Y|=n,则这样的完全偶图记为Km·图1-2(a)是Ks的图 形，由立方体的顶点和边所确定的图（如图1-2(b)是偶图：图1-2(c)