图论及其算法2008数模课件

1.图论问题的起源

18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB七桥问题的分析

七桥问题看起来不难，很多人都想试一试，但没有人找到答案.后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想.Euler把南北两岸和两个岛抽象成四个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图:SNAB欧拉的结论欧拉指出:一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是:1)图是连通的,即任意两点可由图中的一些边连接起来;2)与图中每一顶点相连的边必须是偶数.由此得出结论:七桥问题无解.欧拉由七桥问题所引发的研究论文是图论的开篇之作,因此称欧拉为图论之父.5.图的广泛应用图的应用是非常广泛的,在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络,如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等.还有许多看不见的网络,如各种关系网,像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等,这些网络都可以归结为图论的研究对象----图.其中存在大量的网络优化问题需要我们解决.还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题.6.基本的网络优化问题基本的网络优化问题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题.图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效.例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上,25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问题就得到了解决.

图的基本概念(2)定义2.邻接结点:关联于同一条边的两个结点.孤立结点:不与任何结点相连接的结点.邻接边:关联于同一顶点的两条边.环:两端点相同的边称为环或自回路.平行边:两个结点间方向相同的若干条边称为平行边或重边对称边:两端点相同但方向相反的两条有向边.图的基本概念(3)定义3

无向图:每条边都是无向边的图.有向图:每条边都是有向边的图.混合图:图中不全是有向边,也不全是无向边的图.平凡图:只有一个孤立结点的图.定义4

多重图:含有平行边的图.简单图:无环且无平行边的图.完全图:任何不同结点之间都有边相连的简单无向图.图的基本概念(4)说明:(1)在简单图中,以x为起点y为终点的边至多有一条,因此,图中的边可直接用顶点对表示,而关联函数就可以直接表示在其边集中,故可简记为G=<V(G),E(G)>.(2)对无向图G,将G中的每条边用两条与e有相同端点对称边e和e’来代替后得到一个有向图D,这样得到的有向图D称为G的对称有向图.由此可见,无向图可视为特殊的有向图.例证明:在任意六个人的聚会上,要么三个曾相识,要么三个不曾相识.证明:用A,B,C,D,E,F代表这六个人,若两人曾相识,则在代表该两人的顶点间连一条红边;否则连一条蓝边.于是,原问题等价于证明所得图中必含有同色三角形.考察某一顶点,设为F.与F关联的边中必有三条同色,不妨设它们是三条红边FA,FB,FC.再看三角形ABC.若它有一条红边,设为AB,则FAB是红边三角形;若三角形ABC没有红边,则其本身就是蓝边三角形.图的运算(一）定义1设与是任何两个图.若且是在上的限制,则称是G的子图,记作,称G为G1的母图.若且V1=V,则称是G的生成子图或支撑子图.设,以V1为顶点,以两端点均在V1中的全体边为边集的G的子图,称为V1的导出子图,记作G[V1].设,以E1为边集,以E1中的边关联的全部顶点集的G的子图,称为E1的导出子图,记作G[E1].

特别,若,则以G-V1表示从G中删去V1内的所有点以及与这些顶点关联的边所得到的子图,若V1={v},常把G-{v}简记为G-v,,类似地,设,G-E1表示在G中删去E1中所有边所得的子图,同样G-{e}简记为G-e.路与连通图(一)定义1设u和v是任意图G的顶点,图G的一条u-v是有限的顶点和边交替序列u0e1u1e2…un-1enun(u=u0,v=un),其中与边ei(1in)相邻的两顶点ui-1和ui正好是ei的两个端点.数n(链中出现的边数)称为链的长度.u(u0)和v(un)称为链的端点,其余的顶点称为链的内部点.一条u-v链,当uv时,称它为开的,否则称为闭的.边互不相同的链称为迹,内部点互不相同的链称为路.注释1.(1)在一条链中,顶点和边可以重复.(2)若G是简单图,G中的链u0e1u1e2…un-1enun还可用结点序列u0u1…un-1un表示.(3)不含边的链(即长度为0)称为平凡链.(4)设W是有向图D中u-v链(迹,路),指定W的方向从u到v.若W中所有边的方向与此方向一致,则称W为D中从u到V的有向链(迹,路).路与连通图(二)定义2.两端点相同的迹(即闭集)称为回.两端点相同的路(即闭路)称为圈或回路.长度为K,奇数,偶数的回(圈)分别称为K,奇,偶回(圈).有向闭迹(闭路)称为有向回(有向圈).路与连通图(四)1.说明:容易验证,结点集V(G)上的顶点间的连通关系是V(G)上的一个等价关系,该等价关系确定V(G)的一个划分{V1,V2,…,Vm},使得当且仅当两个顶点x和y属于同一子集Vi时,x和y才是连通的.Vi在G中的导出子图G[V1],G[V2],…,G[Vm]称为G的连通分支或分支,m称为G的连通分支数,记作W(G)=m.如下图有4个连通分支.

定义4.如果无向图G中每一对不同的顶点x和y都有一条路,即W(G)=1,则称G是连通图,反之称为非连通图.路与连通图(五)引理1非平凡图G是连通图当且仅当对V(G)的每一个非空真子集S,定理3设G是P阶连通图,则悬挂点:度数为1顶点.定理4设连通图G至少有两个顶点,其边数小于顶点数,则此图至少有一个悬挂点.路与连通图(七)定义5设是有向图,,若图D中存在x到y的有向路,称结点x可达结点y.规定x到自身总是可达的.

连通图和二分图(1)定义1如果在图G中删去一个结点x后,图G连通分支数增加,即W(G-x)>W(G),则称结点x为G的割点.如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)>W(G),则称边e为G的割边.定义2没有割点的非平凡连通图称为块.G中不含割点的极大连通子图称为图G的块.定义3如果G的顶点集的一个真子集T满足G-T不连通或是平凡图,则称T为G的一个点割.如果图G的边集的一个真子集S满足G-S不连通或是平凡图,则称S为G的一个边割.定义4设G是连通图,称是G的点割}为G的点连通度或连通度;称是G的边割}为G的边连通度.定理1对一个图G,有是图G的最小顶点度.

