中科院研究生院专业基础课：《图论与网络流理论》第一章 图的基本概念 Graph Theory and Network Flow Theory（高随祥）

图论与网络流理论 Graph Theory and Network Flow Theory) 高随 中科院研究生院专业基础课 学时/学分:603 本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数 理统计各专业的硕士学位研究生作为专业基础课,也可供物理学、化学、天文学、 地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通 信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方 法和定理,介绍该领域重要的问题以及典型的算法,展示图论与网络流模型及方 法的广泛应用。为学习者将来从事有关方面的理论研究打下基础,也为进行应用 性研究提供一种有力的工具

1 图论与网络流理论 （Graph Theory and Network Flow Theory） 高随祥 中科院研究生院专业基础课 学时/学分：60/3 本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数 理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、 地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、 信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方 法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方 法的广泛应用。为学习者将来从事有关方面的理论研究打下基础，也为进行应用 性研究提供一种有力的工具

内容提要 第一章图的基本概念 图的基本概念;二部图及其性质;图的同构;关联矩阵与邻接矩阵。 路、圈与连通图;最短路问题。 树及其基本性质;生成树;最小生成树。 第二章图的连通性 割点、割边和块;边连通与点连通;连通度; Whitney定理;可靠通信网络的设计。 第三章匹配问题 匹配与最大匹配:完美匹配;二部图的最大匹配;指派问题与最大权匹配。 第四章欧拉图与哈密尔顿图 欧拉图;中国邮递员问题;哈密尔顿图;旅行商问题 第五章支配集、独立集、覆盖集与团 支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。 第六章图的着色问题 点着色;边着色;平面图;四色猜想;色多项式:色数的应用。 第七章网络流理论 有向图:网络与网络流的基本概念:最大流最小割定理;求最大流的标号算法;最小费 用流问题;最小费用最大流;网络流理论的应用 主要参考书 [JA. Bondy and U.. Murty, Graph theory with applications,1976,有中译本(吴望名等译)。 [2]B. Bollobas, Modern graph theory(现代图论),科学出版社,2001 3]蒋长浩,图论与网络流,中国林业出版社,2001 4]田丰,马仲蕃,图与网络流理论,科学出版社,1987 [5]徐俊明,图论及其应用,中国科技大学出版社,1998。 [6]王树禾,图论及其算法,中国科技大学出版社,1994 「7]殷剑宏,吴开亚,图论及其算法,中国科技大学出版社,2003。 考核方式:平时成绩+期末闭卷笔试

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。 考核方式：平时成绩＋期末闭卷笔试

