图论复习题课件

第一章图和子图图的基本概念；常见的特殊图类；二部图及其性质；图的同构；关联矩阵与邻接矩阵；路、圈与连通图；最短路问题。K-方体图是其顶点为0与1的有序k元组,当且仅当它们的一个坐标不相同时,此两个顶点相连以边。证明k-方体图是有2k个顶点k2k-1条边的2-部图。导出子图和图的运算G2G1G2G1由定理1.2可知图(a)所示的图不是二分图，因为它包含一个长为3的圈,图(b)所示的图是一个二分图，它不含长为奇数的圈.定理一个图是二部图当且仅当它不含奇圈。证明：设P=v0v1…v

k是G的最长路。因为d(v0)≥3，所以存在两个与v1相异的顶点v′,v"与v0相邻。v′,v"必都在路P上，否则会得到比P更长的路。无妨设v′

=vi

,v"=vj,(i<j)。若i,j中有奇数，比如i是奇数，则路P上v0到vi的一段与边v0v

i构成一个偶圈；若i,j都是偶数，则路P上vi到vj的一段与边v0

vi

及v0vj构成一个偶圈。证毕。例设G是简单图，若δ(G)≥3,则G必有偶圈。图中两点的连通：如果在图G中u，v两点有路相通，则称顶点u，v在图G中连通。连通图：图G中任二顶点都连通。图的连通分支：若图G的顶点集V(G)可划分为若干非空子集V1,V

2,…,Vω

，使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图G[Vi]为图G的一个连通分支（i=1,2,…,ω）。V1112921865129734136971V1V2V3V4V5V6V7V8V9V10240∞∞∞∞∞∞∞∞∞∞应用：最短路问题算法实现－标号法课后习题（a）G是单图且证明G连通.（b）v>1时，找一个不连通的单图G使得证：（a）若G不连通，可分为两个顶点数分别为v1，v2的互不连通子图G1，G2。易知于是这与矛盾！（b）G=Kv-1+K1即为所求的单图。用反证法，设G中各点的度均不相等。必有最大度△≥v-1。若△=v-1，必有δ≥1，从而△-δ+1<v,这与各点度均不等矛盾!若△>v-1,又与G是单图矛盾。树及其基本性质；最小生成树。第二章定理下列命题等价：（1）G是树；（2）G中无环边且任二顶点之间有且仅有一条路；（3）G中无圈且ε=ν−1；（4）G连通且ε=ν−1;（5）G连通且对任何e∈E(G)，G−e不连通；（6）G无圈且对任何e∈E(G)，G+e恰有一个圈。证明：（1）⇒（2）G是树⇒G连通⇒∀u,v∈V(G)，存在路P(u,v)。逆定理的成立见习题2.1.1若还存在一条路P′(u,v)≠P(u,v)，则必存在w，w是路P与P′除了v之外最后一个公共顶点。P的(w,v)段与P′的(w,v)段构成圈，这与G是树矛盾。故只存在唯一的(u,v)路。连通且只有两个连通分支，设为G1,G2

。注意到G1,G2分别都连通且任二顶点间只有一条路，由归纳法假设，因此归纳法完成。（3）⇒（4）用反证法。若G不连通，设G1,G2,…,Gw是其连通分支（w≥2），则（因Gi是连通无圈图，由已证明的(1)和(2)知，对每个Gi

