[理学]课件图论讲义.pdf

1图论与网络流理论图论与网络流理论 （（Graph Theory and Network Flow Theory）） 讲授：高随祥讲授：高随祥 中科院研究生院专业基础课中科院研究生院专业基础课 学时学时/学分：学分：60/3 本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课， 也可供物理学、 化学、 天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具 2内容提要内容提要 第一章 图的基本概念第一章 图的基本概念 图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵 路、圈与连通图；最短路问题 树及其基本性质；生成树；最小生成树 第二章 图的连通性第二章 图的连通性 割点、割边和块；边连通与点连通；连通度；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 考核方式考核方式：平时成绩＋期末闭卷笔试 3第一章第一章 图的基本概念图的基本概念 §§1.1 图的基本概念图的基本概念 1. 图图(graph)：一集元素及它们之间的某种关系具体地说，图是一个二元组),(EV，其中集合 V 称为顶点集，集合 E 是VV ×的一个子集（无序对，元素可重复） ，称为边集 例例 1.1.1 ),(EVG=，其中 },,,,{54321vvvvvV =，)},(),,(),,(),,(),,(),,(),,{(55515153433221vvvvvvvvvvvvvvE = 这便定义出一个图 2. 图的图示图的图示 通常， 图的顶点可用平面上的一个点来表示， 边可用平面上的线段来表示 （直的或曲的） 这样画出的平面图形称为图的图示 例如，例 1.1.1 中图的一个图示为 注注： （1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示 比如下图是例 1.1 中图的另一个图示： （2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示 3. 一些概念和术语一些概念和术语 （1） 点与边的关联(incident) （2） 点与点的相邻（adjacent） （3） 边与边的相邻 （4） 边的端点（end vertices） （5） 环边(loop) （6） 重边(multiedge) （7） 简单图(simple graph) v5e1e2e3e4e5e6e7v1v2v3v4 v4e1e2e3e4e5e6e7v1v2 v3v54（8） 完全图(complete graph) （9） 图的顶点数（图的阶）ν、边数ε （10） 顶点 v 的度(degree)：d(v) = 顶点 v 所关联的边的数目（环边计两次） 。

（11） 图 G 的最大度：)}(| )(max{)(GVvvdGG∈=∆ 图 G 的最小度：)}(| )(min{)(GVvvdGG∈=δ （12）正则图(regular graph)：每个顶点的度都相等的图 （13） 图的补图(complement)： 设 G 是一个图， 以)(GV为顶点集， 以)}(),( | ),{(GEyxyx∉为边集的图称为 G 的补图，记为G 定理定理 1.1.1 ε2)()(=∑ ∈GVvvd 证明：按每个顶点的度来计数边，每条边恰数了两次 推论推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0） 4 4. 子图子图 子图子图(subgraph)：如果)()(GVHV⊆且)()(GEHE⊆，则称图 H 是 G 的子图，记为GH ⊆ 生成子图生成子图(spanning subgraph): 若 H 是 G 的子图且()( )V HV G=，则称 H 是 G 的生成子图 点导出子图点导出子图(induced subgraph)：设)(GVV ⊆′，以V′为顶点集，以两端点均在V′中的边的全体为边集所组成的子图，称为 G 的由顶点集V′导出的子图，简称为 G 的点导出子图，记为][VG′. 边导出子图边导出子图(edge-induced subgraph)：设)(GEE ⊆′，以E′为边集，以两端点均在E′中的边的全体为边集所组成的子图， 称为 G 的由边集E′导出的子图， 简称为 G 的边导出子图，记为][EG′. 5. 路和圈路和圈 途径途径(walk)：图 G 中一个点边交替出现的序列 kkiiiiiiveevevwL 2110=。

迹迹(trail)：边不重的途径 路路(path): 顶点不重复的迹 （注：简单图中的路可以完全用顶点来表示， kiiivvvPL 10=） 闭途径闭途径（closed walk） ：起点和终点相同的途径 闭迹闭迹(closed trail)：起点和终点相同的迹，也称为回路（circuit）. 圈圈(cycle): 起点和终点相同的路 5注：注： （1）途径（闭途径） 、迹（闭迹） 、路（圈）上所含的边的个数称为它的长度长度 （2）简单图 G 中长度为奇数和偶数的圈分别称为奇圈奇圈(odd cycle)和偶圈偶圈(even cycle) （3） 对任意)(,GVyx∈， 从 x 到 y 的具有最小长度的路称为 x 到 y 的最短路最短路 （shortest path） ，其长度称为 x 到 y 的距离距离(distance)，记为),(yxdG （4）图 G 的直径(diameter): )}(,| ),(max{GVyxyxdDG∈∀=. （5）简单图 G 中最短圈的长度称为图 G 的围长围长(girth)，最长圈的长度称为图 G 的周长周长 (circumference) 例例 1.1.2 设 G 是一个简单图，若2)(≥Gδ，则 G 中必含有圈。

证明：设 G 中的最长路为kvvvPL10=因2)(0≥vd，故存在与1v相异的顶点 v 与0v相邻若Pv∉，则得到比 P 更长的路，这与 P 的取法矛盾因此必定Pv∈，从而 G 中有圈 例例 1.1.3 设 G 是简单图，若3)(≥Gδ,则 G 必有偶圈 证明：设kvvvPL10=是 G 的最长路 因为3)(0≥vd， 所以存在两个与1v相异的顶点vv′ ′′,与0v相邻vv′ ′′,必都在路 P 上，否则会得到比 P 更长的路无妨设)(,,jivvvvjim，则)( |jim−，于是2|m，这是不可能的因此1, 1++ji，2+−ij三数的公因数必不超过 2从而各个圈长的最大公因数是 1 或 2 6. 二部图二部图 二部图二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得任一条边都有一个端点在 X 中， 另一个端点在 Y 中， 则称 G 为二部图 （或偶图） ， 记为 G＝),(EYXU，),(YX称为 G 的一个划分 完全二部图完全二部图(complete bipartite graph)：在二部图),(EYXGU=中，若 X 的每个顶点与 Y的每个顶点有边连接，则称 G 为完全二部图；若mX = ||，nY = ||，则记此完全二部图为nmK,。

6定理定理 1.1.2 一个图是二部图当且仅当它不含奇圈一个图是二部图当且仅当它不含奇圈 证明： 必要性必要性：设010vvvvCkL=是二部图),(EYXGU=的一个圈无妨设Xv ∈0，由二部图的定义知，Yv ∈1，Xv ∈2，L，一般地，Xvi∈2，Yvi∈+12， （L, 1 , 0=i） 又因Xv ∈0，故Yvk∈，因而 k 是奇数注意到圈 C 上共有1+k条边，因此是偶圈 充分性充分性：设 G 不含奇圈取)(GVu∈，令 }),(| )({oddvudGVvX＝∈=，}),(| )({evenvudGVvY＝∈= 任取一条边21vve =，欲证21,vv分属于 X 和 Y设 P，Q 分别是 u 到21,vv的最短路 （1）如果12vvQP+=或21vvPQ+=，则21,vv到 u 的距离奇偶性相反，21,vv分属于 X 和 Y （2）否则，设u′是 P 与 Q 的最后一个公共顶点，因 P 的),(uu′段和 Q 的),(uu′段都是 u到u′的最短路，故这两段长度相等 假如 P，Q 的奇偶性相同，则 P 的),(1vu′段和 Q 的),(2vu′段奇偶性相同，这两段与边e 构成一个奇圈，与定理条件矛盾。

可见 P，Q 的奇偶性不同，从而21,vv分属于 X 和 Y 这便证明了 G 是一个二部图 7. 连通性连通性 图中两点的连通图中两点的连通：如果在图 G 中 u，v 两点有路相通，则称顶点 u，v 在图 G 中连通 连通图连通图（connected graph） ：图 G 中任二顶点都连通 图的连通分支图的连通分支（connected branch, component） ： 若图 G 的顶点集 V(G)可划分为若干非空子集ωVVV,,,21L，使得两顶点属于同一子集当且仅当它们在 G 中连通，则称每个子图][iVG为图 G 的一个连通分支（ω,, 2 , 1L=i） 注注： （1）图 G 的连通分支是 G 的一个极大连通子图 （2）图 G 连通当且仅当1＝ω 例例 1.1.5 设有 2n 个交换台， 每个台与至少 n 个台有直通线路， 则该交换系统中任二台均可实现通话 证明：证明：构造图 G 如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路问题化为：已知图 G 有 2n 个顶点，且nG ≥)(δ，求证 G 连通 事实上，假如 G 不连通，则至少有一个连通分支的顶点数不超过 n。

在此连通分支中，顶点的度至多是1−n这与nG ≥)(δ矛盾 例例 1.1.6 若图中只有两个奇度顶点，则它们必连通 证明：证明：用反证法假如 u 与 v 不连通，则它们必分属于不同的连通分支将每个分支看成一个图时，其中只有一个奇度顶点这与推论 1.1.1 矛盾 78 8. 图的同构图的同构 由前已知，同一个图有不同形状的图示反过来，两个不同的图也可以有形状相同的图 示比如： 可见1G和2G的顶点及边之间都一一对应， 且连接关系完全相同， 只。