图的矩阵表示(1)1.邻接矩阵:设是任意图,其中V={x1,x2,…,xn},E={e1,e2,…,em},则n阶方阵A=(aij)称为G的邻接矩阵.其中aij为图G中以xi为起点且以xj为终点的边的数目.说明1:由定义易知,无向图的邻接矩阵是对称矩阵,而有向图的邻接矩阵未必是对称矩阵.定理1已知有向图,其中V={x1,x2,…,xn},且A=(aij)nn为G的邻接矩阵,则Ak中的i和j列元素aij(k)是图G中从xi到xj且长度为k的有向链的数目.说明2:该定理同样适合无向图,且定理中的链不能改为迹或路.推论1若G是P阶简单图,且G的邻接矩阵为A=(aij),则对G的每一个顶点vi,i=1,2,…,p,有d(vi)=aii(2),其中A2=(aii(2)).定理2已知P(P3)阶图G的邻接矩阵为A,作P阶方阵R=A+A2+…+Ap-1,则图G连通的充分必要条件为R中的每个元素都不为零.2.关联矩阵:设是有向图,且V=,称阶矩阵M=(mij)为有向图D的关联矩阵,其中设是无向图,且V=,称阶矩阵M=(mij)为无向图D的关联矩阵,其中说明3:从关联矩阵可得无向图的一些性质:(1)关联矩阵的每一列只有两个1(每条边只关联两个顶点);(2)关联矩阵的每一行元素之和为对应顶点的度;(3)若某行中元素全为零,则相应顶点为孤立点;(4)重边所对应的列完全相同.3.可达矩阵:设G=<V,E>是无重边有向图,其中V=,称阶矩阵P=(Pij)为G的可达矩阵.其中图的矩阵表示(2)定理2已知P(P3)阶图G的邻接矩阵为A,作P阶方阵R=A+A2+…+Ap-1,则图G连通的充分必要条件为R中的每个元素都不为零.2.关联矩阵:设是有向图,且V=,称阶矩阵M=(mij)为有向图D的关联矩阵,其中图的矩阵表示(3)设是无向图,且V=,称阶矩阵M=(mij)为无向图D的关联矩阵,其中说明3:从关联矩阵可得无向图的一些性质:(1)关联矩阵的每一列只有两个1(每条边只关联两个顶点);(2)关联矩阵的每一行元素之和为对应顶点的度;(3)若某行中元素全为零,则相应顶点为孤立点;(4)重边所对应的列完全相同.欧拉图(1)定义1给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2)欧拉路是迹(边互不重复),但不是严格意义上的路.定理1连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.欧拉图与哈密顿图(2)定理2连通图G具有欧拉路而无欧拉回路,当且仅当G恰有两个奇数度顶点.定义2给定有向图D,经过D中每边一次且仅一次的有向迹称为D的有向欧拉路.经过D中每边一次且仅一次的有向闭迹(回),称为有向欧拉回路.欧拉图与哈密顿图(3)定理3具有弱连通性的有向图G具有有向欧拉回路,当且仅当G的每个结点的入度等于出度.具有弱连通性的有向图G具有有向欧拉路,当且仅当在G中,一个结点的入度比出度大1,另一个结点的入度比出度小1,而其余每个结点的入度等于出度.定义3含有欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图,统称为欧拉图.求Euler图的Euler回路的Fleury算法.(1)任意选取一个顶点v0,置W0=v0;(2)假定迹(若是有向图,则是有迹)Wi=v0e1v1…eivi已经选出,则用下列方法从E(G)-{e1,e2,…,ei}中取ei+1;(a)ei+1与vi关联(若是有向图,ei+1以vi为起点)(b)除非没有别的边可选择,ei+1不是Gi=G-{e1,e2,…,ei}的割边.(3)当(2)不能执行时,停止.否则让i+1→i,转(2).(以p46为例)定理4若G是Euler图,则Fleury算法终止时得到的迹是Euler回路。定义1给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路.定义2给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路.若存在一条闭路经过图G的每个结点一次且仅一次,这条有向闭路称为哈密顿有向回路.哈密顿图(1)哈密顿图(1)定义3具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图.例1对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.哈密顿图(3)定理1设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y)n,则G是哈密顿图.定理2设u和v是n阶图G的不同非邻接点,且deg(u)+deg(v)n,则G+边{u,v}是哈密顿图当且仅当哈密顿图.定义4给定n阶图G,若将图G度数之和至少是n的非邻接点用一条边连接起来得图G’,对图G’重复上述过程,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G).定理3一个图是哈密顿图当且仅当它的闭包是哈密顿图.定理4设G是阶至少为3的图,如果G的闭包是完全图,则G是哈密顿图.定理5如果G是一个n阶(n3)任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图.说明:由哈密顿图的定义可知,哈密顿图有向图必是强连通的,哈密顿无向图必无割点.8.哈密顿图(4)定理5若G是一个哈密顿图,则对于V(G)的每个非空真子集S,其中W(G-S)为G-S的分支数.