，(3)成立）。这样，，这与矛盾。（4）⇒（5）ε(G−e)=ε(G)−1=ν−2，但每个连通图必满足ε≥ν−1（见下列命题），故图G−e不连通。ν=1,2时，ε≥ν−1显然成立。假设ν≤k的连通图都ε≥ν−1。对于ν=k+1的连通图H，任取v∈V(H)，考虑H−v。若H−v连通，则由归纳假设，ε(H−v)≥ν(H−v)−1=k−1，而命题若图H连通，则ε(H)≥ν(H)−1。证明：对ν做数学归纳法。（5）⇒（6）先证G中无圈：若G中有圈，删去圈上任一边仍连通，矛盾。再证G+e恰含一个圈：因G连通且已证G无圈，故G是树。由（2），任二顶点间仅有一条路相连，故G+e中必有一个含有e的圈；另一方面，若G+e中有两个圈含有e，则G+e−e=G中仍含有一个圈，矛盾。（6）⇒（1）只需证G连通。任取u,v∈V(G)，若u、v相邻，则u与v连通。否则，G+uv恰含一个圈，故u与v在G中连通。由u、v的任意性，图G连通。定理证毕。证明：设T是一个非平凡树。因T连通，故对每个顶点vi，都有。若对所有vi都有，则另一方面，这两方面矛盾。故T至少有一个1度顶点，设为u。除此之外，其余ν−1个顶点的度数之和为2ν−3。若这些点的度都大于或等于2，则其度数之和≥2(ν−1)推论2.2非平凡树至少含两个1度顶点（叶子）。定义

对图G，若V(G)的子集使得，则称为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。注：（1）割点是1－顶点割集。（2）完全图没有顶点割集。第三章图的连通性；割点、割边和块；边连通与点连通；连通度。完全图的连通度定义为κ(Kν)=ν−1。空图的连通度定义为0。连通度：

κ(G)=min{|||是G的顶点割集}。注：(1)使得的顶点割集

称为G的最小顶点割集。(2)若κ(G)≥k，则称G为k连通的。

(3)若G不连通，则κ(G)=0。

(4)若G是平凡图，则κ(G)=0。

(5)所有非平凡连通图都是1连通的。在§2.2中为图G的一个边割集。含有k条边的边割集称为k-边割集。注：(1)对非平凡图G，若是一个边割集，则G\E′不连通。使得是G的一个边割集，其中。(2)一条割边构成一个1－边割集。对图G的每个边割集，必存在非空的S⊂V(G)，(3)边连通度：完全图的连通度定义为。空图的连通度定义为0。注：(1)对平凡图或不连通图G，。(2)若图G是含有割边的连通图，则。(3)若

，则称G为k－边连通的。(4)所有非平凡连通图都是1－边连通的。(5)使得的边割集

称为G的最小边割集。确定下列给定图类的点连通度和边连通度.由定义我们可以确定对于图的任一点和任意一条边，有下列性质成立定理3.1证明：先证。若G不连通，则。若G是完全图，则。下设G连通但不是完全图。则G有边割集含有条边。设这个边割集为

。对中每条边，选取一个端点，去掉这些端点（至多个）后，G便成为不连通图，故这些端点构成一个点割集

，。因此。再证。设d(v)=δ。删去与v关联的δ条边后，G变成不连通图，故这δ条边构成G的一个边割集。因此。证毕。v2G1v1v3v4v5v6v7v9v8G2v2v1v3v4v5v8v6v7例1、分别找G1和G2两个边割；2、给出它们的边连通度。G234例3.2块（block）定义：

无割点的连通图称为块。图的块：若满足下列三条：（1）H是图G的子图；（2）H本身是一个块；（3）H是具有此性质的极大子图。则称H是图G的一个块。例注：至少有三个顶点的图是块当且仅当它是2－连通图。

