第1章图论2教材

§1.6

偶图、匹配及其应用一．偶图

定义1

若图G=(V,E)的点集能划分为两个互不相交的非空子集V1与V2（V1∪V2=V），使任意的e∈E，e

的两端点分属于V1与V2，则称

G为偶图，记为G=(V1,V2,E)。

若偶图G=(V1,V2,E)为简单图，且V1的每个点均与V2的每个点相邻，则称G为完全偶图，记为Km,n

，其中

m,n分别为V1与V2的点数。

例

K3,3

K1,3

G1

G2

四个图均为偶图;

K1,3,K3,3为完全偶图

定理11一个图是偶图当且仅当它不含长度为奇的圈。例偶图不是偶图又由定理11知至少两个点的树是偶图。二．匹配

定义2设M是图G的边子集，若任意的e∈M，e

都不是环，且属于M的边互不相邻，则称M为

G的一个匹配。设M为

G的一个匹配，对v∈V(G)，若v是M中某边的一个端点，则称v为M饱和点，否则称为M非饱和点。

匹配还可分为最大匹配（含边数最多的匹配）和完美匹配（图中的点均为M饱和点的匹配M）等类型。对M2，点v1是的饱和点，点v2是非饱和点。v1v2v3v4v8v5v7v6

例1中的M1

和M2既不是最大匹配，也不是完美匹配，而M3是最大匹配，也是完美匹配。例1设图G为:G的匹配有：M1={v1v8}M2={v1v3，v8v4，v7v5}M3={v1v2，v8v3，v7v4，v6v5}等等

关系：

(1)

完美匹配必是最大匹配，而最大匹配不一定是完美匹配。(2)

一个图的最大匹配必存在，但完美匹配不一定存在。(3)

图G存在完美匹配的一个必要条件是G的点数为偶。

设M为图G的一个匹配可看出：对Г3，若取Г3中非M的边再连同

M的不在Г3中的边组成M’，则M’的边数比

M的边数多，这表明

M不是该图的最大匹配。M交替路：G中由M中的边与非M中的边交替组成的路。M可扩路：起点与终点均为M非饱和点的M交替路。例如，取M={红边}Г1Г2Г3M交替路M可扩路定理12

G的匹配M是最大匹配当且仅当G不含M可扩路.三．偶图的匹配取图G的一个顶点子集S，令

N(S)={v|存在u∈S，且v与u相邻}称N(S)为S的邻集。取S={v1,v2}，则N(S)={v8,v3,v1,v2}v1v2v3v4v8v5v7v6例如图中1．偶图存在最大或完美匹配的条件设偶图G=(V1,V2,E)，则有下列必要或充分条件：①

G存在饱和

V1的每个点的匹配，当且仅当对任意的

S

V1，有|N(S)|≥|S|即

N(S)的点数不少于S的点数。Í②

若存在正整数t，满足任意的v∈V1，有

d(v)≥t，同时对任意的u∈V2，有d(u)≤t，则G存在饱和V1的每个点的匹配。③

若G为k正则偶图，k>0，则G存在完美匹配。④若|

V1|>|V2|，则不存在饱和V1的每个点的匹配。

例2

判断图G1与图G2（如下图所示）是否存在饱和V1的每个点的匹配，其中V1={v1,v2,v3}。解

对G1，取S={v1,v2}，则

N(S)=

{u1}，有|N|(S)|<|S|。由条件①，G1不存在饱和V1的每个点的匹配。对G2，因对任意的v∈V1，有

d(v)≥3，对任意的u∈V2，有

d(u)≤3。由条件②知V1存在饱和V1的每个点的匹配。实际上，匹配M={v1u1，v2u3，v3u4}即满足要求。G1G2v1

v2

v3v1

v2

v3u1

u2u3

u4u1

u2u3

u4应用—工作安排问题

问题：n个工人x1,x2,…,xn，n

件工作y1,y2,…,yn。已知xi

能胜任

ki

件工作，i=1，2，…,n。问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作。假定每件工作只能一人做，若能，又如何安排？