9.哈密顿图(5)说明:定理6只是一个必要条件,如下的皮特森图,尽管有但它不是哈密顿图.

10.哈密顿图(6)应用定理5若G是一个n(n3)阶任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图.例1.11个学生要共进晚餐,他们将坐成一个圆桌,计划要求每次晚餐上,每个学生有完全不同的邻座.这样能共进晚餐几次.分析:如何将该问题转化成图论中的相关问题.实际上,可以这样来构造一个图,即以每个学生看作图的顶点,以学生的邻座关系作为图的边,11.哈密顿图(7)这样学生每次进餐的就坐方式就对应一个哈密顿回路.两次进餐中,每个学生有完全不同的邻座对应着两个没有公共边的哈密顿回路.因为每个学生都可以与其余学生邻座,故问题转化为在图K11中找出所有没有公共边的哈密顿回路的个数.K11中共有条边,而K11中每条哈密顿回路的长度为11,因此K11中最多有55/11=5条没有公共边的哈密顿回路,构造方法为:设第一条哈密顿回路为(1,2,3,…,11,1),将1固定在圆心,其余固定在圆周上,如图(1)所示,然后将图的顶点旋转i×3600/10(i=1,2,3,4),从而就得到另外4个哈密顿回路.12.哈密顿图(8)