若只有两个顶点，则有反例，例如K2是个块，但不是2连通的。定理3.2(Whitney,1932)ν≥3的图G是2－连通图（块）当且仅当G中任二顶点共圈。课后习题（a）证明：若G是单图，且则(b)找一个单图G,满足解：（a）证：当时，若不相邻，则对任意第三点都有这时，对任意v-3个顶点的子集V′,均有G-V′仍连通。故当时，故（b）对作易知：v=4时，v>4时，Kv-4中的v-4个顶点构成G的顶点割集，故再由定理3.1即得课后习题证明：若G为满足的单图，证：在G中除去任意的k－1个顶点，所得之图记为G1。则由练习15知，G1连通，从而知G是k-连通。则G是k-连通的。注:按定义从而对k=v时，的情况，即G是Kv的情况，要相应地把结论中的v-连通换成(v-1)连通。课后习题若G是3-正则单图，则证：①若从而至少存在一个分支仅一条边和v相则不连通，故所以②若则存在不连通，由于所以③设不连通。关联。显然这边为G的割边，故故G-e2连通。由于故v1是G-e2的割点,且另一方面由定理3.1G1=G-v1连通。则v2是G1的割点且类似与②知在G1中存在一割边e2(关联于v2)使G1-e2不连通。于是类似于②知，在G-e2中存在一割边e1,即不连通,故所以④由定理3.1知，由于我们已穷举了的一切可能情况，故综合上述,(注：值得注意，在证明过程中仅用到△≤3这条件，从而对于△≤3的单图成立结论成立。第四章欧拉图与哈密尔顿图。欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。定理4.1一个非空连通图是Euler图当且仅当它没有奇度顶点。Euler图的判定推论4.1一个连通图有Euler迹当且仅当它最多有两个奇度顶点。给定一个由16条线段构成的图形(见图)。证明：不能引一条折线与每一线段恰好相交一次。(折线可以是不封闭的和自由相交的，但它的顶点不在给定的线段上，而边也不通过线段的公共端点，即不允许折线从图的缺口处穿过。)例证明：我们先来建立一个图G。图G中的顶点xi代表这个图形的区域Xi(i=1,2,3,4,5,6)。顶点xi与xj之间连接的边数等于区域Xi与Xj公共线段的数目(如图所示)这样建立的图G中的每一条边对应这个图形的一条线段。存在满足条件的折线当且仅当G中存在一条Euler环游或Euler通路。由于G中有四个奇点，故G不存在Euler环游及Euler通路，也即证明了在图形中不能引一条满足要求的折线。*经过图G的每个顶点恰一次的路称为G的Hamilton路。*经过图G的每个顶点恰一次的圈称为G的Hamilton圈。Hamilton图的研究起源于十二面体的游戏（1856）与Euler图不同，目前为止尚没有找到判别一个图是否是Hamilton图的有效充要条件。这是图论中未解决的重要难题之一。

给出一些经典的充分条件和必要条件。定理4.3若G是H图，则对V(G)的每个非空真子集S，均有w(G－S)≤|S|。证明：设C是G的H圈，则对V(G)的每个非空真子集S，均有w(C－S)≤|S|由于C－S是G－S的生成子图，故w(G－S)≤W(C－S)≤|S|。证毕。利用定理4.3可判断下图不是H图。但定理4.3不能来判断下列Petersen图不是H图。Petersen图（1）度型条件定理4.4(Dirac,1952)若G是简单图，且ν≥3，δ≥v/2，则G是Hamilton图。令A={G|G的顶点数为ν≥3，δ≥ν/2，且G是非Hamilton图}。取A中边最多的一个G。因ν≥3，故不是完全图（否则G是Hamilton图）。设u和v是G的不相邻顶点。充分条件证明:用反证法：假定定理不真。于是G中存在以u为起点v为终点的Hamilton路v1v2…vν。这里v1=u，vν=v，令和由于故,并且由G的选择，G＋uv是Hamilton图。因G是非Hamilton图，故G＋uv的H圈必经过e=uv。（因为若，则G将包含H圈，矛盾）。故d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T|<ν，这与δ≥ν/2的前提矛盾。证毕。引理4.5（Bondy&Chvátal,1974）设G是简单图，u和v是G中不相邻的顶点，且d(u)+d(v)≥ν，则G是Hamilton图当且仅当G＋uv是Hamilton图。(2)闭包型条件定理4.7一个简单图是Hamilton图当且仅当它的闭包是Hamilton图。证明：在构作闭包过程中，反复运用引理4.5即可。推论4.8设G是ν≥3的简单图。若C(G)是完全图，则G是Hamilton图。

例

有一个n人的团体(n≥3)，这n个人中互相认识的对数(两个人认识就算作一对)至少是1/2(n-1)(n-2)+2.证明这n个人可以围桌而坐，使每个人与他相邻座位上的2个人认识。证明：以顶点代表人，两顶点相邻当且仅当2个人互相认识，则G是至少有条边的简单图。现在证明G是Hamilton图。假若不然，则G无Hamilton回路，由Lemma4.5知，G中存在两个不相邻的顶点u与v。使因而G中至多有n－1条边关联

Hamilton回路C。现在只需按C的顺序安排人员围桌而坐，就能使每个人与相邻座位的两个人认识。于u和v。作G1=G-{u,v}，由于u和v不相邻，故这与相矛盾。所以G有定理4.9设G是度序列为（d1,d2,…,dν

）的简单图，这里d1≤d2≤…≤dν，并且ν≥3。若不存在小于ν／2的m，使得dm

≤m和dν−m

<ν−m，则G是Hamilton图。(3)度序列条件例求下图的最优投递路线，A为邮局。解：只有两个奇点，V′={B,E}。B到E的最短路为BAFE，权为13。完全赋权图K2及相应的Euler图G*为易求得其Euler环游，并得到最优回路。应用：中国邮递员问题课后习题证明：若(a)G不是2-连通的，或(b)G是二部圈，且它的二部划分(X,Y)有|X|

≠|Y|，则G是非Hamilton图。证：(a)若G不是2-连通的，则G不连通或存在割点v有由定理4.3知G是非Hamilton图。且|X|<|Y|，(b)设G是2-部图，其划分为(X，Y)，则有由定理4.3知G是非Hamilton图。证：设P(u,v)是G中最长路，其长度为l<2δ,路P(u,v)中的顶点依次为故和u,v相邻的顶点均在路上．由于G是单图，从而若令课后习题若G是连通单图，且v>2δ,则G中有一条长度至少为2δ的路。按定义故所以有设于是我们得到G中的一个长度为l+1的圈C如下：，则显然P″的长度大于l，但这又与P(u,v)是G中最长路相矛盾。故一条路P″:P′加上路，由于故在C外恒存在一点由于G是连通的，所以有一条C外的路P′和C相连，相连，不失一般性，不妨假定和v1于是我们在G

中找到第五章匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配。定义

设G是一个图,M⊆E(G),满足:对∀ei,ej∈M,ei与ej在G中不相邻,则称M是G的一个匹配。对匹配M中每条边e=uv,其两端点u和v称为被匹配M所匹配,而u和v都称为是M

饱和的(saturatedvertex)。注:每个顶点要么未被M饱和,要么仅被M中一条边饱和。定义设M是G的一个匹配，若G中无匹配M'

，使得|M'

|>|M|,则称M是G的一个最大匹配；如果G中每个点都是M饱和的,则称M是G的完美匹配(Perfectmatching).

213456MatchingM261345MatchingM'显然,完美匹配必是最大匹配。定义设M是G的一个匹配,G的M交错路是指其边M和E(G)\M中交替出现的路。如果G的一条M交错路(alternatingpath)的起点和终点都是M非饱和的,则称其为一条M可扩展路或M增广路(augmentingpath)。P:v5v4v2v1v3是M-alternating。v1v2v3v4v5v6v7v8定理5.1(Berge,1957)图G的匹配M是最大匹配的充要条件是G中不存在M可扩展路。偶图的对集和覆盖定义

图G的邻集。定理5.2(Hall,1935)设G是具有二划分(X,Y)的二部图，则G有饱和X的匹配当且仅当对∀S⊆X，|N(S)|≥|S|，其中N(S)表示S的所有邻点之集。推论5.5设G=(X，Y)是二部图，且X=Y=n。若δ(G)≥n/2，则G有完美匹配。证明(用反证法)：若G没有完美匹配，则由推论5.2，存在S⊆X,S≠φ，使|N(S)|<|S|。因G是二部图且δ(G)≥n/2，故|S|>|N(S)|≥δ(G)≥n/2，且Y\N(S)≠φ（因|N(S)|<|S|≤|X|=|Y|）。令u∈Y\N(S)，则N(u)⊆X\S，因此，这与条件矛盾。故G有完美匹配。证毕。例下图所示的是14个大小相同的正方形组成的图形。试证明：不论如何用剪刀沿着图形中所画的直线对它进行裁剪，总剪不出7个由相邻的两个小正方形组成的矩形来。证明：将图形中方格从1到14编号。以方格为顶点集作简单图G=(V,E)，边ij∈E(G)当且仅当i、j所在的方格在图形中相邻（有公共边）。注意G中每条边对应于原图形中由相邻两个小正方形组成的矩形，故剪出7个矩形相当于在G中求由7条边组成的匹配。由于有14个顶点，故所求的是完美匹配。但这样的匹配是不存在的。事实上，G是一个二部图，其二划分为X={1,3,4,6,9,11,12,14}，Y={2,5,7,8,10,13}。|X|=8>6=|Y|。由推论5.2，不存在完美匹配。引理5.3

设M是对集，K是覆盖，适合|M

|=|K|，则M是最大对集，且K是最小覆盖。证明：若M*是最大对集，且K'是最小覆盖，则由(5.5)由于|M

|=|K|，所以。定理5.3

在偶图中，最大对集的边数等于最小覆盖的顶点数。推论1（k−1）边连通偶数阶k正则图有完美匹配。证明：设G是命题中所述的k正则图。当k=1时，结论显然。以下假定k≥2。设S是G的任一个非空顶点集，G1,G2,…,Gn

是G\S的奇分支。令νi

=V(G),mi=|{e|e是Gi

与S之间的连边}|。由于κ′≥k−1，故mi≥k−1,(i=1,2,…,m)。完美匹配定理5.4(Tutte,1947)图G有完美匹配的充分必要条件是对∀S⊂V(G)，O(G\S)≤|S|。若存在i，使得m

i=k−1

，则因从而因此，但因νi−1是偶数（每个Gi是奇分支），上式两端不可能相等。这个矛盾说明mi≥k（i=1,2,…,n)，于是由Tutte定理，G有完美匹配。证毕。(1)证明：设G是没有割边的3-正则图，S是V的真子集，用