建模：以工人和工作为点，当且仅当xi

能胜任工作

yj

时则连线，得偶图G=(V1,V2,E)。于是一种符合要求的安排对应G中一个完美匹配。所以此问题实际上是求偶图的完美匹配问题.

进一步：若不要求人数与工作数相等，则问题是求偶图的饱和V1的每个点的匹配问题，其中V1是工人的集合；进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为求偶图的最大匹配问题。求偶图的最大匹配的方法，称为匈牙利算法

算法思想：先任取一个匹配

M，然后寻找M可扩路。若不存在M可扩路，则M为最大匹配；若存在，则将可扩路中M与非M的边互换，得到一个比M多一条边的匹配M

’，再对M

’

重复上面过程。算法是从V1的每个非饱和点出发寻找M可扩路的。若从V1的每个非饱和点出发都无M可扩路，则M必无可扩路，从而M是最大匹配。这是因偶图中不可能存在两个端点均在V2中的M可扩路。匈牙利算法

给定偶图G=(V1,V2,E)。(1)任取一个匹配M。(3)

取V1的非饱和点

x0，令

X={x0}，Y=Φ。(5)若y为饱和点，则转（6）；否则转（7）。(6)

存在z∈V1，有yz∈M，令

X=

X∪{z}，Y

=

Y∪{y}，转（4）。(7)

存在x0到

y的M可扩路Γ，令

M=(M∪E(Γ))\

(M∩E(Γ))，转（2）。(2)

若

V1中每个点均为

M饱和点，则停（输出M）；否则继续（3）。(4)

若N(X)=Y，则将x0也作为M饱和点对待，转(2)；否则取

y∈N(X)\Y。例3求图G（如图（a）所示）的最大匹配，其中V1={v1,v2,v3,v4,v5}。（1）任取一个匹配M={v1u1，v3u3，v5u5}，如图（a）的红边所示。(2)显然V1中存在非饱和点，取其中一个

v2，令X={v2}，Y=Φ。①因N(X)={u1,u3}≠Y，故取u1∈N(X)\Y=N(X)={u1,u3}。②

u1为饱和点，且v1u1∈M，令X=X∪{v1}={v1,v2}，Y=Y∪{u1}=

{u1}。③因N(X)={u1,u2,u3}≠Y，故取u2∈N(X)\Y={u2,u3}。④u2为非饱和点，得M可扩路Γ=v2u1v1u2v1u3u4u2u1v3v4v5u5v2(a)⑤取M=(M∪E(Γ))\

(M∩E(Γ))={v2u1,v1u2,v3u3,v5u5}，如图（b）中的红边。(3)

取V1的非饱和点

v4。从v4出发重复（2）的过程得M可扩路Γ=v4u5v5u4

(4)