1

(3,2,4,6)57(5,3,2,4)

(2,4,6,8)39(7,5,3,2)

(4,6,8,10)211(9,7,5,3)

(6,8,10,11)410(11,9,7,5)(8,10,11,9)68(10,11,9,7)图1

1第五节最短路路问题1.加权图:边上有数的图称为加权图;该数称为边的权。2.最短路问题:如何求两个结点之间的最短路.3.迪克斯曲拉算法:这是荷兰计算机科学教授EdsgerW.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项.迪克斯曲拉算法是求出一个连通加权简单图中从结点a到结点z的最短路.边{i,j}的权(i,j)>0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.4.迪克斯曲拉算法流程ProcedureDijkstra(G:所有权为正的加权连通简单图){G带有顶点a=v0,v1,…,vn=z和权w(vi,vj),若{vi,vj}不是G中的边,则w(vi,vj)=)Fori:=1tonL(vi):=L(a):=0S:={初始化标记,a的标记为0,其余结点标记为,S是空集}WhilezSbeginu:=不属于S的L(u)最小的一个顶点S:=S{u}For所有不属于S的顶点vIfL(u)+w(u,v)<L(v)thenL(v):=L(u)+w(u,v){这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记}End{L(z)=从a到z的最短路的长度}.例1.用迪克斯曲拉算法求下图所示的加权图中顶点a与z之间最短路的长度.（见65页）a4b5d2110c8e263z定理1迪克斯曲拉算法求出连通简单无向图的中两点之间的最短路的长度。定理2迪克斯曲拉算法使用O(n2)次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间的最短路的长度。迪克斯曲拉算法可以推广到求加权有向图的最短路。定理3设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路，那么式（2）有唯一有限解。.Floyd算法Dijkstra算法只求出一个特定顶点到其他各顶点的最短路.但在许多实际问题中,需求出任意两点之间的最短路,如全国各城市之间最短的航线,选址问题等.Floyd算法可以比较好地解决这一问题.为介绍Floyd算法,先定义矩阵的两种运算.定义1已知矩阵A=(aij)ml,B=(bij)ln,规定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,…,ail+blj).定义2已知矩阵A=(aij)mn,B=(bij)mn,规定D=A⊗B=(dij)mn,其中dij=min(aij,bij).可以利用上面定义的运算求任意两点间的最短距离.

已知n阶加权简单图G,设D=(dij)nn是图G的边权矩阵即dij=w(i,j)(若G是有向图,则dij=w<i,j>),若结点i到结点j无边相连时,则取dij=.然后依次计算出矩阵D[2],D[3],…,D[n]及S,其中D[2]=DD=(dij[2])nnD[3]=D[2]D=(dij[3])nn,……,D[n]=D[n-1]D=(dij[n])nnS=D⊗D[2]⊗D[3]⊗…D[n]=(Sij)nn

由定义可知,dij[k]表示从结点i到结点j经k边的路(在有向图中即为有向路)中的长度最短者.这就是Floyd算法.Floyd算法的时间复杂度为O(n4).v121v27v6v41332v6例2.利用Floyd算法求下图中任意两点间最短有向路的长度.(p71-73)Warshall算法D=(dij)为图G的边权矩阵(1)输入D(2)k：=1；(3)i：=1；(4)dij:=min(dij,dik+dkj),j=1,2,…,n(5)i：=i+1,若i≤n,转(4);(6)k：=k+1,若k≤n,转(3);否则停止。实质上是考虑经过n次结点转换每一次保留最短路的长度。举例见P74.旅行推销员问题和中国投递员问题（NPC问题）

一、旅行推销员问题