第一章图的基本概念 §11图的基本概念 图 graph):一集元素及它们之间的某种关系。具体地说,图是一个二元组(V,E),其中 集合V称为顶点集,集合E是V中元素组成的某些无序对的集合,称为边集 例111G=(,E),其中 V={v1,V2,V3,V4,v3},E={(V1,v2),(V2,v3)、(v3,v4)(V3,Vs),(v1,V5),(v1,V5),(vs,"s)}。 这便定义出一个图。 图的顶点集中的元素称为顶点,边集中的元素称为边。在本书中边e=(l,y)也常写为 e=uv,顶点u和v称为边e的端点,反过来也称边e连接顶点u和v。图G的顶点数目|V 称为图G的阶,边的数目E|称为图G的边数。本书中一般将图的边数记为E,将图的阶 记为U 2.图的图示 通常,图的顶点可用平面上的一个点来表示,边可用平面上的线段来表示(直的或曲的)。 这样画出的平面图形称为图的图示。 例如,例1.1.1中图的一个图示为 注:(1)由于表示顶点的平面点的位置的任意性,同一个图可以画出形状迥异的很多图示。 比如下图是例1.1.1中图的另一个图示: (2)图的图示直观易懂,因此以后一般说到一个图,我们总是画出它的一个图示来表示 3.一些术语和概念 设G=(V,E是一个图,下述概念中顶点均取自V,边均取自E。 (1)点与边的关联 (inciden):如果在图G中点v是边e的一个端点,则称点v与边e在 图G中相关联 (2)点与点的相邻 adjacent:如果图上两点uy被同一条边相连,则称u在图G中相

3 第一章 图的基本概念 §1.1 图的基本概念 1. 图(graph)：一集元素及它们之间的某种关系。具体地说，图是一个二元组(V, E) ，其中 集合 V 称为顶点集，集合 E 是 V 中元素组成的某些无序对的集合，称为边集。 例 1.1.1 G = (V, E) ，其中 { , , , , } 1 2 3 4 5 V = v v v v v ， {( , ),( , ),( , ),( , ),( , ),( , ),( , )} 1 2 2 3 3 4 3 5 1 5 1 5 5 5 E = v v v v v v v v v v v v v v 。 这便定义出一个图。 图的顶点集中的元素称为顶点，边集中的元素称为边。在本书中边 e = (u, v) 也常写为 e = uv，顶点 u 和 v 称为边 e 的端点，反过来也称边 e 连接顶点 u 和 v。图 G 的顶点数目| | V 称为图 G 的阶，边的数目| | E 称为图 G 的边数。本书中一般将图的边数记为ε ，将图的阶 记为υ 。 2. 图的图示 通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。 例如，例 1.1.1 中图的一个图示为 注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。 比如下图是例 1.1.1 中图的另一个图示： （2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。 3. 一些术语和概念 设 G = (V, E)是一个图，下述概念中顶点均取自 V，边均取自 E。 （1） 点与边的关联(incident)：如果在图 G 中点 v 是边 e 的一个端点，则称点 v 与边 e 在 图 G 中相关联。 （2） 点与点的相邻(adjacent)：如果图上两点 u,v 被同一条边相连，则称 u,v 在图 G 中相 v5 e1 e2 e3 e4 e5 e6 e7 v1 v3 v2 v4 v4 e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v5

邻。 (3)边与边的相邻:如果图G中两条边有至少一个公共端点,则称这两条边在图G中相 邻。 (4)环边oop):图中两端点重合的边称为环边。 (5)重边( multiedge):设u和v是图G的顶点,图G中连接u和v的两条或两条以上的 边称为图G中u、间的重边。 (6)简单图( simple graph):既无环边也无重边的图称为简单图 (7)完全图( complete graph):任意两点间都有一条边的简单图称为完全图,n阶完全图记 为Kn (8)平凡图 trivial graph)只有一个顶点,没有边的图 (9)空图 empty graph)边集为空的图 (10)零图( null graph):顶点集为空的图。 (11)顶点v的度( degree):图G中顶点v所关联的边的数目(环边计两次)称为顶点v的 度,记为dd(v)或d(v) (12)图G的最大度:△(G)=max{d(v)v∈V(G)} 图G的最小度:(G)=min{d()|v∈(G)} (13)正则图 regular graph):每个顶点的度都相等的图。 (14)图的补图( complement):设G是一个图,以V(G)为顶点集,以{(x,y)(x,y)gE(G)} 为边集的图称为G的补图,记为G。 定理11对任何图G,都有∑d(v)=26 ve/(G) 证明:按每个顶点的度来计数边,每条边恰数了两次。 推论1.11任何图中,奇度顶点的个数总是偶数(包括0)。 证明留作练习。 4.子图 子图( (subgraph):对图G和H,如果V(H)∈H(G)且E(H)cE(G),则称图H是图G的 子图,记为HcG。 生成子图( spanning subgraph)若H是G的子图且(H)=(G),则称H是G的生成子图 点导出子图 (induced subgraph):设G是一个图,V’cV(G)。以V为顶点集,以G中两端 点均属于V的所有边作为边集所组成的子图,称为G的由顶点集V导出的子图,简称为G 的点导出子图,记为G[] 边导出子图 edge-induced subgraph:设G是一个图,E'cE(G)。以E’为边集,以E’中 边的所有端点作为顶点集所组成的子图,称为G的由边集E′导出的子图,简称为G的边导 出子图,记为G[E勹]

4 邻。 （3） 边与边的相邻：如果图 G 中两条边有至少一个公共端点，则称这两条边在图 G 中相 邻。 （4） 环边(loop)：图中两端点重合的边称为环边。 （5） 重边(multiedge)：设 u 和 v 是图 G 的顶点，图 G 中连接 u 和 v 的两条或两条以上的 边称为图 G 中 u、v 间的重边。 （6） 简单图(simple graph)：既无环边也无重边的图称为简单图。 （7） 完全图(complete graph)：任意两点间都有一条边的简单图称为完全图，n 阶完全图记 为 Kn. （8） 平凡图(trivial graph): 只有一个顶点，没有边的图。 （9） 空图(empty graph): 边集为空的图。 （10） 零图(null graph): 顶点集为空的图。 （11） 顶点 v 的度(degree)：图 G 中顶点 v 所关联的边的数目（环边计两次）称为顶点 v 的 度，记为 dG(v)或 d(v)。 （12） 图 G 的最大度： (G) max{d (v) | v V (G)} Δ = G ∈ ； 图 G 的最小度： (G) min{d (v) | v V (G)} δ = G ∈ 。 （13）正则图(regular graph)：每个顶点的度都相等的图。 （14）图的补图(complement)：设 G 是一个图，以V(G) 为顶点集，以{(x, y) | (x, y) ∉ E(G)} 为边集的图称为 G 的补图，记为G 。 定理 1.1.1 对任何图 G，都有 ( ) ( ) 2 vVG d v ε ∈ ∑ = 。 证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 证明留作练习。 4. 子图 子图(subgraph)：对图 G 和 H，如果V(H) ⊆ V(G) 且 E(H) ⊆ E(G) ，则称图 H 是图 G 的 子图，记为 H ⊆ G 。 生成子图(spanning subgraph): 若 H 是 G 的子图且VH VG ( ) () = ，则称 H 是 G 的生成子图。 点导出子图(induced subgraph)：设 G 是一个图，V ′ ⊆ V(G) 。以V ′为顶点集，以 G 中两端 点均属于V ′的所有边作为边集所组成的子图，称为 G 的由顶点集V ′导出的子图，简称为 G 的点导出子图，记为G[V ′]. 边导出子图(edge-induced subgraph)：设 G 是一个图， E′ ⊆ E(G) 。以 E′为边集，以 E′中 边的所有端点作为顶点集所组成的子图，称为 G 的由边集 E′导出的子图，简称为 G 的边导 出子图，记为G[E′]

设gV(G),EcE(G),今后经常用G-表示从图G中删除顶点子集V"(连 同它们关联的边一起删去)所获得的子图,用G-E表示从图G中删除边子集E′(但不 删除它们的端点)所获得的子图。特别地,对顶点v和边e,常用G-v表示G-{v},G-e 表示G-{e}图G的一个顶点子集E'。 5.路和圈 途径wak:图G中一个点边交替出现的序列w=veve2…∈V称为图G的一条途径, 其中v、V分别称为途径w的起点和终点,w上其余顶点称为中途点 迹(trai):图G中边不重复的途径称为迹。 路(path):图G中顶点不重复的迹称为路。 (注:简单图中的路可以完全用顶点来表示,P=VV1…v) 闭途径( closed walk:图G中起点和终点相同的途径称为闭途径。 闭迹( closed trail):图G中边不重复的闭途径称为闭迹,也称为回路( circuit)。 圈( cycle):中途点不重复的闭迹称为圈 注 (1)途径(闭途径)、迹(闭迹)、路(圈)上所含的边的数目称为它的长度 (2)简单图G中长度为奇数和偶数的圈分别称为奇圈 odd cvcle)和偶圈( even cvcle) (3)对任意x,y∈V(G),从x到y的具有最小长度的路称为x到y的最短路( shortest path) 其长度称为x到y的距离 distance,记为d(x,y) (4)简单图G中最短圈的长度称为图G的围长 girth),最长圈的长度称为图G的周长 (circumference) 例112设G是一个简单图,若δ(G)≥2,则G中必含有圈 证明:设G中的最长路为P=vV1…V。因d(v0)≥2,故存在与v1相异的顶点v与v相 邻。若vgP,则得到比P更长的路,这与P的取法矛盾。因此必定v∈P,从而G中有 圈。证毕。 例113设G是简单图,若(G)≥3,则G必有偶圈 证明:设P=v0V1…v是G的最长路。 因为d(v)≥3,所以存在两个与v1相异的顶点v,v”与v相邻。v,v"必都在路P上, 否则会得到比P更长的路。无妨设v=,"=v,(</)。 若i,j中有奇数,比如i是奇数,则路P上v0到v的一段与边vv构成一个偶圈 若都是偶数,则路P上v到v的一段与边vv及v”,构成一个偶圈。证毕。 例14设G是简单图,若(G)≥3,则G中各个圈长的最大公因数是1或2

5 设V ′ ⊆ V (G) ， E′ ⊆ E(G) ，今后经常用G −V ′ 表示从图 G 中删除顶点子集V ′（连 同它们关联的边一起删去）所获得的子图，用G − E′ 表示从图 G 中删除边子集 E′（但不 删除它们的端点）所获得的子图。特别地，对顶点 v 和边 e，常用G − v 表示G {} − v ，G − e 表示G e −{ }图 G 的一个顶点子集 E′。 5. 路和圈 途径(walk)：图 G 中一个点边交替出现的序列 k k i i i i i i w v e v e "e v 0 1 1 2 = 称为图 G 的一条途径， 其中 0 i v 、 k i v 分别称为途径 w 的起点和终点，w 上其余顶点称为中途点。 迹(trail)：图 G 中边不重复的途径称为迹。 路(path)：图 G 中顶点不重复的迹称为路。 （注：简单图中的路可以完全用顶点来表示， k i i i P v v "v 0 1 = ） 闭途径(closed walk)：图 G 中起点和终点相同的途径称为闭途径。 闭迹(closed trail)：图 G 中边不重复的闭途径称为闭迹，也称为回路（circuit）。 圈(cycle)：中途点不重复的闭迹称为圈。 注： （1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的数目称为它的长度。 （2）简单图 G 中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。 （3）对任意 x, y ∈V(G)，从 x 到 y 的具有最小长度的路称为 x 到 y 的最短路（shortest path）， 其长度称为 x 到 y 的距离(distance)，记为d (x, y) G 。 （4）简单图 G 中最短圈的长度称为图 G 的围长(girth)，最长圈的长度称为图 G 的周长 (circumference)。 例 1.1.2 设 G 是一个简单图，若δ (G) ≥ 2，则 G 中必含有圈。 证明：设 G 中的最长路为 k P v v "v = 0 1 。因d(v0 ) ≥ 2 ，故存在与 1 v 相异的顶点 v 与 0 v 相 邻。若v ∉ P ，则得到比 P 更长的路，这与 P 的取法矛盾。因此必定v ∈ P ，从而 G 中有 圈。证毕。 例 1.1.3 设 G 是简单图，若δ (G) ≥ 3 ,则 G 必有偶圈。 证明：设 k P v v "v = 0 1 是 G 的最长路。 因为d(v0 ) ≥ 3， 所以存在两个与 1 v 相异的顶点v′, v′′ 与 0 v 相邻。v′, v′′ 必都在路 P 上， 否则会得到比 P 更长的路。无妨设v v , v v , (i j) ′ = i ′′ = j < 。 若i, j 中有奇数，比如 i 是奇数，则路 P 上 0 v 到 i v 的一段与边 i v v0 构成一个偶圈； 若i, j 都是偶数，则路 P 上 i v 到 j v 的一段与边 i v v0 及 j v v0 构成一个偶圈。证毕。 例 1.1.4 设 G 是简单图，若δ (G) ≥ 3 ,则 G 中各个圈长的最大公因数是 1 或 2