G1,G2,…,Gn表示G-S的奇分支，并设mi

是一个端点在S中的那些边的条数。由于G是3正则的，所以并且(2)推论5.4(Peterson,1891)２－边连通（无割边）的３正则图有完美匹配。由(3)和(2)可得所以由定理5.4，G有完美匹配。由(1)是奇数。又由于G没有割边，所以mi≠1。因此mi≥3for1≤i≤n(3)注：有割边的３正则图未必有完美匹配，例如：因O(G−v)=3,故无完美匹配。应用：二部图最大匹配第6、7、8章染色定理6.1设G是二部图，则。定理6.2(Vizing定理，1964)设G是无环非空简单图，则独立集、覆盖集与团点独立集、点覆盖集、边覆盖集与团的概念。图的着色问题点着色；边着色；平面图；四色猜想。从而Petersen图的边色数如图所示它是Petersen图的一种4–边另一方面证明Petersen图是4–边色的。证：由练习5.1.5，Petersen图不是可1–因子化的，正常着色，故有课后习题证明：若G是非空正则单图，且v为奇数，则证：因为v=奇数，故G的任一正常的边着色的每一色类最多是条边，从而又由于G是正则图，从而故另一方面由Vizing故定理知例支配集、点独立集、点覆盖集与团定理7.1.4若I是独立集，则它是极大独立集当且仅当它是支配集。证明：必要性由定理7.1.3显然。充分性：设I是独立集又是支配集，则对∀v∈V(G)\I，因I是支配集，v必与I中某顶点相邻。故I∪{v}不是独立集。可见I是极大独立集。定理7.1.7顶点子集C是图G的点覆盖集当且仅当