（最邻近算法给出旅行推销员问题的近似解）步骤如下（1）由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。（2）以表示最新加到这条路上的结点，从不在路上的所有结点中选一个和最靠近的结点，把连接与这一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。例1用“最邻近算法”给出下面加权图中有充分小权的哈密顿路P76.AFBECD16697151312183513182119说明:“最邻近插入方法”是“最邻近法”的一种改进方法.该方法是在每次迭代中都构成一个闭的旅行路线.求解时,在已经建立旅程以外的顶点中,寻找最临近于旅程中某个顶点的顶点,然后将其插入该旅程中,并使增加的距离尽可能小,当全部顶点收入这个旅程后,就找到了所求的最短哈密顿回路的近似解.例2用“最邻近插入方法”找出上图中具有充分小权的哈密顿回路.定理1设P是加权连通图G中一条包含G的所有边至少一次的闭链，则P最优的充要条件（具有最小长度）是：（1）P中无二重以上的边；（2）在G的每个圈中C中，重复边集E的长度之和不超过这个圈的长度的一半，即W(E)1/2W(C).二.中国邮路问题奇偶点作业法（1）把G中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中无奇度顶点，即G1为多重欧拉图.（2）若G1中某对结点间有多于两条边连接，则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由2条边连接。得到图G2.（3）检查G2的每个圈C，若某个圈C上重复边集E的权和超过这个圈的权和的一半，则将C按定理1必要性证明中的方法进行调整，直到对G2所有的圈其重复边的权和不超过此圈权和的一半，得到图G3.（4）用Fleury算法求G的Euler回路.例3求下图G的最优环游p81.v1v2v3v4v5v6v7v8v9v10v11v1224553646465447938AV12v104v95v8V26v114v126v7554477V39

v43

v58

v6B4455447799

8864636C446466654444793836D44

433

455364666642树的基本概念定义1树是无圈连通无向图.树中度数为1的结点称为树的叶.树中度数大于1的结点称为树的分枝点或内点.不相交的若干树称为森林,即森林的每个连通分枝是树.定义2设T是有向图,若T的基础图是树,称T是有向树.定义3仅一个结点的入度为0,其余所有结点的入度都为1的有向树称为根树.入度为0的结点称为根.出度为0的结点(度数为1的结点)仍称为叶;出度不为0的结点称为分枝点或内点.由根到某一顶点v的有向路的长度,称为v的层数.根树的高度就是顶点层数的最大值.支撑树定义1若T是G的一个生成子图且又是一棵树,则称T是图G的一棵生成树或支撑树.生成树T中的边称为T的树枝,不在生成树T中的G的边,称为树T的弦.定理1图G有生成树G为连通图.求连通简单图的生成树

深度优先搜索和广度优先搜索深度优先搜索:任意选择图G的一个顶点为根,通过不断地增加边来形成以顶点v0为起点的路,直到这条路经过图G的每个顶点,此时得到的这条路就是该图的生成树.其中每条新边都与路上的一个顶点以及不在路上的一个顶点关联.如果这条路不经过图G的所有顶点,则返回倒数第二个顶点,继续重复上面过程,直到不能添加更多的边为止.又图G是有有限边数的连通图,故最后总能产生一棵生成树.例1用深度搜索来找出下图G的生成树abcdefghijk广度优先搜索基本思想:从图的顶点中任意地选择一个根,然后添加与该顶点相关联的所有边,在这个阶段添加的新顶点成为生成树里1层上的顶点,任意地排序它们.下一步,按顺序访问1层上的每一个顶点,只要不产生回路,就添加与这个顶点相关联的每条边,这样就产生了树里2层上的顶点.遵循这样的原则继续下去,经有限步骤后(因为图中只有有限条边)就产生了生成树.例2.用广度优先搜索找出例1中图G的生成树.P106最小支撑树定义1:连通加权图里权和最小的支撑树称为最小支撑树.最小支撑树的实际应用背景:在某一国家或地区,需建造一铁路网/公路网把一些城市连接起来,需要总长度最短或造价最低.寻找最小支撑树的贪心算法原理:通过添加还没使用过的具有规定性质且权最小的边来进行的,其实质就是在每步上进行最优选择,即“局部最优化”.

