(课件)图论讲义

1图论与网络流理论（GraphTheoryandNetworkFlowTheory）讲授：高随祥中科院研究生院专业基础课学时/学分：60/3本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。2内容提要第一章图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。路、圈与连通图；昀短路问题。树及其基本性质；生成树；昀小生成树。第二章图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。第三章匹配问题匹配与昀大匹配；完美匹配；二部图的昀大匹配；指派问题与昀大权匹配。第四章欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。第五章支配集、独立集、覆盖集与团支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。第六章图的着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。第七章网络流理论有向图；网络与网络流的基本概念；昀大流昀小割定理；求昀大流的标号算法；昀小费用流问题；昀小费用昀大流；网络流理论的应用。主要参考书[1]J.A.BondyandU.S.Murty,Graphtheorywithapplications,1976,有中译本（吴望名等译）。[2]B.Bollobas,Moderngraphtheory(现代图论)，科学出版社，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）边的端点（endvertices）（5）环边(loop)（6）重边(multiedge)（7）简单图(simplegraph)v5e1e2e3e4e5e6e7v1v2v3v4v4e1e2e3e4e5e6e7v1v2v3v54（8）完全图(completegraph)（9）图的顶点数（图的阶）ν、边数ε（10）顶点v的度(degree)：d(v)=顶点v所关联的边的数目（环边计两次）。（11）图G的昀大度：)}(|)(max{)(GVvvdGG∈=∆图G的昀小度：)}(|)(min{)(GVvvdGG∈=δ（12）正则图(regulargraph)：每个顶点的度都相等的图。（13）图的补图(complement)：设G是一个图，以)(GV为顶点集，以)}(),(|),{(GEyxyx∉为边集的图称为G的补图，记为G。定理1.1.1ε2)()(=∑∈GVvvd证明：按每个顶点的度来计数边，每条边恰数了两次。推论1.1.1任何图中，奇度顶点的个数总是偶数（包括0）。4.子图子图(subgraph)：如果)()(GVHV⊆且)()(GEHE⊆，则称图H是G的子图，记为GH⊆。生成子图(spanningsubgraph):若H是G的子图且()()VHVG=，则称H是G的生成子图。点导出子图(inducedsubgraph)：设)(GVV⊆′，以V′为顶点集，以两端点均在V′中的边的全体为边集所组成的子图，称为G的由顶点集V′导出的子图，简称为G的点导出子图，记为][VG′.边导出子图(edge-inducedsubgraph)：设)(GEE⊆′，以E′为顶点集，以两端点均在E′中的边的全体为边集所组成的子图，称为G的由边集E′导出的子图，简称为G的边导出子图，记为][EG′.5.路和圈途径(walk)：图G中一个点边交替出现的序列kkiiiiiiveevevwL2110=。迹(trail)：边不重的途径。路(path):顶点不重复的迹。（注：简单图中的路可以完全用顶点来表示，kiiivvvPL10=）闭途径（closedwalk）：起点和终点相同的途径。闭迹(closedtrail)：起点和终点相同的迹，也称为回路（circuit）.圈(cycle):起点和终点相同的路。5注：（1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度。（2）简单图G中长度为奇数和偶数的圈分别称为奇圈(oddcycle)和偶圈(evencycle)。（3）对任意)(,GVyx∈，从x到y的具有昀小长度的路称为x到y的昀短路（shortestpath），其长度称为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更长的路。无妨设)(,,jivvvvji=′′=′。若ji,中有奇数，比如i是奇数，则路P上0v到iv的一段与边ivv0构成一个偶圈；若ji,都是偶数，则路P上iv到jv的一段与边ivv0及jvv0构成一个偶圈。证毕。例1.1.4设G是简单图，若3)(≥Gδ,则G中各个圈长的昀大公因数是1或2。证明：由上例知，G中有长分别为1,1++ji和2+−ij的圈。若1,1++ji，2+−ij三数有公因数2m，则)(|jim−，于是2|m，这是不可能的。因此1,1++ji，2+−ij三数的公因数必不超过2。从而各个圈长的昀大公因数是1或2。证毕。6.二部图二部图(bipartitegraph)：若图G的顶点集可划分为两个非空子集X和Y，使得任一条边都有一个端点在X中，另一个端点在Y中，则称G为二部图（或偶图），记为G＝),(EYXU，),(YX称为G的一个划分。完全二部图(completebipartitegraph)：在二部图),(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中连通。连通图（connectedgraph）：图G中任二顶点都连通。图的连通分支（connectedbranch,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.图的同构由前已知，同一个图有不同形状的图示。反过来，两个不同的图也可以有形状相同的图示。比如：可见1G和2G的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是同构的(isomorphic)。从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。定义1.1.1两个图))(),((GEGVG=与))(),((HEHVH=，如果存在两个一一映射：)()(:HVGV→α，)()(:HEGE→β，使得对任意)(),(GEvue∈=，都有)())(),((HEvu∈αα且=)(eβ))(),((vuαα，则称图G与H同构。记为HG≅.9.图的矩阵表示（1）关联矩阵=)(GM⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛νεννεεενmmmmmmmmmeeevvvLLLLLLLLM2122221112112121，其中ijm表示顶点iv与边je关联的次数。（2）邻接矩阵=)(GA⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛vvvaaaaaaaaavvvvvvνννννLLLLLLLLM2122221112112121，其中ija表示顶点iv与jv相邻的次数。v1v2v3v4e1e3e2e4e5e6a4u1a1a2a3u2u3u4a6a5u1u2u3u4a1a3a2a4a5a6G1G28例1.1.7⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=0211000100110000001111010011)(GM，⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=1101101101021120)(GA。可见：（1）