V(G)\C是G的点独立集。证明：C是图G的点覆盖集⇔G的每条边至少有一端在C中⇔没有两端都在V(G)\C中的边⇔V(G)\C是点独立集。证毕。推论7.1.3

C是图G的极小点覆盖集当且仅当V(G)\C是G的极大点独立集。点覆盖与点独立集的关系：推论7.1.4

α(G)+β(G)=ν.证明：利用定义，可得-=V\K,和

-=V\S即可证明。边独立集与边覆盖集定义图G的一个匹配M称为G的一个边独立集。G的最大匹配所含的边数称为G的边独立数或匹配数，记为。边独立数与点覆盖的关系：例是边覆盖，但不是极小边覆盖。也是极小边覆盖，还是最小边覆盖；都是边覆盖，推论7.2.3设G是二部图且，则。证明：由于，而由Konig定理，(定理5.3)得故。证毕。定理5.3

在偶图中，最大对集的边数等于最小覆盖的顶点数。易证：χ(G)=1⇔G=

；χ(G)=2⇔G是非空二部图；χ(G)=ν(G)⇔G⊇Kν（3）χ(C2n+1)=3。（4）χ(G)≥3⇔G含有奇圈。（5）四色定理：对任何平面图G，χ(G)≤4。点染色理论的基本问题：给定图G，确定χ(G)的值。顶点着色定义8.1.4设χ(G)=k,(k≥1)。若对G的任何真子图H，均有χ(H)<k，则称G是临界k色图。图的顶点染色问题可以归结为求图的独立集，它的顶点集至少能划分成多少个点不交的独立集？（2）Grótzsch图是临界4色图；（1）G是临界1色图⇔G≅K1

