《《图论复习题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论复习题》PPT课件.ppt（123页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章第一章 图和子图图和子图图的基本概念；常见的特殊图类；二部图及其性质；图的基本概念；常见的特殊图类；二部图及其性质；图的同构；关联矩阵与邻接矩阵；路、圈与连通图；图的同构；关联矩阵与邻接矩阵；路、圈与连通图；最短路问题。最短路问题。K-方体图是其顶点为方体图是其顶点为0与与1的有序的有序k元组元组,当且仅当它当且仅当它们的一个坐标不相同时们的一个坐标不相同时,此两个顶点相连以边。证此两个顶点相连以边。证明明k-方体图是有方体图是有2k个顶点个顶点k2k-1条边的条边的2-部图。部图。导出子图和图的运算导出子图和图的运算G2G1G2G1由定理由定理 1.2可知图可知图(a)所示的图不是二分
2、图，因为它所示的图不是二分图，因为它包含一个长为包含一个长为3的圈的圈 ,图图(b)所示的图是一所示的图是一个二分图，它不含长为奇数的圈个二分图，它不含长为奇数的圈.定理定理 一个图是二部图当且仅当它不含奇圈。一个图是二部图当且仅当它不含奇圈。证明：设证明：设 P =v0v1 v k是是G 的最长路。的最长路。因为因为d(v 0)3，所以存在两个与所以存在两个与 v 1相异的顶点相异的顶点v,v 与与 v 0相邻。相邻。v,v必都在路必都在路P 上，否则会得到比上，否则会得到比P 更更长的路。无妨设长的路。无妨设v =v i,v=v j,(i 1时，找一个不连通的单图时，找一个不连通的单图G使
3、得使得证：证：（a）若）若 G 不连通，可分为两个顶点数分别为不连通，可分为两个顶点数分别为v1，v2的互不连通子图的互不连通子图 G1，G2。易知易知于是于是这与这与矛盾！矛盾！（b）G=Kv-1+K1即为所求的单图。即为所求的单图。课后习题：证明在任何两个或两个以上人的组内课后习题：证明在任何两个或两个以上人的组内,存在存在两个人在组内有相同个数的朋友。两个人在组内有相同个数的朋友。证：证：令上述组内人的集合为图令上述组内人的集合为图G的顶点集合，若两人互的顶点集合，若两人互相是相是朋友朋友，则其间，则其间连以一边连以一边，所得之图，所得之图G是组内人员的是组内人员的朋友关系图。显然朋友关
4、系图。显然G是单图，图中是单图，图中顶点的度顶点的度恰表示该人恰表示该人在组内在组内朋友的个数朋友的个数，利用图，利用图G，上述问题就抽象成如下，上述问题就抽象成如下的的图论问题：在一个单图图论问题：在一个单图G中，若中，若v（G）2，则在，则在G中存中存在度相等的两个顶点。在度相等的两个顶点。用用反证法反证法，设，设G中各点的度均不相等。必有最大度中各点的度均不相等。必有最大度v-1。若。若=v-1，必有，必有1，从而，从而-+1v-1,又与又与G是单图矛盾。是单图矛盾。树及其基本性质；最小生成树。树及其基本性质；最小生成树。第二章第二章定理定理 下列命题等价：下列命题等价：（1）G 是树；
5、是树；（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)。逆定理的成立见习题逆定理的成立见习题若还存在一条路若还存在一条路P(u,v)P(u,v)，则必存在，则必存在w，w 是路是路P 与与P 除了除了v 之外最后一个公共顶点。之外最后一个公共顶点。P 的的
6、(w,v)段与段与P 的的(w,v)段构成段构成圈圈，这与，这与G 是树是树矛盾。故只存在唯一的矛盾。故只存在唯一的(u,v)路。路。=1时，时，=0，结论真。，结论真。假设假设 k 时结论真，我们来证明当时结论真，我们来证明当=k+1时，也时，也有有=1成立。成立。当当=k+1时，任取时，任取u,v V(G)。考虑图。考虑图G=G uv，因，因G 中中u、v 间只有一条路，即边间只有一条路，即边uv，故，故G不不（2）（3）若若G 有圈，则此圈上任二顶点间有两条不同的路，有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。与前提条件矛盾。下面用归纳法证明下面用归纳法证明=1。连通且只有两
7、个连通分支，设为连通且只有两个连通分支，设为 G 1,G 2。注意到。注意到 G 1,G 2分别都连通且任二顶点间只有一条路，由归纳法假设分别都连通且任二顶点间只有一条路，由归纳法假设 ，因此因此归纳法完成。归纳法完成。（3）（4）用反证法。若用反证法。若G 不连通，设不连通，设 G 1,G 2,G w是其连通分是其连通分支（支（w 2），则），则 （因（因G i是连通无圈图，是连通无圈图，由已由已证明的证明的(1)和和(2)知，知，对每个对每个G i，(3)成立）。这样，成立）。这样，这与，这与 矛盾。矛盾。（4）（5）(G e)=(G)1=2，但每个连通图必满，但每个连通图必满 足足 1（
8、见下列命题），故图（见下列命题），故图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。证明：对证明：对 做数学归纳法。做数学归纳法。(H)(H v)+1 (k 1)+1 =(k+1)1 =(H)1。若若H v 不连通，不连通，设设 H 1,H 2,H w 是其连通分支是其连通分支由归纳假设，由归纳假设，故故 而而(H)(
9、H v)+w (k w)+w=(k+1)1 归纳法完成。归纳法完成。（w 2）。）。=(H)1。（5）（6）先证先证G 中无圈：若中无圈：若G 中有圈，删去圈上任一边仍连通，中有圈，删去圈上任一边仍连通，矛盾。矛盾。再证再证G+e 恰含一个圈：因恰含一个圈：因G 连通且已证连通且已证G 无圈，故无圈，故G 是树。由（是树。由（2），任二顶点间仅有一条路相连，故），任二顶点间仅有一条路相连，故G+e 中必有一个含有中必有一个含有e 的圈；另一方面，若的圈；另一方面，若G+e 中有两中有两个圈含有个圈含有e，则，则G+e e=G 中仍含有一个圈，矛盾。中仍含有一个圈，矛盾。（6）（1）只需证只需证
10、G 连通。任取连通。任取u,v V(G)，若，若u、v 相邻，则相邻，则u 与与v 连通。否则，连通。否则，G+uv 恰含一个圈，故恰含一个圈，故u 与与v 在在G 中中连通。由连通。由u、v 的任意性，图的任意性，图G 连通。连通。定理证毕。定理证毕。证明：证明：设设T 是一个非平凡树。因是一个非平凡树。因T 连通，故对每个顶点连通，故对每个顶点v i，都有，都有 。若对所有若对所有v i 都有都有 ，则，则另一方面，另一方面，这两方面矛盾。故这两方面矛盾。故T 至少有一个至少有一个1 度顶点，设为度顶点，设为u。除。除此之外，其余此之外，其余 1个顶点的度数之和为个顶点的度数之和为2 3。
11、若这些点的度都大于或等于若这些点的度都大于或等于2，则其度数之和，则其度数之和 2(1)推论推论2.2 非平凡树至少含两个非平凡树至少含两个1 度顶点（叶子）。度顶点（叶子）。=2 2。这与。这与2 3矛盾。故除矛盾。故除u 之外之外T 还至少有一个还至少有一个度为度为1 的顶点。证毕。的顶点。证毕。定义定义 对图对图G，若，若V(G)的子集的子集 使得使得 ，则称则称 为图为图G 的一个顶点割集。含有的一个顶点割集。含有k 个顶点的顶点个顶点的顶点割集称为割集称为k-顶点割集。顶点割集。注：注：（1）割点是）割点是1顶点割集。顶点割集。（2）完全图没有顶点割集。）完全图没有顶点割集。第三章第
12、三章图的连通性；图的连通性；割点、割边和块；边连通与点连通；割点、割边和块；边连通与点连通；连通度。连通度。完全图的连通度定义为完全图的连通度定义为(K)=1。空图的连通度。空图的连通度定义为定义为0。连通度：连通度：(G)=min|是是G 的顶点割集的顶点割集。注：注：(1)使得使得 的顶点割集的顶点割集 称为称为G 的最小的最小 顶点割集。顶点割集。(2)若若(G)k，则称，则称G 为为k 连通的。连通的。(3)若若G 不连通，则不连通，则(G)=0。(4)若若G 是平凡图，则是平凡图，则(G)=0。(5)所有非平凡连通图都是所有非平凡连通图都是1 连通的。连通的。例例v2G1v1v3v4
13、v5v6v7v9v8G2v2v1v3v4v5v8v6v71、分别找、分别找G1和和G2两个顶点割；两个顶点割；2、给出它们的连通度。、给出它们的连通度。例例在在2.2中中 为图为图G 的一个的一个边割集边割集。含有。含有k 条边的边割条边的边割集称为集称为k-边割集。边割集。注：注：(1)对非平凡图对非平凡图G，若，若 是一个边割集，则是一个边割集，则G E 不连通。不连通。使得使得 是是G 的一个边割集，其中的一个边割集，其中 。(2)一条割边构成一个一条割边构成一个1边割集。边割集。对图对图G 的每个边割集的每个边割集 ，必存在非空的，必存在非空的S V(G)，(3)边连通度：边连通度：完
14、全图的连通度定义为完全图的连通度定义为 。空图的连通度定。空图的连通度定义为义为0。注：注：(1)对平凡图或不连通图对平凡图或不连通图G，。(2)若图若图G 是含有割边的连通图，则是含有割边的连通图，则 。(3)若若 ，则称，则称G 为为k边连通的。边连通的。(4)所有非平凡连通图都是所有非平凡连通图都是1边连通的。边连通的。(5)使得使得 的边割集的边割集 称为称为G 的最小边割集。的最小边割集。确定下列给定图类的点连通度和边连通度确定下列给定图类的点连通度和边连通度.由定义我们可以确定对于图的任一点和任意一条边，由定义我们可以确定对于图的任一点和任意一条边，有下列性质成立有下列性质成立定理
15、定理3.1证明：证明：先证先证 。若若G 不连通，则不连通，则 。若若G 是完全图，则是完全图，则 。下设下设G 连通但不是完全图。则连通但不是完全图。则G 有边割集含有有边割集含有 条边。设这个边割集为条边。设这个边割集为 。对。对 中每条边，选取一个端点，去掉这些端点（至多中每条边，选取一个端点，去掉这些端点（至多 个）后，个）后，G 便成为不连通图，故这些端点构成一便成为不连通图，故这些端点构成一个点割集个点割集 ，。因此。因此 。再证再证 。设设d(v)=。删去与。删去与v 关联的关联的 条边后，条边后，G 变成不变成不连通图，故这连通图，故这 条边构成条边构成G 的一个边割集。的一个
16、边割集。因此因此 。证毕。证毕。v2G1v1v3v4v5v6v7v9v8G2v2v1v3v4v5v8v6v7例例1、分别找、分别找G1和和G2两个边割；两个边割；2、给出它们的边连通度。、给出它们的边连通度。G234例例3.2 块块（blockblock）定义：定义：无割点的连通图称为块。无割点的连通图称为块。图的块：若满足下列三条：图的块：若满足下列三条：（1）H 是图是图G 的子图；的子图；（2）H 本身是一个块；本身是一个块；（3）H 是具有此性质的极大子图。是具有此性质的极大子图。则称则称H 是图是图G 的一个块。的一个块。例例注：注：至少有三个顶点的图是块当且仅当它是至少有三个顶点的
17、图是块当且仅当它是2连连 通图。通图。若只有两个顶点，则有反例，例如若只有两个顶点，则有反例，例如 K2是个块，是个块，但不是但不是2 连通的。连通的。定理定理3.2 (Whitney,1932)3的图的图G 是是2连通图连通图（块）当且仅当（块）当且仅当G 中任二顶点共圈。中任二顶点共圈。课后习题课后习题（a）证明：若）证明：若G是单图，且是单图，且则则(b)找一个单图找一个单图G,满足满足解解：（：（a）证：）证：当当时，时，若若不相邻，不相邻，则对任意第三点则对任意第三点都有都有这时，这时，对任意对任意v-3个顶点的子集个顶点的子集V,均有均有G-V 仍连通。仍连通。故故当当 时，时，故
18、故（b）对）对作作易知：易知：v=4时，时，v4时，时，Kv-4中的中的v-4个顶点构成个顶点构成G的顶点割集，故的顶点割集，故再由再由定理定理3.1即得即得课后习题课后习题 证明：若证明：若G为满足为满足的单图，的单图，证：证：在在G中除去任意的中除去任意的k1个顶点，所得之图记为个顶点，所得之图记为G1。则则由练习由练习15知，知，G1连通，连通，从而知从而知G是是k-连通。连通。则则G是是k-连通的。连通的。注注:按定义按定义从而对从而对 k=v 时，时，的情况，即的情况，即G是是Kv的情况，的情况，要相应地把结论中的要相应地把结论中的v-连通换成连通换成(v-1)连通。连通。课后习题课
19、后习题 若若G是是3-正则单图，则正则单图，则 证：证：若若从而至少存在一个分支仅一条边和从而至少存在一个分支仅一条边和v 相相则则不连通，故不连通，故所以所以 若若则存在则存在不连通，由于不连通，由于所以所以设设不连通。不连通。关联。关联。显然这边为显然这边为G的割边，故的割边，故故故G-e2连通。由于连通。由于故故v1是是G-e2的割点的割点,且且另一方面另一方面由定理由定理3.1G1=G-v1连通。则连通。则 v2是是 G1的割点且的割点且类似与类似与知知 在在G1中存在一割边中存在一割边e2(关联于关联于v2)使使 G1-e2不连通不连通。于是类似于于是类似于知，知，在在G-e2中存在
20、一割边中存在一割边e1,即即不连通不连通,故故所以所以由定理由定理3.1知，知，由于由于我们已穷举了我们已穷举了的一切可能情况，故综合上述的一切可能情况，故综合上述,(注：值得注意，在证明过程中仅用到注：值得注意，在证明过程中仅用到 3这条件，这条件，从而对于从而对于3的单图成立的单图成立结论成立。结论成立。第四章第四章欧拉图与哈密尔顿图。欧拉图与哈密尔顿图。欧拉图；中国邮递员问题；欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。哈密尔顿图；旅行商问题。定理定理4.1 一个非空连通图是一个非空连通图是Euler 图当且仅当它没有图当且仅当它没有奇度顶点。奇度顶点。Euler 图的判定图的判定推
21、论推论4.1 一个连通图有一个连通图有Euler 迹当且仅当它最多有两迹当且仅当它最多有两个奇度顶点。个奇度顶点。给定一个由给定一个由16条线段构成的图形条线段构成的图形(见图见图)。证明：不能引一条折线与每一线段恰好相交一次。证明：不能引一条折线与每一线段恰好相交一次。(折折线可以是不封闭的和自由相交的，但它的顶点不在给定线可以是不封闭的和自由相交的，但它的顶点不在给定的线段上，而边也不通过线段的公共端点，即不允许折的线段上，而边也不通过线段的公共端点，即不允许折线从图的缺口处穿过。线从图的缺口处穿过。)例例证明：我们先来建立一个图证明：我们先来建立一个图G。图。图G中的顶点中的顶点xi代表
22、代表这个图形的区域这个图形的区域Xi(i=1,2,3,4,5,6)。顶点。顶点xi与与xj之间之间连接的边数等于区域连接的边数等于区域Xi与与Xj公共线段的数目公共线段的数目(如图所示如图所示)这样建立的图这样建立的图G中的每一条边对应这个中的每一条边对应这个图形的一条线段。存在满足条件的折线图形的一条线段。存在满足条件的折线当且仅当当且仅当G中存在一条中存在一条Euler环游或环游或Euler通路。由于通路。由于G中有四个奇点，故中有四个奇点，故G不存在不存在Euler环游及环游及Euler通路，也即证明了在通路，也即证明了在图形中不能引一条满足要求的折线。图形中不能引一条满足要求的折线。*
23、经过图经过图G 的每个顶点恰一次的路称为的每个顶点恰一次的路称为G 的的Hamilton 路。路。*经过图经过图G 的每个顶点恰一次的圈称为的每个顶点恰一次的圈称为G 的的Hamilton 圈。圈。Hamilton 图的研究起源于十二面体的游戏（图的研究起源于十二面体的游戏（1856）与与Euler 图不同，目前为止尚没有找到判别一个图图不同，目前为止尚没有找到判别一个图是否是是否是Hamilton 图的有效充要条件。这是图论中未解决图的有效充要条件。这是图论中未解决的重要难题之一。的重要难题之一。给出一些经典的充分条件和必要条件。给出一些经典的充分条件和必要条件。定理定理 4.3 若若G 是
24、是H 图，则对图，则对V(G)的每个非空真子集的每个非空真子集S，均有，均有w(GS)|S|。证明：设证明：设C 是是G 的的H 圈，则对圈，则对V(G)的每个非空真子集的每个非空真子集S，均有，均有w(CS)|S|由于由于CS 是是GS 的生成子图，故的生成子图，故w(GS)W(CS)|S|。证毕。证毕。利用定理利用定理4.3可判断下图不是可判断下图不是H 图。图。但定理但定理4.3 不能来判断下列不能来判断下列Petersen 图不是图不是H 图。图。Petersen 图图（1）度型条件）度型条件定理定理4.4 (Dirac,1952)若若G 是简单图，且是简单图，且3，v/2，则则G 是
25、是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 的选择，的选择，Guv 是是Hamilton 图。因图。因G
26、 是非是非Hamilton 图，故图，故Guv 的的H圈必经过圈必经过e=uv。（因为若（因为若 ，则，则G 将包含将包含H圈圈 ，矛盾）。，矛盾）。故故d(u)+d(v)=|S|+|T|=|S T|+|S T|，这，这与与 /2的前提矛盾。证毕。的前提矛盾。证毕。引理引理4.5 （Bondy&Chvtal,1974）设设G 是简单图，是简单图，u 和和v 是是G 中不相邻的顶点，且中不相邻的顶点，且d(u)+d(v)，则，则G 是是Hamilton 图当且仅当图当且仅当Guv 是是Hamilton 图。图。(2)闭包型条件闭包型条件定理定理4.7 一个简单图是一个简单图是Hamilton 图
27、当且仅当它的闭图当且仅当它的闭包是包是Hamilton 图。图。证明：在构作闭包过程中，反复运用引理证明：在构作闭包过程中，反复运用引理4.5 即可。即可。推论推论4.8 设设G 是是3的简单图。若的简单图。若C(G)是完全图，则是完全图，则G 是是Hamilton 图。图。例例 有一个有一个n 人的团体人的团体(n3)，这，这n 个人中互相个人中互相认识的对数认识的对数(两个人认识就算作一对两个人认识就算作一对)至少是至少是1/2(n-1)(n-2)+2.证明这证明这n 个人可以围桌而坐，使每个人与个人可以围桌而坐，使每个人与他相邻座位上的他相邻座位上的2个人认识。个人认识。证明：证明：以顶
28、点代表人，两顶点相邻当且仅当以顶点代表人，两顶点相邻当且仅当2个人互相个人互相认识，则认识，则G是至少有条边的简单图。现在证明是至少有条边的简单图。现在证明G是是Hamilton图。假若不然，则图。假若不然，则G无无Hamilton回路，由回路，由Lemma 4.5知，知，G中存在两个不相邻的顶点中存在两个不相邻的顶点 u 与与 v。使。使因而因而G中至多有中至多有n1 条边关联条边关联 Hamilton回路回路C。现在只需按。现在只需按C的顺序安排人员的顺序安排人员围桌而坐，就能使每个人与相邻座位的两个人认识。围桌而坐，就能使每个人与相邻座位的两个人认识。于于u 和和 v。作作G1=G-u,
29、v，由于，由于u 和和v不相邻，故不相邻，故这与这与相矛盾。所以相矛盾。所以G有有定理定理4.9 设设G 是度序列为（是度序列为（d1,d2,d）的简单）的简单图，这里图，这里 d1 d2 d，并且，并且 3。若不存在小于。若不存在小于2的的m，使得，使得dm m 和和dm m，则，则G 是是Hamilton 图。图。(3)度序列条件度序列条件例例 求下图的最优投递路线，求下图的最优投递路线，A 为邮局。为邮局。解：只有两个奇点，解：只有两个奇点，V=B,E。B 到到E 的最短路为的最短路为BAFE，权为，权为13。完全赋权图。完全赋权图 K2及相应的及相应的Euler 图图G*为为易求得其易
30、求得其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
31、是非是非 Hamilton 图。图。证：证：设设P(u,v)是是 G 中最长路，中最长路，其长度为其长度为l2,则则 G 中有一条长中有一条长度至少为度至少为2的路。的路。按定义按定义故故所以有所以有设设于是我们得到于是我们得到 G 中的一个中的一个 长度为长度为l+1的圈的圈C如下：如下：，则则显显然然P的长度大于的长度大于l，但这又与，但这又与P(u,v)是是 G 中最长路中最长路相矛盾。相矛盾。故故一条路一条路P:P加上路，加上路，由于由于故在故在 C 外恒存在一点外恒存在一点由于由于 G 是连通的，是连通的，所以有一条所以有一条 C 外的路外的路P和和 C 相连，相连，相连，相连，不失
32、一般性，不失一般性，不妨假定和不妨假定和v1于是我们在于是我们在G 中找到中找到第五章第五章匹配问题匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配。匹配与最大匹配；完美匹配；二部图的最大匹配。定义定义 设设G 是一个图是一个图,M E(G),满足满足:对对ei,ej M,ei与与 ej在在G 中不相邻中不相邻,则称则称M 是是G 的一个匹配。的一个匹配。对匹配对匹配M 中每条边中每条边e=uv,其两端点其两端点u和和v称为被匹配称为被匹配M 所匹配所匹配,而而u和和v都称为是都称为是M 饱和饱和的的(saturated vertex)。注注:每个顶点要么未被每个顶点要么未被M 饱和饱和,要
33、么仅被要么仅被M 中一条中一条边饱和。边饱和。定义定义 设设M 是是G 的一个匹配，若的一个匹配，若G 中无匹配中无匹配M，使得，使得|M|M|,则称则称M 是是G 的一个最大匹配；的一个最大匹配；如果如果G 中每个点都是中每个点都是M 饱和的饱和的,则称则称M 是是G 的的完美完美匹配匹配(Perfect matching).213456Matching M261345Matching M显然显然,完美匹配必是最大匹配。完美匹配必是最大匹配。定义定义 设设M 是是G 的一个匹配的一个匹配,G 的的M 交错路是指其边交错路是指其边M 和和E(G)M 中交替出现的路。如果中交替出现的路。如果G
34、的一条的一条M 交交错路错路(alternating path)的起点和终点都是的起点和终点都是M 非饱和非饱和的的,则称其为一条则称其为一条M可扩展路或可扩展路或M 增广路增广路(augmenting path)。P:v5v4v2v1v3 是是 M-alternating。v1v2v3v4v5v6v7v8定理定理 5.1(Berge,1957)图图G 的匹配的匹配M 是最大匹配的是最大匹配的 充要条件是充要条件是G中不存在中不存在M 可扩展路。可扩展路。偶图的对集和覆盖偶图的对集和覆盖定义定义 图图G 的邻集。的邻集。定理定理5.2 (Hall,1935)设设G 是具有二划分是具有二划分(X
35、,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)|N(S)|(G)n/2，且且Y N(S)（因因|N(S)|6=|Y|。由推论。由推论5.2，不存在完美匹配。，不存在完美匹配。引理引理5.3 设设M是对集，是对集，K是覆盖，
36、适合是覆盖，适合|M|=|K|，则，则M是最大对集，且是最大对集，且K是最小覆盖。是最小覆盖。证明：证明：若若M*是最大对集，且是最大对集，且K 是最小覆盖，则由是最小覆盖，则由(5.5)由于由于|M|=|K|，所以，所以 。定理定理5.3 在偶图中，最大对集的边数等于最小覆盖的顶在偶图中，最大对集的边数等于最小覆盖的顶 点数。点数。推论推论1 （k 1）边连通偶数阶）边连通偶数阶k 正则图有完美匹配。正则图有完美匹配。证明：设证明：设G 是命题中所述的是命题中所述的k 正则图。正则图。当当k=1时，结论显然。时，结论显然。以下假定以下假定k 2。设。设S 是是G 的任一个非空顶点集，的任一个
37、非空顶点集，G 1,G 2,Gn 是是G S 的奇分支。令的奇分支。令i=V(G),m i=|e|e是是 Gi 与与S 之间的连边之间的连边|。由于由于 k 1，故，故m i 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,
38、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)是奇数。又由于是奇
39、数。又由于G没有割边，所以没有割边，所以mi1。因此。因此 mi3 for 1i n(3)注：注：有割边的正则图未必有完美匹配，例如：有割边的正则图未必有完美匹配，例如：因因O(G v)=3,故无完美匹配。故无完美匹配。应用：应用：二部图最大匹配二部图最大匹配第第6、7、8章章 染色染色定理定理6.1 设设G 是二部图，则是二部图，则 。定理定理6.2(Vizing 定理，定理，1964)设设G 是无环非空简单是无环非空简单图，则图，则独立集、覆盖集与团独立集、覆盖集与团点独立集、点覆盖集、边覆盖集与团的概念。点独立集、点覆盖集、边覆盖集与团的概念。图的着色问题图的着色问题点着色；边着色；平面
40、图；四色猜想。点着色；边着色；平面图；四色猜想。从而从而 Petersen 图的边色数图的边色数如图所示它是如图所示它是 Petersen 图的一种图的一种 4 边边另一方面另一方面证明证明 Petersen 图是图是 4 边色的。边色的。证：证：由练习，由练习，Petersen 图不是可图不是可 1 因子化的，因子化的，正常着色，故有正常着色，故有 课后习题课后习题 证明：若证明：若 G 是非空正则单图，且是非空正则单图，且v为奇数，则为奇数，则证：因为证：因为v=奇数，故奇数，故G的任一正常的边着色的任一正常的边着色的每一色类最多是的每一色类最多是条边，从而条边，从而又由于又由于G是正则图
41、，从而是正则图，从而故故另一方面由另一方面由 Vizing故故定理知定理知例例支配集、点独立集、点覆盖集与团支配集、点独立集、点覆盖集与团定理定理 若若I 是独立集，则它是极大独立集当且仅当它是是独立集，则它是极大独立集当且仅当它是支配集。支配集。证明：必要性由定理证明：必要性由定理7.1.3 显然。显然。充分性：充分性：设设I 是独立集又是支配集，则对是独立集又是支配集，则对v V(G)I，因，因I 是支配集，是支配集，v 必与必与I 中某顶点相邻。故中某顶点相邻。故Iv不不是独立集。可见是独立集。可见I 是极大独立集。是极大独立集。定理定理 顶点子集顶点子集C 是图是图G 的点覆盖集当且仅
42、当的点覆盖集当且仅当 V(G)C 是是G 的点独立集。的点独立集。证明：证明：C 是图是图G 的点覆盖集的点覆盖集G 的每条边至少有一端的每条边至少有一端在在C 中中 没有两端都在没有两端都在V(G)C 中的边中的边 V(G)C 是点独立集。证毕。是点独立集。证毕。推论推论 C 是图是图G 的极小点覆盖集当且仅当的极小点覆盖集当且仅当V(G)C 是是G 的极大点独立集。的极大点独立集。点覆盖与点独立集的关系：点覆盖与点独立集的关系：推论推论 (G)+(G)=.证明：证明：利用定义，可得利用定义，可得 -=V K ,和和 -=V S 即可证明。即可证明。边独立集与边覆盖集边独立集与边覆盖集定义定
43、义 图图G 的一个的一个匹配匹配M 称为称为G 的一个的一个边独立集边独立集。G 的最大匹配所含的边数称为的最大匹配所含的边数称为G 的边独立数或匹配数，的边独立数或匹配数，记为记为 。边独立数与点边独立数与点覆盖的关系：覆盖的关系：例例 是边覆盖，但不是极小边覆盖。是边覆盖，但不是极小边覆盖。也是极小边覆盖，还是最小边覆盖；也是极小边覆盖，还是最小边覆盖；都是边覆盖，都是边覆盖，推论推论7.2.3 设设G 是二部图且是二部图且 ，则，则 。证明：由于证明：由于 ，而由，而由Konig 定理，定理，(定理定理5.3)得得 故故 。证毕。证毕。定理定理5.3 在偶图中，最大对集的边数等于最小覆盖
44、的顶点数。在偶图中，最大对集的边数等于最小覆盖的顶点数。易证：易证：(G)=1 G=；(G)=2 G是非空二部图；是非空二部图；(G)=(G)G K（3）(C2n+1)=3。（4）(G)3 G含有奇圈。含有奇圈。（5）四色定理：对任何平面图四色定理：对任何平面图G，(G)4。点染色理论的基本问题：给定图点染色理论的基本问题：给定图G，确定，确定(G)的值。的值。顶点着色顶点着色定义定义 设设(G)=k,(k 1)。若对。若对G的任何真子图的任何真子图H，均有均有(H),且令且令d1 ，于是于是由由Brooks定理定理 k，再由定理再由定理1.1 和和定理定理 8.1 有有课后习题课后习题：设：
45、设 G 的的-临界子图记为临界子图记为 H，下面我们分，下面我们分三种情况讨论：三种情况讨论：(1)H 是奇圈。由于是奇圈。由于 G 是连通的非奇圈图，故在是连通的非奇圈图，故在 G 中存在中存在 H 外的边与外的边与 H 相连，所以相连，所以(G)3。另一方面另一方面，故，故(2)H 是完全图是完全图。由于由于 G 的连通性及的连通性及G 不是完全图不是完全图故在故在 G 中存在中存在 H 外的边与外的边与 H相连，所以相连，所以(3)H 既不是奇圈又不是完全图，由练习知既不是奇圈又不是完全图，由练习知,，所以此时所以此时 H 满足命题的条件。满足命题的条件。于是有于是有。即即。所以有所以有
46、综合上述情况，综合上述情况，命题成立。命题成立。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,
47、3的平面嵌入的平面嵌入 因为因为K3,3 不具有长小于不具有长小于4的圈，的圈，G的每个面的度必然的每个面的度必然至少是至少是4。因此由定理。因此由定理9.4,有有即即 于是由定理于是由定理9.5 可以得到可以得到导导致致谬误谬误。推论推论9.3 K3,3 是非平面的是非平面的.例例 说明彼得森图不是平面图。说明彼得森图不是平面图。删去图删去图(a)彼得森图的结点彼得森图的结点b，得到它的一个子图为图，得到它的一个子图为图(b)所示所示H。而。而H同胚于同胚于K3,3，故彼得森图不是平面图。，故彼得森图不是平面图。显然，库拉斯基给出了平面图的充要条件，但用它并不能得出显然，库拉斯基给出了平面图
48、的充要条件，但用它并不能得出判别一个图是否平面图的有效算法。判别一个图是否平面图的有效算法。图所示图所示G和和H的色数是多少？的色数是多少？图图G的色数至少为的色数至少为3，因为顶点，因为顶点a,b 和和c 必须指定为不同必须指定为不同的颜色。为检验是否可以用三种颜色来对的颜色。为检验是否可以用三种颜色来对G着色，指定着色，指定a为红色，为红色，b为蓝色，为蓝色，c为绿色；从而为绿色；从而d必为红色；必为红色；e为绿为绿色，色，f为蓝色；最后，确定为蓝色；最后，确定g为红色。因此为红色。因此G的色数的色数(G)=3。H的色数的色数(H)=4。12345678G723456112,13,14,1
49、5,(2648,58,68,78,37762345212,13,14,1548,58,68,78,37例例2345312,13,14,1548,58,68,78672345414,1548,58,68,786712345515,48,58,68,7867123456 48,58,68,7867123457 68,78671823458 786718234596718第十一章第十一章 网络网络有向图；网络与网络流的基本概念；最大流最小割有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；网络流理论的应用。定理；求最大流的标号算法；网络流理论的应用。(5,8)(4,5)(2,2)
50、(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 使得使得val f val