普林算法算法的基本思想:首先选择带最小权的边,把它放进支撑树里.相继向树里添加带最小权的边,这些边与已在树里的顶点相关联,并且不与已在树里的边形成圈,直到添加了n-1条边止.算法描述如下:算法1普林算法Procedureprim(G:带n个顶点的连通无向图)T:=权最小的边Fori:=1ton-2begine:=与T里顶点相关联的权最小的边,并且若添加到T里则不形成圈T:=添加e之后的Tend{T是G的最小支撑树}例1用普林算法求下图所示的最小支撑树定理1普林算法是正确的,即在算法结束时,得到一棵最小支撑树.(证略)1745102616158abcgfde克鲁斯卡尔(Kruskal)算法算法的基本思想:选择图中最小的一条边,相继添加不与已经选择的边形成圈的权最小的边,直到挑选n-1(n为结点的个数)条边为止.该算法的伪代码如下:ProcedureKruskal(G:n个顶点的连通加权无向图)T:=空图.Fori:=1ton-1beginE:=当添加到T里时不形成圈的G里权最小的边T:=添加e之后的TEnd{T是G的最小支撑树}定理2由Kruskal算法构作的任何生成树T=G[e1,e2,…,en-1]都是G的最小生成树,n为G的结点数.基于破圈法的最小生成树的生成方法该方法是由管梅谷教授给出的,其基本思想为:设G是连通加权简单图,若G不是树,则G中必含有回路,删去G中含于某回路内权最大的一条边,所得的图记为G1,G1是G的连通生成子图.下一步,若G1不是树,又从G1某个回路内删去权最大的一条边,如此下去,最后不能按上述方式删边时,得到的图T便是G的一棵生成树.定理3由破圈法最后得到的图T为G的一棵最小生成树.平面图的着色定义1设G是无孤立结点的连通的平面图，且G有K个面F1，F2，…Fk(包括外部面).则按下列过程作G的对偶图G.（1）在G的每个面内设置一个结点vi(1ik)。（2）过Fi与Fj的每一条公共边ek作一条仅作一条边{vi,vj}与ek相交。（3）当且仅当ek只是Fi的边界时，vi恰有一自回路与ek相交。这样所得的图G*称为图G的对偶图.若G*与G同构,称G是自对偶的.如下图G的对偶图为图中虚线.12341324定义2图的着色是对该图的每个顶点都指定一种颜色，使没有两个相邻的顶点指定为相同的颜色。如果这些顶点选自于一个有k种颜色的集合，而不管k种颜色是否都用到，这样的着色称为k着色。定义3图G的色数是着色这个图G所需要的最少颜色数。记作(G)。图G的色素也称为图G的点色素.从定义可知,对于G的任何子图H,均有x(H)x(G).若G是n阶完全图,若G是n阶完全图,则x(G)=n;若G是至少有一边的二分图,则x(G)=2;若G是长为奇数的圈,则x(G)=3.当x(G)3时,G的特征至今尚未清楚,在下一节,将给出G的色素x(G)的一个上界.定理1设u和v是图G中两个不相邻的顶点,则(G)=min{(G+{u,v}),(G•{u,v})},其中G•{u,v}是把G中结点u与v重合成一个新结点，且G中分别与u与v关联的边都与该新结点关联。四色问题:连通简单平面图的色素不超过4.四色问题是盖思里于1852年提出,后经众多数学家尝试证明,均以失败告终.1976年,美国数学家阿佩尔和黑肯宣布借助用计算机证明,但时间超过了1000小时,其可靠性仍在置疑之中.例1求下图G和H的色数acfgbedGHa:红,b:蓝,c:绿,d:红,e:绿，f:蓝,g:红(3色)定理2（五色定理）连通简单平面图G的色数为不超过5.例2.由n(n3)个顶点v1,v2,…,vn以及边{v1,v2},{v2,v3},…,{vn-1,vn}{vn,v1}组成的图称为圈图,记作Cn,试问圈图的Cn的色数是多少。（分n为奇数，或偶数）例3.Kn和Km,n的色数分别是多少？解:由于Kn的每两个顶点都相邻,而当两个相邻的顶点必指定不同的颜色,故Kn的色素为n.Km,n的色数为2.用一种颜色着色m个顶点,用另一种颜色着色n个顶点.第五节图着色的应用贮藏问题:某工厂生产n种化学制品c1,c2,…,cn,其中某些制品是互不相容.若它们相互接触,则会发生化学反应甚至引起爆炸,为安全起见,该工厂必须把仓库分成若干隔间,以便把不相容的化学制品储藏在不同的隔间,试问该仓库至少应分成几个隔间?解:构建简单图G=<V,E>,其中V(G)={c1,c2,…,cn}边{ci,cj}E(G)化学制品ci与cj互不相容.易知,仓库的最少隔间数等于图G的色素x(G).电视频道分配问题某地区内有n家电视发射台T1,T2,…,Tn.主管部门为每家电视发射台分配一个频道.为排除干扰,使用同一频道的电视台之间的距离必须大于指定的正数d,试问该地区至少需要多少频道?构建简单图G=<V,E>,其中V(G)={T1,T2,…,Tn}边{Ti,Tj}E(G)Ti与Tj之间距离d.易知,需要的最少频道等于图G的色素x(G).考试安排问题某高校有n门选修课程v1,v2,…,vn需要进行期末考试.同一学生不能在同一天里参加两门课程的考试.问学校的期末考试需要几天?构建简单图G=<V,E>,其中V(G)={v1,v2,…,vn}边{vi,vj}E(G)vi与vj被同一同学选修.故考试需要的最小天数等于图G的色素x(G).顺序着色算法