；G是临界2色图⇔G≅K2

；G是临界3色图⇔G是奇圈；Grötzschgraphis4-critical(1958)（3）任何k色图都包含一个临界k色子图；（4）每个色临界图都是连通的。定理8.1.1色临界图的顶点割集不是团。推论8.1.1

每个色临界图都是块（即不含割点，亦即2连通）。推论8.1.2若临界k色图G有2顶点割集{u,v}，则u与v不相邻。定理8.1.2(Dirac,1952)设G是临界k色图（k≥2），则边连通度κ′(G)≥k-1。推论8.1.3设G是临界k-色图，则δ(G)≥k−1。推论8.1.4任何k色图至少有k个顶点的度≥k−1。推论8.1.5对任何简单图G，χ(G)≤Δ(G)+1。定理8.1.3(Brooks，1941)设G是连通的简单图，且G既不是奇圈又不是完全图，则χ(G)≤Δ(G)。解：因Peterson图G含有奇圈，故不是二部图，因而χ(G)≥3；另一方面，G既不是奇圈又不是完全图，且Δ(G)=3,故χ(G)≤Δ(G)=3。因此，χ(G)=3。例：求Peterson图的色数。8.1.9(a)证明：若u,v是临界图G的两个顶点，则N(u)不是N(v)的子集；(b)证明：不存在k+1个顶点的k–临界图G。证：(a)若，由于，故，所以u,v不相邻。又因G是k–临界

图,故对G-u存在(k-1)—正常着色。若在此基础上令u和v着同色，则最后得到G课后习题上的一个(k-1)—正常着色，于是，这和G是k–色图相矛盾，故(b)若这样G存在，由定理8.1知，。另一方面显然故在G中存在两个不N(u)不是N(v)的子集.相邻的顶点v1,v2,由于及，故但这与(a)相矛盾，故结论成立。8.2.1证明：Brooks定理等价于下述命题：若G是k–临界(k≥4)，且不是完全图，则。证：＝＞：由于k≥4，故G不可能是奇圈，由假设G不是完全图，故△>δ,且令d1＝△，于是由Brooks定理△≥k，

再由定理1.1和定理8.1有课后习题＜＝：设G的-临界子图记为H，下面我们分三种情况讨论：(1)H是奇圈。由于G是连通的非奇圈图，故在G

中存在H外的边与H相连，所以△(G)≥3。另一方面，故(2)H是完全图。由于G的连通性及G不是完全图故在G中存在H外的边与H相连，所以

