第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中u , v 两点是其割点。 定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。 证明留作习题。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。
第三章 匹配理论 §3.1 匹配与最大匹配 定义3.1.1 设G 是一个图, )(G E M ?，满足:对i e ?,M e j ∈，i e 与j e 在G 中不相邻，则称M 是G 的一个匹配。对匹配M 中每条边uv e =，其两端点 u 和 v 称为被匹配M 所匹配，而 u 和 v 都称为是M 饱和的(saturated vertex )。 注:每个顶点要么未被M 饱和, 要么仅被M 中一条边饱和。 定义3.1.2 设M 是G 的一个匹配, 若G 中无匹配M ′, 使得||||M M >′, 则称M 是G 的一个最大匹配；如果G 中每个点都是M 饱和的, 则称M 是G 的完美匹配(Perfect matching ). 显然, 完美匹配必是最大匹配。 例如，在下图G 1中，边集{e 1}、{e 1,e 2}、{e 1,e 2,e 3}都构成匹配，{e 1,e 2,e 3}是G 1的一个最大匹配。在 G 2中，边集{e 1,e 2,e 3,e 4}是一个完美匹配，也是一个最大匹配。 定义3.1.3 设M 是G 的一个匹配, G 的M 交错路是指其边M 和M G E \)(中交替出现的路。如果G 的一条M 交错路(alternating path)的起点和终点都是M 非饱和的，则称其为一条M 可扩展路或M 增广路(augmenting path)。 定理 3.1.1(Berge,1957) 图G 的匹配M 是最大匹配的充要条件是G 中不存在M 可扩展路。 证明:必要性:设M 是G 的一个最大匹配。如果G 中存在一个M 可扩展路P ,则将P 上所有不属于M 的边构成集合M ′。显然M ′也是G 的一个匹配且比M 多一条边。这与M 是最大匹配相矛盾。 充分性:设G 中不存在M 可扩展路。若匹配M 不是最大匹配，则存在另一匹配M ′,使 ||||M M >′. 令 ][M M G H ′⊕=，(M M M M M M ′?′=′⊕∩∪称为对称差)。 则H 中每个顶点的度非1即2(这是因为一个顶点最多只与M 的一条边及M ′的一条边相关联)。故H 的每个连通分支要么是M 的边与M ′的边交替出现的一个偶长度圈，要么是M 的边与M ′的边交替出现的一条路。 由于||||M M >′，H 的边中M ′的边多于M 的边，故必有H 的某个连通分支是一条路，且始于M ′的边又终止于M ′的边。这条路是一条M 可扩展路。这与条件矛盾。 证毕。
数学竞赛：图论讲义 大连市第二十四中学 邰海峰 重要的概念与定理 完全图 每两个顶点之间均有边相连的简单图称为完全图,有n 个顶点的完全图(n 阶完全图)记为n K . 顶点的度 图G 中与顶点v 相关联的边数(环按2条边计算)称为顶点v 的度(或次数),记为()d v .()G δ与()G ?分别表示图G 的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为偶数的顶点称为偶顶点. 树 没有圈的连通图称为树,用T 表示,其中度为1的顶点称为树叶(或悬挂点).n 阶树常表示为n T . k 部图 若图G 的顶点集V 可以分解为k 个两两不相交的非空子集的并,即 1,()k i i j i V V V V i j == =?≠ 并且同一子集i V (1,2,,)i k =内任何两个顶点没有边相连,则称这样的图为k 部图,记作12(,,,;)k G V V V E =. 2部图又叫做偶图,记为(,;)G X Y E =. 完全k 部图 在一个k 部图12(,,,;)k G V V V E =中,i i V m =(1,2,,)i k =,若对任意 ,,(,,1,2,,)i i j j v V v V i j i j k ∈∈≠=均有边连接i v 和j v ,则称图G 为完全k 部图,记为12,,,k m m m K . 欧拉迹 包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹. 欧拉图 包含欧拉迹的图为欧拉图. 欧拉图必是连通图. 哈密顿链(圈) 经过图上各顶点一次并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密顿圈的图称为哈密顿图. 平面图 若一个图G 可画在平面上,即可作一个与G 同构的图G ',使G '的顶点与边在同一平面内,且任意两边仅在端点相交,则图G 称为平面图. 一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面. 竞赛图 有向完全简单图称为竞赛图.有n 个顶点的竞赛图记作n K . 有向路 在有向图(,)D V U =中,一个由不同的弧组成的序列12,,,n u u u ,其中i u 的起点为i v ,终点为1(1,2,,)i v i n +=,称这个序列为从1v 到1n v +的有向路(简称路),n 为这个路的长,1v 为
第八章独立集和团 §8.1 独立集 °独立集：设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则称S为G的一个独立集。 °最大独立集：G的一个独立集S称为G的最大独立集，是说：G不包含适合S′>S的独立集S′。 °例子：(见图8.1) °覆盖：G的一个覆盖是指V的子集K，使得G的每条边都至少有一个端点属于K。 °例子：在图8.1中，两个独立集都是覆盖的补集。 定理8.1：设S?V，则S是G的独立集当且仅当V\S是G的覆盖。证：按定义，S是G的独立集当且仅当G中每条边的两个端点都不同时属于S，即当且仅当G的每条边至少有一个端点属于V\S，亦即当且仅当V\S是G的覆盖。? °独立数：G的最大独立集的顶点数称为G的独立数，记为α(G)。°覆盖数：G的最小覆盖的顶点数称为G的覆盖数，记为β(G)。 推论8.1：α+β=υ。 证：设S是G的一个最大独立集，K是G的一个最小覆盖。由定理8.1，V\K是独立集，而V\S是覆盖。因此 υ?β=V\K≤α (8.1) υ?α=V\S≥β (8.2)
结合8.1式和(8.2)式，即得α+β=υ。? °边覆盖：G的一个边覆盖是指E的一个子集L，使得G的每个顶点都是L中某条边的端点。 °边独立集：即对集。 *注意：边覆盖并不总是存在的，G有边覆盖，当且仅当δ>0。 °边独立数和边覆盖数：最大对集的边数称为边独立数，记作α′G;最小边覆盖的边数称为边覆盖数，记作β′(G)。 *注意：对集的补集不一定是边覆盖，边覆盖的补集也不一定是对集。定理8.2 (Gallai)：若δ>0,则α′+β′=υ。 证：设M是G的一个最大对集，U是M非饱和顶点集。由于δ>0且M是最大对集，所以存在|U|条边的一个集E′，它的每条边都和U 的每个顶点相关联。显然，M∪E′是G的边覆盖，因而 β′≤M∪E′=α′+υ?2α′=υ?α′ 即α′+β′≤υ (8.3) 再设L是G的一个最小边覆盖，置H=G[L]，并且设M是H的一个最大对集。用U记H中的M非饱和顶点集。由于M是最大对集，所以H[U]没有连杆，从而 L?M=L\M≥U=υ?2|M| 又因为H是G的子图，所以M也是G的对集，从而 α′+β′≥M+L≥υ (8.4) 综合(8.3)式和(8.4)式，即得α′+β′=υ。?
第一章习题 1. 对任何简单图G ，(1) 证明：(1) ()2 G υυε?≤；(2) (1) ()2 G υυε?= 当且仅当G K ν?。 2. 证明：(1) ,()m n K mn ε=；(2) 若G 是完全二部图，则2 ()4 G υε≤ 。 3. 图G 有21条边，12个3度顶点，其余顶点的度均为2，求图G 的阶数。 4. 证明：任何简单图必有至少两个顶点具有相等的度。 5. 设G 是简单图，求G 的所有不同的生成子图的个数（包括G 本身和空图）。 6. 证明：任何图中，奇度顶点的个数总是偶数（包括0）。并由此证明：在任一次聚会上握过奇数 次手的人必为偶数个。 7. 证明或反证：如果u 和v 是图G 中仅有的具有奇数度的顶点，则G 包含一条u , v 路。 8. 证明：若4υ≥且1+=νε，则存在)(G V v ∈使得3)(≥v d 。由此证明： n 个球队比赛（4n ≥）， 已赛完n +1场，则必定有一个球队已参加过至少3场比赛。 9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使 得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？ 10. 在平面上有n 个点12{,,,}n S x x x =???，其中任两个点之间的距离至少是1。证明在这n 个点中， 距离为1 的点对数不超过3n 。 11. 某次会议有n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。 12. 在一个化学实验室里，有n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种 化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n 个药箱中共有几种不同的化学品？ 13. 在一次舞会中，A 、B 两国留学生各(2)n n >人，A 国每个学生都与B 国一些(不是所有)学生跳 过舞，B 国每个学生至少与A 国一个学生跳过舞。证明一定可以找到A 国两个学生12,a a 及B 国两个学生12,b b ，使得1a 和12,b a 和2b 跳过舞，而1a 和22,b a 和1b 没有跳过舞。 14. 证明：2ε δυ ≤ ≤Δ，（其中 2ε υ 称为顶点平均度）。 15. 令G 是至少有两个顶点的图。证明或反证：(1) 删除一个度为()G Δ的顶点不会增加顶点的平均 度；(2) 删除一个度为()G δ的顶点不会减小顶点的平均度。 16. 令G 是一个顶点平均度为2a ε υ = 的无圈图。(1) 证明：G x ?的顶点平均度至少为a 当且仅当 ()2 a d x ≤ 。(2) 利用(1)的结果给出一个算法来证明：如果0a >，则G 有一个最小度大于2a 的 子图。
定理10.8 (Kuratowski定理)：一个图G是平面图当且仅当G中不包含同态于K5或K3,3的子图。 证明：在10.3节，我们已证明了K5和K3,3不是平面图，再由定理10.4可知，当一个图G包含同态于K5或K3,3的子图，则G不是平面图。从而定理的必要性得证。 现在我们来证明定理的充分性。我们对G的边数归纳证明。当G 只有m=1条边时，显然G是平面图。现在我们假设当G的边数m< N(N≥2)时，G是平面图。现在设G有m=N条边。我们证明：如果G不包含同态于K5和K3,3的子图，但G不是平面图，则导出矛盾。设G不是平面图，则有以下几个结论： (a)G必须是连通的； (b)G不包含割点； (c)如果G中任一边(x, y)被删除，则所得到的图G′中存在包含x和y 的圈。 我们来证明结论(c)。注意到G′是连通的，这因为G不包含割点。如果G′中不存在包含x和y的圈，那么从x到y的每条路径都经过一个公共点z。换句话说，z是G′的一个割点。那么G′可以在z处分解成两个连通分支G1′包含x和z和G2′包含y和z。我们在G1′中加入边xz，得G1"，在G2′中加入边yz的G2"。这时G1"和G2"都不包含同态于K5和K3,3的子图。这是因为G1′是G的子图不可能包含同态于K5或K3,3的子图，假如G1"中包含这样的子图，则该子图必然经过边xz，而在G中可找到一条从z到y的路径P再加上边yx代替xz，从而G中存在同
态于K5或K3,3的子图，这与假设矛盾。同理可证对G2"结论成立。 由归纳假设，G1"和G2"是平面图。根据定理10.5，我们可以找到G1"的平面嵌入，使得xz在外部面上，也可以找到G2"的平面嵌入，使得yz 在外部面上，令G1"和G2"在z处相交，并用xy边取代xz和yz边，则可以得到G的一个平面嵌入，这与G不是平面图的假设矛盾。从而证明了G′不包含割点。即G′是一个块。再由定理3.2，x和y包含在G′ 的一个圈C中，事实上，C可能是包含x和y的若干个圈中的一个。因为G′不包含同态于K5或K3,3的子图，并且G′比G少一条边，由归纳假设，G′是平面图。设G′是G′的平面嵌入。我们选择C为包含x和y且把G′的尽可能多的面包围在其内部的圈。G′的在C的内部的桥称为内部桥，而G′在C外部的桥称为外部桥。我们给C赋予一个顺时针的方向。如果p和q是C上两个顶点，那么S[p,q]表示C上从p到q 顺时针方向的路径的顶点集。S]p,q[=S p,q?{p,q}。注意到，C的任意一个外桥在S[x,y]或S[y, x]上不可能有两个接触点，否则我们可以找到一个圈C′包含x和y且比C包围更多的面到其内部。 G是由平面图G′加上一条边x,y构造起来。考虑到对C的外桥和内桥的要求以及G不是平面图的假设，C一定有一个外桥E和一个内桥I。对于外桥E，E只能有两个接触点i和j，使得 i∈S]x,y并且 j∈S y,x[ I在C上可以有任意多个接触点，但I至少有两个接触点满足：a∈S]x,y并且 b∈S y,x[ 否则(x,y)就可以加入到C的内部，从而得到G的平面嵌入，矛盾。
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点： 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。 例 定理2.1.1 如果点v 是图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得 ][1E G 和][2E G 恰好有一个公共顶点v 。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 以上两个结论的证明留作习题。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设T 是G 的生成树，则T 至少有两个叶子u ,v ，由上一定理知，u ,v 都不是T 的割点，即1)()(==?T w u T w 。由于u T ?是图u G ?的生成树，故 )(1)()()(G w T w u T w u G w ===?=?，
图论与网络流理论 （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。 [4] 田丰，马仲蕃，图与网络流理论，科学出版社，1987。 [5] 徐俊明，图论及其应用，中国科技大学出版社，1998。 [6] 王树禾，图论及其算法，中国科技大学出版社，1994。 [7] 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。 考核方式：平时成绩＋期末闭卷笔试
第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑
§4.3Hamilton图 * 经过图G的每个顶点恰一次的路称为G的Hamilton路。 * 经过图G的每个顶点恰一次的圈称为G的Hamilton圈。 Hamilton图的研究起源于十二面体的游戏（1856） 与Euler图的有效充要条件。 一、必要条件 定理4.3.1 设G G是二部图，若G 是H图，则G 证明： *Herschel 定理 4.3.2若G是 证明：设C是G的 由于C－S是G－S 证毕。 利用定理4.3.2 但定理4.3.2不能来判断下列Petersen图不是H图。
2. 充分条件 （1）度型条件 定理4.3.3(Dirac, 1952) 若G 是简单图，且3≥ν，2 ν δ≥，则G 是Hamilton 图。 证明 用反证法：假定定理不真。令 |{G A =G 的顶点数为3≥ν，2 ν δ≥ ，且G 是非Hamilton 图}。 取A 中边最多的一个G 。因3≥ν，故不是完全图（否则G 是Hamilton 图） 。设u 和v 是G 的不相邻顶点。由G 的选择，G ＋uv 是Hamilton 图。因G 是非Hamilton 图，故G ＋uv 的H 圈必经过e = uv 。于是G 中存在以u 为起点v 为终点的Hamilton 路νv v v L 21。 这里u v =1，v v =ν，令 }|{1E uv v S i i ∈=+和}|{E v v v T i i ∈=。 由于T S v U ?ν，故ν<||T S U ，并且0||=T S I （因为若T S v i I ∈?，则G 将包含H 圈11121v v v v v v v i i +?L L νν，矛盾）。 故ν<+=+=+||||||||)()(T S T S T S v d u d I U ，这与2 ν δ≥的前提矛盾。证毕。 (2) 闭包型条件 定理4.3.4（Bondy & Chvátal,1974） 设G 是简单图，u 和v 是G 中不相邻的顶点，且 ν≥+)()(v d u d ，则G 是Hamilton 图当且仅当G ＋uv 是Hamilton 图。 证明：必要性是显然的。 充分性：若G ＋uv 是Hamilton 图而G 不是，则与定理4.3.3一样可推出矛盾。证毕。 定义：图G 的闭包（closure ）是指由如下方法所得之图： 反复连接G 中度之和不小于ν的不相邻顶点对，直到没有这样的顶点对为止。 图G 的闭包记为C(G)。
第六章 染色理论 许多实际问题可以归结为求图的匹配或者独立集。此外，在许多应用中，人们希望知道：一个给定的图，它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。 §6.1 点染色 定义6.1.1 设G 是一个无环边的图。G 的顶点正常k 染色(proper vertex k-colouring)π是指k 种颜色k ，，，L 21对于G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。换句话说，G 的顶点正常k 染色π是一个映射 },,2,1{)(:k G V L →π, 使得)(1 i ?π 是独立集或空集),,2,1(k i L =. 注：设π是G 的一个顶点正常k 染色。令 })(|)({)(V 1i x G V x i i =∈==?ππ，（k i ,,2,1L =）。 则π实际上是对顶点集)(G V 的一种划分：),,,(21k V V V L =π，其中φ=j i V V I ， )(1 G V V k i i ==U ，且每个i V 是独立集或空集),,2,1(k i L =. 例： 定义6.1.2 若存在G 的一种顶点正常k 染色，则称图G 是点k 色可染的(vertex k-colourable)， 有时简称为k 色可染的或可k 染色的。 注：⑴ 每个图G 一定是)(G ν色可染的。 ⑵ 若图G 是k 色可染的，则对任何正整数k m ≥，G 也m 色可染。 定义6.1.3 设G 是无环边的图，令 G k G |min{)(=χ是k 色可染的}， 称)(G χ为G 的点色数，有时简称为色数(chromatic number)。若k G =)(χ，则称G 为k 色图(k-chromatic graph)。
第四章 Euler 图和Hamilton 图 §1. Euler 图 一、基本概念 七桥问题：如下图。从任一陆地点出发，经过每座桥一次且仅一次回到出发点，是否可能？ 哥尼斯堡七桥 G 转化为图论问题：图G 中从任一顶点出发，经过每条边恰好一次回到出发点，是否可能？ Euler 环游(tour,circuit,closed trail)：经过图G 的每条边恰好一次的闭迹。 Euler 迹（trail ）：经过每条边恰好一次的迹。 Euler 图：有Euler 环游的图。 七桥问题：图G 是否Euler 图？ 二、Euler 图的判定 定理4.1.1 一个非空连通图是Euler 图当且仅当它没有奇度顶点。 证明 必要性：设图G 是Euler 图，C 是G 中一个Euler 环游。对)(G V v ∈?，v 必在C 上出现。因C 每经过v 一次，就有两条与v 关联的边被使用。设C 经过v 共k 次，则k v d 2)(=。 充分性：无妨设1)(>G ν。因G 连通，故至少有一条边。下面用反证法证明充分性结论。 假设图G 无奇度顶点，但它不是Euler 图。令 S ={G|G 至少有一条边，无奇度顶点，且不是Euler 图} 则φ≠S 。取S 中边数最少的一个，记为G ′。因2)(≥′G δ，故G ′含有圈，因而含有闭迹。设C 是G ′中一条最长的闭迹。由假设，C 不是G ′的Euler 环游。因此)(\C E G ′必有一个连通分支至少含有一条边。记这个连通分支为0G 。由于C 是闭迹，故0G 中没有奇度顶点，且)()(0G G ′<εε。由G ′的选择可知，0G 必有Euler 环游0C 。由于G ′连通，故C 必经过0G 中至少一个顶点，从而φ≠)()(0C V C V I 。因此0C C +是G ′的一条闭迹，且 )()(0C C C εε>+，这与C 的选取矛盾。证毕。
第五章 支配集、独立集、覆盖集和 Ramsey 数
本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的 图均为简单图。
§5.1 支配集、点独立集、点覆盖集
一、支配集(Domination set)
定义 5.1.1 设 D ? V (G ) ，若对 ?u ∈ V (G ) ，要么 u ∈ D ，要么 u 与 D 中的某些顶点相邻， 则称 D 为图 G 的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支 配集。 G 的含顶点最少的支配集称为最小支配集。 图 最小支配集的顶点个数称为 G 的支配数， 记为 γ (G ) 或 γ 。 例如，在下图中， D0 = {v0 } ， D1 = {v1 , v 4 , v7 } ， D2 = {v1 , v3 , v5 , v6 } 都是 G 的支配集， 前两个是极小支配集， D0 是最小支配集。 γ (G ) = 1 。 v1 v8 v7 v6 G v5 v0 v2 v3 v4
注： （1）最小支配集必是一个极小支配集，反之不然。 （2）任一支配集必含有一个极小支配集。 （3）极小支配集不唯一，最小支配集一般也不唯一。 （4）对二部图 G = ( X , Y ) ，X 和 Y 都是支配集。 （5）若图 G 有完美匹配 M*，则从 M*中每边取一个端点构成的顶点集是一个支配集。 定理 5.1.1 设图 G 中无孤立顶点，则存在支配集 D，使得 D = V (G ) ? D 也是一个支配集。 证明：无妨设 G 是连通图。于是 G 有生成树 T。任取 v0 ∈ V (G ) 。令
D = {v | v ∈ V (G ) 且 d T ( v0 , v ) ＝偶数}，
则 D = V (G ) ? D = {v | v ∈ V (G ) 且 d T ( v0 , v ) ＝奇数}，且 D 和 D 都是支配集。证毕。 定理 5.1.2 设图 G 无孤立顶点， D1 是一个极小支配集，则 D1 = V (G ) ? D1 也是一个支配集。 证明（反证法） ：若不然，存在 v0 ∈ D1 ，它与 D1 中所有顶点都无边相连，但它又不是孤立顶 点，故必与 D1 中顶点连边，因此 D1 ? v0 仍是支配集。这与 D1 是极小支配集矛盾。证毕。 推论 5.1.1 设图 G 中无孤立顶点。 G 的任一个极小支配集 D1 ， 对 必存在另一个极小支配集 D2 ， 使得 D1 ∩ D2 = φ 。 证明：由定理 5.1.2， D1 = V (G ) ? D1 也是一个支配集，且 D1 ∩ D = φ 。 D1 中必含有一个极 小支配集 D2 。显然 D1 ∩ D2 = φ 。证毕。
1