V1已无非饱和点，故结束。v1u3u4u2u1v3v4v5u5v2(b)v1u3u4u2u1v3v4v5u5v2(c)取M={v1u2，v2u1，v3u3，v4u5，v5u4}，如图（c）中红边。工作安排问题未考虑每人做某项工作的效率。若要求考虑效率，并问“如何安排使效率最大”，这称为最优安排问题。最优安排的图论模型是在赋权偶图中寻找具有最大权的匹配。鉴于课时，此问题的求解不作介绍。§1.7图的着色一、边着色设A,B是两个集合，φ是A到B的一个映射，记为φ：A→B，对Í¢ABBAÍ¢,记φ()()}{AaaA¢Î=¢fφ-1，()}{BxxB¢Î=¢)(f特别地当

B’＝{b}时，φ

也记为φ(b)。-1-1()B¢定义

给定图G=(V,E),称映射

φ：E

→{1,2,…,k}为G的一个k-边着色，简称边着色，称{1,2,…,k}为色集。若φ为G的边着色且

e’,e’’

ÎE,当e’

与e’’相邻时，φ(e’)≠φ(e’’)，则称该着色是正常的。图G的正常k-边着色的最小k值称为G的边色数，记为c’

(G),简记为c’

.

若图G存在一个正常k-边着色，则称G是k-边可着色的。

若φ为图G的边着色，e为G的边，我们也称φ(e)为边e的着色或边e着φ(e)色。图(a)和图(b)表达了同一个图的两个3-边着色。其中(b)为正常3-边着色。(a)(b)'c易知该图有=3任何正常边着色中和任一顶点关联的各边必须着不同色，由此推知c′≥Δ

定理定理对任意的二部图G，c

′(G)=Δ(G)。解

设Km,n的互补顶点子集为X={x0,x1,…,xm-1}，Y={y0,y1,…,yn-1}。例

给出Km,n

的一个正常Δ-边着色。假定m≤n,此时Δ＝n。()nmjiKEyx,Î"记为＝使,φ(xiyj)=(i+j)(modn)i＋nj令

φ：E(Km,n)→{0,2,…,n-1}任取Km,n中两条邻边xiyj

和xiyk,

j≠k。从而，c′

(Km,n)≤n≤Δ所以，c′

(Km,n)=Δ同理，对邻边xiyj

和xkyj,也有φ(xiyj)≠φ(xkyj)。若φ(xiyj)=φ(xiyk),则i＋nj=

i＋nk,从而

j＝k，矛盾。所以φ(xiyj)≠φ(xiyk)。以上表明φ是正常边着色。定理(Vizing)①若G是简单图，则c′(G)=D或D+1。②设无环图G

的最大重数为m，则c’

≤Δ+m。例下图是一个边色数达到Δ+µ

的图，其中Δ=4,µ=2。简单图的边色数仅两种情况，或为Δ，或为Δ＋1。我们将c’=Δ的简单图称为第一类图，否则为第二类图。易知，路、树、简单偶图为第一类图；奇圈、n为奇时的Kn为第二类图。尽管简单图的边色数仅两类，但判断一个什么样的简单图是第一类图，这个问题还未完全解决。边着色的应用—排课表问题问题：设有m位教师x1,x2,…,

xm

和n个班级y1,y2,…,

yn。已知在一周内xi需给

yj

上

kij

节课，若将上一节课所用的时间称为一个课时。问如何制订一张课时数尽可能少的课表？假定在同一课时内一位教师只能上一个班，一个班只能一个教师上。建模：将教师与班级作为点，若教师xi需给

yj

上

kij节课，则在xi与

yj

间连

kij

条边，得偶图G。这样，一个课时1－1对应G中－个匹配，而一个匹配又1－1对应一种正常边着色的着同色的一组边。例如，取n=2，m=3，并假定x1需给

y1上两节课；x1,x2需给

y2,y3各上一节课的偶图模型如图所示。此图的边色数为4，这对应一个四课时的课表。x2x1y1y2y3

因偶图G的边色数为△(G)，所以排课表问题可归纳为：对给定的偶图G=(V1,V2,E)，如何对G用△(G)种色进行正常边着色？求解方法如下：(1)

假定|V1|≥|V2|,加点扩充V2为V2*,使|V1|=|V2*|。(2)找出V1中最小度点与V2中最小度点，然后连成边。如此直至各点的度均等于△(G)，记所得之图为G*。由前面的章节的讨论知G*存在完美匹配。(3)用匈牙利算法找出G*的一个完美匹配M1，再找G*-M1

的完美匹配M2，如此继续可求得G*的一组互不相交的完美匹配M1，M2，…,M△

。(4)取M1，M2，…,M△

中原来图的边即为所求。例4

求下图G

的一个颜色数达到最小的正常边着色。解c’（G）=△(G)=3扩充G为G*，见图(a)。G*的一个正常边着色也见(a)。x1x2x3x4y1y2y3G:(a)x1x2x3x4y1y2y3y4x1x2x3x4y1y2y3G的着色

二、顶点着色定义

给定图G=(V,E)，称映射

φ：V→{1,2,…,k}为G的一个k–点着色，简称着色，称{1,2,…,k}为色集。若对G中任意两个相邻顶点u和v均满足φ(u)≠φ(v),则称该着色为正常的。图G的正常k–着色的最小k值称为G的色数，记为c(G),简记为c

。

若图G存在一个正常k-着色，则称G是k-可着色的。设是G的一个着色，u为G中的点，我们也称φ(u)为u的着色或u着φ(u)色。上图的(a),(b)表达了一个图的两个3-着色，其中(b)为正常的，易知该图有c＝3。(a)(b)

定理对任意的图G均有：≤Δ+1c证明

对图G的点数n用归纳法。当n＝1时，c

=1，Δ≥0，满足c

≤Δ+1。

对n≥2的图G,取u∈V(G),设G’＝G-u。由归纳假设c(G’)≤Δ(G’)+1，从而存在G’的(Δ(G’)+1)-着色φ。因Δ(G’)≤Δ(G),所以φ也是G’的(Δ(G)+1)-着色。(G)≤Δ(G)+1c设

dG(u)=k,G中与u相邻的点为v1,v2,…,vk。因|{φ(v1),…,φ(vk)}|≤k＜Δ(G)+1,所以存在j∈{1,2,…,Δ(G)+1}满足j

{φ(v1),…,φ(vk)},令φ(u)=j,则φ被扩充为G的一个(Δ(G)+1)-着色，所以定理

设G是连通图。假定G既不是完全图又不是奇圈，则≤Δc一个着色算法：

给定图G=(V，E)，设V={v1,v2,…,

vn}，着色函数为φ

，色集C={1,2,…,Δ+1}。(i)令φ(v1)=1,i=1。(ii)

若i=n,则停；否则令

C(vi＋1)

={φ

(vj)|j≤i并且vj

与vi＋1相邻}设k为C\C(v

i＋1)

中的最小正整数，令

φ

(vi＋1)=k。(iii)令i=i+1,转(ii)

例试用算法给图中的图着色。

解

设φ

为着色函数，C={1,2,…,5},着色过程如下:V1V6V5V2V3V4(1)φ

(v1)=1,C(v2)={1},C\C(v2)={2,…,5}(2)φ(v2)=

2,C(v3)={1,2},C\C(v3)={3,…,5}(3)φ(v3)=3,C(v4)={3},C\C(v4)={1,2,4,5}(4)φ(v4)=1,C(v5)={1},C\C(v5)={2,…,5}(5)φ

(v5)=2,C(v6)={1,2,3},C\C(v6)={4,5}(6)φ

(v6)=

4§1.8

平面图

问题：假定有三个仓库x1，x2，x3和三个车站y1，y2，y3。为了便于货物运输，准备在仓库与车站间修筑铁路，如图(a)所示,其中边代表铁路。问是否存在一种使铁路不交叉的路线设计方案，以避免修建立交桥。

问题的解答但如果在x3与y1之间也要修一条铁路，则可验证满足要求的方案不存在。

x1

x2x3y1

y2y3(a)

x1

x2x3

y1

y2y3?

定义1

若图G可画在一个平面上使除顶点外边不交叉，则称G可嵌入平面，或称G为可平面图。可平面图G的边不交叉的一种画法称为G的一个平面嵌入，G的平面嵌入表示的图称为平面图。例1=平面图可平面图可平面图不可平面图=不可平面图

=可平面图==可平面图

定义：设G是一个平面图，G将所嵌入的平面划分为若干个区域，每个区域的内部连同边界称为G的面，无界的区域称为外部面或无限面。每个平面图有且仅有一个外部面。设f是G的一个面，构成f的边界的边数（割边计算两次）称为f的次数，记为deg(f

)。例2

有5个面：f1，f2，f3，f4，f5（f5为外部面）图不连通，其外部面的次数为5f1f2f3f5f4deg(f1)=1deg(f2)=2deg(f3)=3deg(f4)=6deg(f5)=10相加为22，正好是边数11的2倍定理19

设具有m条边的平面图G的所有面的集合为Ψ,则m2)deg(=åYÎff（8.1）证明

任取G的一条边e。若e是两个面的公共边，则在计算面的次数时，e被计算两次。若e不是公共边，则e是G的割边，由面的次数的定义，e也被计算两次。所以所有面的次数之和是边数的2倍，即（8.1）式成立。证明

对r用归纳法。设r=k时，（8.2）式成立。定理20（Euler公式）设G是具有n个点m条边r个面的连通平面图，则有

n–m+r=2（8.2）当r=1时，G无圈又连通，从而是树，有n=m+1于是n-m+r

=（m+1）-m+1=2同时n’

=n，m’=m-1，r’=r-1代人（8.3）式得

n-（m-1）+（r-1）=2即n–m+r=2

当r=k+1时，此时G至少两个面，从而有圈C。删去C中一条边，记所得之图为G’。并设G’的点数、边数和面数依次为n’,m’和r’,易知G’仍连通，但只有k个面，由归纳假设有

n’-m’+r’=2（8.3）定理21

设G是具有n

个点m条边的连通平面图,Ψ是G中所有面的集合，若对任意的f∈Ψ均有deg(f)≥l≥3，则

)2(2--£nmll(8.4)证明

设G有r个面，因每个面均有deg（f）≥l

，故åFÎ=£fflmr2)deg()1.8(mrl2£Þ将上式代入Euler公式

n–m+r=2得22³+-mmnlÞ)2(2--£nmll推论22设简单可平面图G有n

个点m条边,且n≥3，则

m≤3n-6

（8.5）证明

先假定G连通。因G至少有三个点又连通且为简单图，故对G相应的平面图中每个面的次数至少是3。由定理21，取l=3得m≤)2(233--n=3-6n

设G不连通。若G存在至少有三个点的连通分支，因对G的这些分支均满足（8.5）式，将各不等式相加也得类似不等式，设为m1≤3n1-6。

设G没有大于两个点的连通分支。此时m≤n。因n≥3时，n≤3n-6，所以有m≤3n-6。再设G的所有少于3个点的连通分支的总边数为m2，总点数为n

2。此时有m2≤n

2≤3n

2，于是m1+m2≤3(n

1+n

2)-6，从而有m≤3n-6。例3

证明K5和K3,3是不可平面图。证明

若K5是可平面图，则因K5是至少三个点的简单图，由推论22，K5应满足m≤3n-6。而K5中m=10，n=5，代入不等式(8.5)得10≤3×5–6=9矛盾，所以K5是不可平面图。对K3,3，因K3,3没有长小于4的圈，所以若K3,3是可平面图，则对其相应的平面图中每个面的次数至少为4。由定理21，K3,3应满足l=4的不等式（8.4）即m≤（-2）=2-4244-nn而K3,3中m=9，n=6，代入上式得:9≤2×6-4=8矛盾，所以K3,3是不可平面图。

定理23若G是简单平面图，则δ≤5.证明

对点数n=1，2，直接验证可知结论成立。设n≥3，若δ≥6，则åÎ=£)(2)(6GVvdnm

n

m＞3n-6Þ这与推论22矛盾。所以δ≤5。§1.9

网络流一运输网络与最大流

现实生活中，人们经常见到一些网络，如铁路网、公路网、通信网、煤气管网等。这些网络有一个共同的特点，就是在网络中都有诸如物资、人或信息等某种量从一个地方流向另一个地方。因而如何安排这些量的流动以便取得最大效益将是一个很有意义的课题。

本节将涉及有向图，其定义只须将无向图的定义中的无序点对改为有序点对即可。我们将有向图中以x为起点y为终点的有向边记为〈x,y〉。有向图中点v的出度定义为图中以点v为起点的边的条数，记为d+(v)；点v的入度定义为图中以v为终点的边的条数，记为d-(v)；度定义为出度加上入度，仍记为d(v)。例1图1-46表示的图是一个有向图，其中

d+(u1)=2，d-(u1)=1，d(u1)=3；d+(u4)=1，d-(u4)=2，d(u4)=3u1u3u4u2图1-46

定义1一个连通的且无环的有向图G=〈V,E〉，若满足下列条件：

(1)恰有一个入度为零的点s（称为发点）；(2)恰有一个出度为零的点t（称为收点）；(3)每条边上都带有一个非负的权（称为边容量），则称G为运输网络，简称为网络。网络中，边〈x,y〉的容量记为c(x,y)，既非发点又非收点的点称为中间点。例图1-47就是一个网络。

sbdcta782546534图1-47定义2

给定网络G=〈V,E〉，若定义在E上的实值函数f

满足：（1）对任意的(x,y)∈E，有0≤f(x,y)≤c(x,y),

f(x,y)称为边〈x,y〉的流量；（2）所有中间点v，恒有

f-(v)=f+(v)其中f-(v)表示所有以v为终点的边上的流量之和，f+(v)表示所有以v为起点的边上的流量之和。则称f为G的流函数，简称流。定义2中的（1）表示通过边的流量不能超出该边的容量，称为容量约束；（2）表示流进中间点的流量的总和等于流出该点的流量的总和，称为守恒条件。abcst图1-485,25,47,14,33,34,43,2例下图是一个网络流的例子，其中各边的第一个数字表示该边的容量，第二个数字表示该边的流量。

设f是网络G的流，称发点s流出的流量之和为f的值，记为fv，即fv

=f+(s)。

例如图1-48所示的网络流f，有fv=6。割的概念：

设f是G的流，若G中不存在其他流f’，满足f’v

＞fv，则称f为G的最大流。

给定网络G=〈V,E〉，取SV，记=V\S，满足发点s∈S，收点t∈，令（S,）={<x,y>|<x,y>∈E，x∈S，y

∈}称（S,）为G的割。令

c(S,)=称c(S,)为割(S,)的割容量，割容量最小的割称为最小割。ÌSSSSSSåÎ),(),(),(SsyxyxcSS例abcst图1-485,25,47,14,33,34,43,2图1-48中取S={s,a,c}，则S={b,t}，(S,S)={<a,b>，<c,t>}（图中虚线所通过的两条边）。有

c(S,S)=

c(a,b)+

c(c,t)=5+4=9定理25

在任一运输网络中，从发点流出的总量等于收点流进的总量。定理24

网络G中任一流的值不超过该网络的任一割的容量。设f是网络G的一个流，将G视为无向图，Γ为从发点s到收点t的一条路，若Γ中的所有前向边<x,y>（即方向与路中从s到t的方向一致的边）有f(x,y)<

c(x,y)，所有后向边<u,v>有f(u,v)＞0，则称Γ为关于f的可增路。s9,4tdcba10,58,37,26,3上图是将某网络视为无向图时从s到t的一条路，其中边上的第一个数字表示该边的容量，第二个数字表示该边的流量，边<s,a>，<c,d>与<d,t>为前向边，边<b,a>与<c,b>为后向边，并且此路为可增路。设Γ为G的一条可增路，对Γ中的任一条边〈i,j〉，令

δij

=îíì><><-为后向边为前向边jijifjijifjic,),,(,),,(),(

,δ=

min{δij

}例如对上图中的可增路

δ=

min{6-3，2，3，10-5，9-4}=2定理28给定网络G，f

是G的最大流当且仅当G中不存在关于f的可增路。网络最大流的一个算法，称为标号法算法的思想:

对流f（初始时，取f为零流）寻找可增路，若存在，则通过调整路上的值使f增大，再对f重复此过程，直到不存在可增路。定理26

在任一运输网络中，最大流的值等于最小割的容量。算法（1）对任意的<x,y>∈E,置f(x,y)=0，标发点为（s+,∞），令δs

=∞。(2)

若点x已标号，则对与x相邻的未标号的点y，按下法标号：

①<x,y>∈E。当f(x,y)＜c(x,y)时，令

δy

=min{c(x,y)-f(x,y)，δx

}给y标号(x+,δy)；当f(x,y)=c(x,y)时，不给y标号；

②<y,x>∈E。当f(y,x)＞0时，令

δy=min{f(y,

x)，δx}给y标(x