(3)H既不是奇圈又不是完全图，由练习8.1.7知,，所以此时H满足命题的条件。于是有。即。所以有综合上述情况，命题成立。v1*v2*v3*v4*bacdefgh设平面图G有n个顶点，m条边，d个面，分别为S1，S2，…，Sd，在每个Si面放置一个顶点vi*，如果Si和Sj面相邻，则用(vi*,vj*)连接(vi*点和vj*点，使(vi*,vj*)与面Si和Sj的公共边只相交一次，且G的其它边界无交点。这样得到的图G*称为G的对偶图。平面图证明假定K3,3是平面的，令G是K3,3的平面嵌入因为K3,3不具有长小于4的圈，G的每个面的度必然至少是4。因此由定理9.4,有即于是由定理9.5可以得到导致谬误。推论9.3

K3,3是非平面的.例说明彼得森图不是平面图。删去图(a)彼得森图的结点b，得到它的一个子图为图(b)所示H。而H同胚于K3,3，故彼得森图不是平面图。显然，库拉斯基给出了平面图的充要条件，但用它并不能得出判别一个图是否平面图的有效算法。图所示G和H的色数是多少？图G的色数至少为3，因为顶点a,b和c必须指定为不同的颜色。为检验是否可以用三种颜色来对G着色，指定a为红色，b为蓝色，c为绿色；从而d必为红色；e为绿色，f为蓝色；最后，确定g为红色。因此G的色数(G)=3。H的色数(H)=4。12345678G723456Ĝ1{12,13,14,15},(26}{48,58,68,78},{37}762345Ĝ2{12,13,14,15}{48,58,68,78},{37}例2345Ĝ3{12,13,14,15}{48,58,68,78}672345Ĝ4{14},{15}{48,58,68,78}6712345Ĝ5{15},{48,58,68,78}6712345Ĝ6{48,58,68,78}6712345Ĝ7{68},{78}67182345Ĝ8{78}67182345Ĝ96718第十一章网络有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；网络流理论的应用。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2网络D及其一个流vs为发点(源)，vt为收点(汇)，其余点为中间点。对每条弧(vi

,vj)，有弧的容量cij

，弧的流量fij，常记做(fij

,cij

).

定义3设F是网络G的一个流，其源为a，汇为z，称值为流F的值，记作val(F)。

定义4设f是网络N的最大流，如果不存在流f′使得valf′>valf

。

网络的割集有多个，其中割集容量最小者称为网络的最小割集容量(简称最小割)。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2割集(S,S)中所有始点在S，终点在S的弧容量之和称为(S,S)的割集容量(割量)。记作因此，若能找到一个可行流f，一个割集(S,S)，使得成立则f必是最大流，而(S,S)是最小割。推论11.1显然，对于网络的任意一个可行流f和割(S,S)，成立定理11.2一个可行流f={fij}，称fij=

cij的弧为饱和弧，称fij<cij的弧为不饱和弧.

fij=

0的弧为零流弧，fij>

0的弧为非零流弧.(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2饱和弧零流弧不饱和弧设P是网络D的一条连接源点vs和汇点vt的链，定义链P的方向是从vs到vt，前向弧—弧的方向与P的方向一致；全体记为P

+.后向弧—弧的方向与P的方向相反；全体记为P

-.则P中的弧可分为两类：f是一个可行流，P是从vs到vt的一条链，如果(1)P的每一前向弧都是不饱和弧（）;(2)P的每一后向弧都是非零流弧（）；则称P是网络D的关于可行流f的一条增广链。简称增广链。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2增广链P：

定理11.3：设f是网络D上的一个可行流，则f是一个最大流当且仅当网络D不存在f的增广链。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2增广链P：8528796653vsv1vtv4v3v2算例：求下面网络的最大流.(0,8)(0,5)(0,2)(0,8)(0,7)(0,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(1)给网络赋一个初始0流f0；给vs标号(-,∞);(-,∞)(a)对弧(vi,vk),若,则给vk

标号(+vi,l(vk)),其中(b)对弧(vk,vi),若,则给vk

标号(-vi,l(vk)),其中标号过程1(+vs,8)(+vs,2)(+v1,5)(+v3,2)(+v2,5)找到流f0的增广链P0