到目前为止,还没有一个有效算法来确定色素.顺序着色算法是一个求x(G)的有效算法:设G=<V,E>是简单无向图，V={x1,x2…xn}用N(xi)表示与xi相邻的全部顶点集合；对顶点xi着色C，记为(xi)=C.i:=1c:=1若对yN(xi),(y)C,则令(xi)=C并转入第5步。C:=C+1并转入第3步。若i<n，则i:=i+1并转回第2步，否则停止.例1试用顺序着色法求图G的色数。1211212121321211321212132121定理1设G是简单连通图，顺序着色法产生G的顶点的一个(G）+1着色，所以(G)（G）+1定理1给出了连通简单图G的色数的上界.1941年R.L.Brooks证明了下面的定理.定理2设G是一个连通简单图,其顶点的最大度为.若G既不是完全图Kn,也不是奇数圈图Cn,则x(G).边着色定义1图G的边着色对G的每一条边都指定一个颜色，使得没有两个相邻的边都为同一种颜色。如果这些颜色都取自一个有K种颜色的集合，而不管这K种颜色是否都用掉，这样的边着色称为K—边着色。定义2图G的边着色数是着色这个图G需要的最少颜色数。记为’(G).边着色转化为点着色的方法：

边着色可以转化为相应的点着色,即在边着色图中,将所有的边对应地转化成点着色图中的结点,结点转化成相应的边.因此,由点着色性质定理不难得到如下定理.定理1若G是非空连通的简单图，G的最大顶点度为,则’(G)+1。（不证）定义3.图G的不同K—着色的数目，称为图G的色多项式。记作f(G,k).说明:(1)若k<x(G),此时k-着色不存在,显然有f(G,k)=0,从而即知,满足f(G,k)>0的最小的k即为G的色数.(2)设mi是i种颜色对图G的顶点进行着色的不同方案数.用k(ki)种颜色对图G进行着色,每取i种颜色时,共有miCki种不同的着色方案,故有:f(G,k)=m1Ck1+m2Ck2+…+mnCkn,其中n为图G的顶点数.显然,f(G,k)是k的多项式.图的两种基本运算:(1)Guv设u,v是图G的不邻接的两个顶点,把u,v收缩成一个顶点x,并把G中凡与u,v关联的边均使之与x关联,这样所得的新图。记作Guv.(2)G:e把图G的一条边删去并使它的两个端点重合,也即边e被收缩.这样得到的新图。记作G:e.定理3.设u,v是G的两个不相邻的顶点，则f(G,k)=f(G+{u,v},k)+f(G:uv,k)说明:定理3表明,若G是有P个顶点和q条边的图,则有一个q+1条边的图G1=G+{u,v}(u与v不相邻接)和一个有P-1个顶点的图G2=Guv,使f(G,k)=f(G1,k)+f(G2,k).对G1和G2依次类推,直到只出现完全图为止.因此,一个图的色多项式f(G,k)是f(Kn,k)型的表达式的和.完全图的色多项式例1.对三阶完全图K3而言,有f(K3,k)=k(k-1)(k-2).解:由于对K3中的任何指定一个顶点,可以用k种颜色中的任何一种进行着色;对K3的第二个顶点,可以用k-1种颜色中的任何一种进行着色;对K3的第三个顶点,可以用k-2种颜色中的任何一种进行着色.一般地,对于P阶完全图，有f(Kp,k)=k(k-1)(k-2)…(k-p+1)例1三阶完全图K3有f(K3,k)=k(k-1)(k-2)例2求图G的色多项式。f(G,k)=K5+3K4+K3=k(k-1)(k-2)(k-3)(k-4)+3k(k-1)(k-2)(k-2)(k-3)+k(k-1)(k-2)=k5-7k4+18k3-20k2+8k匹配匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想.定义1.设G=<V,E>是无环图,ME(G),M,若M中任意两条边都不相邻,则称M是图G的一个匹配.若对图G的任何匹配M’,均有M’<M,则称M是图G的最大匹配,记作’(G).定义2.设M是图G的匹配,G中与M中的边关联的顶点称为M饱和点.若图G的顶点都是M饱和,则称为G的完美匹配.说明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定义与边的方向无关,故匹配是针对无向图而言.(3)图G的边不交匹配的最小数目即为G的边色数.定义3.(可增广路):设M是图G的匹配,P是G的一条路,且在P中,M的边和E(G)-M的边交替出现,则称P是G的一条交错路.若M交错路P的两个端点为M非饱和点,则称P为M可增广路.例1.求下图G的一条交错路和一条可增广路.62341587匹配的几个性质定理定理1.设M1和M2是图G的两个不同匹配,由M1M2导出的G的边导出子图记作H,则H的任意连通分支是下列情况之一:(1)边在M1和M2中交错出现的偶圈.(2)边在M1和M2中交错出现的路.定理2.M是图G的最大匹配,当且仅当G中不存在M可增广路.

定义:NG(S):设S是图G的任意顶点子集,G中与S的顶点邻接的所有顶点的集合,称为S的邻集,记做NG(S).定理3(Hall定理,1935)设G是有二部划分(V1,V2)的二分图,则G含有饱和V1的每个顶点的匹配M的充要条件是,对SV1,有N(S)S.推论1具有二部划分(V1,V2)的二分图G有完美匹配V1=V2,且对SV1(或V2),有N(S)S.推论2.设G是k(>0)正则二分图,则G有完美匹配.推论3.设G是二部划分(V1,V2)的简单二分图,且V1=V2=n,若(G)n/2,则G有完美匹配.定理4.G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇数阶连通分支数目.例1.有n张纸牌,每张纸牌的正反两面都写上1,2,…n的某一个数,证明:如果每个数字恰好出现两次,则这些纸牌一定可以这样摊开,使朝上的面中1,2,…n都出现.证明:作一个二分图G=<V1,V2,E>,其中V1={1,2,…,n},V2={y1,y2,…,yn}表示这n张纸牌.i与yi之间连接的边数等于数i在纸牌yj中出现的次数,这样得到的图G是一个2-正则二分图,因此图G中有完美匹配,设为M={1yi1,2yi2,…,nyin}

则只要把纸牌yi1中的1朝上,yi2中的2朝上,…,yin的n朝上,这样摊开,这样摊开的纸牌就能使上面中1,2,…,n都出现.例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该厂所生产的双色布中,每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布,它们含有所有的6种颜色.(从匹配方面思考)第五节最大匹配的生成算法-匈牙利算法定义1.根在x的M交错子图:设M是图G的匹配,x是G中非M饱和点.G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在x的M交错子图.定理1.设M是具有二部划分(V1,V2)的二分图G的匹配,xV1是非M饱