一、图论的发展Euler研究了这一游戏问题,他将四块陆地视为四个结点,七座小桥成为连接四个结点的连线.形成了最早研究的一类图论问题——Euler图问题.2.环游世界问题(1856年)有人用一个十二面体代表地球,它上面的二十个顶点代表世界上的二十个大城市,三十条棱,表示连接二十个大城市的路径.二、图论的基本概念与同一条边相关联两个顶点称为相邻的;相关联与同一个顶点的两条边称为相邻的.两个顶点重合为一点的边称为环;图G的邻接矩阵是一个nn矩阵A=(aij)nn,其中aij是连接顶点vi与vj的边的数目.次为奇数的顶点称为奇点,否则称为偶点.一、路,回路,连通二部图(偶图):图G=(V,E),如果顶点集合V可以被划分为两个不相交的非空子集S,T,即S∩T=,S∪T=V,且对任意的边uvE,则uS,vT.二、最短路问题Stop0.S0={u0},v0S0,i=0,P(u0)=0,vS0,T(v)=+(其中P为永久标号,T为临时标号,故此算法也称为标号法).Stop1.vSi,记T(v):=min{T(v),P(uj)+w(uj,v),ujSi}计算P0=min{T(v),vSi},记达到P0值的顶点(如果多于一个,则任取其一)v=ui+1,且P(ui+1)=P0.Step2.若i=n-1或v0Si+1,则终止;否则令Si+1=Si∪{ui+1},i:=i+1,返回Step1.应用举例:设备更新问题.161.T(v2)=min{T(v2),P(v1)+w(v1,v2)}=16;T(v3)=min{T(v3),P(v1)+w(v1,v3)}=22;T(v4)=min{T(v4),P(v1)+w(v1,v4)}=30;T(v5)=min{T(v5),P(v1)+w(v1,v5)}=41;T(v6)=min{T(v6),P(v1)+w(v1,v6)}=59;2.T(v3)=min{T(v3),P(v2)+d(v2,v3)}=min{22,16+16}=22;T(v4)=min{T(v4),P(v2)+d(v2,v4)}=min{30,16+22}=30;T(v5)=min{T(v5),P(v2)+d(v1,v5)}=min{41,16+30}=41;T(v6)=min{T(v6),P(v2)+d(v1,v6)}=mon{59,16+41}=57;16有向图最短路问题的0-1线性规划模型:§3树与最小支撑树问题(5)若T无回路,且在任意两点间添加一条边,则T被含有一个且仅一个回路.(6)图T中任意两点之间有且仅有一条路可达.避回路法:从图G=(V,φ)及任一点v1V开始,作V1={v1}.选取边e=vivjEk,满足viVk且vjVk,则令Ek+1=Ek∪{e},Vk+1=Vk∪{vj},直到第n步,即Vn=V为止.则T=(V,En)为所求.第0步:任取一点v1,作V1={v1},E1=φ,给v1标号(0,0).第1步:在Vk中寻找满足边e=vivjEk,viVk,vjVk且第2标号最小的结点之一vi(p,q),如果存在,则给vj标号(i,q+1),转第2步;否则终止.第2步:令Vk+1=Vk∪{vj},Ek+1=Ek∪{e}.若Vk+1=V,则终止;否则转第1步.v2三、最小支撑树算法若在第2步结束,则图G的一个最小支撑树T=(V,En)已经找到,否则可以证明图G不连通.V3={v1,v5,v6},E2={v1v6,v6v5},W(V2)=7.v2§4Euler图和Hamilton图在Euler图中寻找Euler回路的原则是不得选割边.实际上只需在两个奇点之间添加一条路径即可使这两个奇点改为偶点,而路径经过的点奇偶性不变.由奇点个数为偶数的性质,如此可将图改为不含奇点的图.但增加了许多添加边.例如:此算法不是好算法:这是由于回路的数量是相当多且不易搜索.定理7:G为简单图,且|V|=n3,若(G)n/2,则图G是Hamilton图.§5匹配(边无关集)由此定理可知:若要寻找图G的一最大匹配,关键是寻找当前匹配M的可扩路.若找到一条可扩路P,则M=E(P)M为G的一个匹配且|M|>|M|+1.当对某一个匹配M*,若其没有可扩路,即M*为G的一个最大匹配.寻找M的可扩路算法:匈牙利树的特点为有奇数个点,且仅有一个非饱和点.v1u3v1§6网络最大流问题通过画出网络的基础有向图,并在每条弧上标出它的容量来描述一个网络.二、最大流定理记发点的净流出量为v(f),即对于网络N=(V,A,c),f={fij}为一可行流.若fij=cij,则称弧vivj为饱和流,否则称为非饱和流;若fij=0,则称弧vivj为零流,否则称为非零流.若P是从vs到vt的一条路(非