《图论模型及其应用》由会员分享，可在线阅读，更多相关《图论模型及其应用（44页珍藏版）》请在金锄头文库上搜索。
1、Konigsberg9S|S|S1.121.1GV(G)GE(G)V(G)&V(G)GV(G)&V(G)V(G)V(G)&V(G)=(ab)|abV(G).V(G)E(G)Gn(G)m(G)G1G=V(G)=1234E(G)=(12)(23)(34)(13)(34)(22)(14)1G1-111-11G(1)()2-()1G(2)(vivj)ekek=(vivj)vivjekek1Ge21Ge5e6(3)vivjeiejekviviek(4)V(G)ek=vivjekDAG()()(5)Gw:E(G)RRwew(e)e1.2GvV(G)vGdG(v)(Gd(v)Gv()21G2443d(v)=
2、0vd(v)=1vd(v)vd(v)vkkGvV(G)v()d+(v)=d+G(v)(d(v)=dG(v)Gv()vd(v)=dG(v)()2()1)1.1G=PvVd(v)=2|E|2GPvVd+(v)=PvVd(v)=|E|1.1Gd(v)=dG(v)v1.3HGHGV(H)V(G)E(H)E(G)HGHGHGH6=GHGHGV(H)=V(G)G=VVEEVGGVVGVEGEEGEG=VVEEGV=GVVGVGEGEGEGEE()1.4GGP=v0e1v1e2v2elvlv0vlvr1vrerr=12lv0vlPPlPGPPv0=vlPPPPv0=vlPPPP3()P12vr1ervrer
3、r=12l1.5GuwV(G)Guw(uw)-)uw(uw)-G(uw)-uwGxyd(xy)=dG(xy)xy()()Gp(G)GGVGVk-kVV=vv1(1.7)Gmin|V|VGGn(G)1k-k1-EE=eeeGp(Ge)p(G)1.2GeGeGGe=(uv)GGeGe(uv)-PPeGeeGCGeGeeCeGe(Ge)p(G)=p(Ge)eG211141.6G=V=v1v2vnE=e1e2emmijviejmij=1viejej2viejej0viej(mij)nmGM(G)Gmij=1viej1viej0viejG=V=v1v2vnaijvivj(aij)nnGA(G)Gaijv
4、ivj21GM(G)=1001001121000000111100000111A(G)=01111110110210201.75(1)nKn1993B-(2)G=VXYEXYG(XY)(XY)xXyY(xy)|X|=m|Y|=nKmn1.3GGG(XY)Gv0e1v1e2v2e3v3e4v4e5v0G5v0Xv1Yv2Xv3Yv4Xv0Yv0XGGvV(G)X=xV(G)|d(vx)Y=yV(G)|d(vy)XYVvXGe=(uw)XYeGuwXvuPvwQvPuwQvG()GXY2(3)1.4Tm(T)=n(T)11.2T1T221.2().Tx1.11.42(n1)=2m=PvV(T)d(
5、v)x+2(nx)x2262.342.1(computabledecidable)(uncomputableundecidable)102.2()()nn2.1fgckxk|f(x)|c|g(x)|f(x)O(g(x)f(x)=O(g(x)f(x)=O(g(x)g(x)=O(f(x)f(x)g(x)f(x)=(g(x)1f(x)=x2+100 x+1000O(x2)x1x2+100 x+1000x2+100 x2+1000 x2=1101x2k=1c=11012.1f(x)=anxn+an1xn1+a1x+a0a0a1anf(x)=O(xn)7x1|f(x)|=|anxn+an1xn1+a1x
6、+a0|an|xn+|an1|xn1+|a1|x+|a0|=xn(|an|+|an1|1x+|a1|1xn1+|a0|1xn)xn(|an|+|an1|+|a1|+|a0|)k=1c=|an|+|an1|+|a1|+|a0|f(x)|cxnf(x)=O(xn)22.2f1(x)=O(g1(x)f2(x)=O(g2(x)g1(x)=O(g2(x)f1(x)+f2(x)=O(g2(x)c1c2k1k2xk1|f1(x)|c1|g1(x)|xk2|f2(x)|c2|g2(x)|g1(x)=O(g2(x)c3k3|g1(x)|c3|g2(x)|xk3xk=max(k1k2k3)|f1(x)+f2(x)
7、|f1(x)|+|f2(x)|c1|g1(x)|+c2|g2(x)|c1c3|g2(x)|+c2|g2(x)|=c|g2(x)|c=c1c3+c2f1(x)+f2(x)=O(g2(x)22.3f1(x)=O(g1(x)f2(x)=O(g2(x)f1(x)f2(x)=O(g1(x)g2(x)2.222nn!logn!On!=123nnnnn=nnlogn!lognn=nlognn!=O(nn)logn!=O(nlogn)3f(n)=8nlogn!+(n2+5)lognOnlogn!=O(nlogn)8n=O(n)8nlogn!=O(n2logn)n2+5=O(n2)(n2+5)logn=O(n2
8、logn)f(n)=O(n2logn)Ox1lognlog2nnnlognn22nn!n0n81.nknkn(n1)+(n2)+2+1=n(n1)2.O(n2)nO(nlogn)2.(TSP)nnn2.2GGCGHamiltonCGHamiltonHamiltonHamiltonnHamiltonHamiltonHamiltonn(n1)!2Hamilton()(n1)!)O(nc)cn2.3PNPP()9P(tractablefeasible)(intractableinfeasible)NPIC(I)NP4G=kc:V12kG(uv)Ec(u)6=c(v)(Gk-)NPI=GC(I)c:V
9、12kk-c:V12k(O(m)k-PNPNP=PNPPNPNPNPCNPC2.3P1P2AP1I1P2I2I1P1I2P2P1P2P2PP1P2.4ANPC(1)ANP(2)BNPBA2.4(2)NP2.4NPCNPCNPNP=PNP6=P2-1!#$%#$%!NP!P!NPC#NP102-1:1971NPCSATNPCNPBNPCNPCAAB5(G=SS)G=k|V|kSSTSPNPCNPCHamilton3.Dijkstra21.8510.3()Gew(e)GDijkstra1959Dijkstra(u0)G(u1u2un1)1.SVu0SS=VS11P=u0uvu0Su0S(1)u0v
10、(2)uSP(u0u)-u0u(1)(2)d(u0v)=d(u0u)+w(uv).d(u0S)=minuSvSd(u0u)+w(uv).S0=u0Step1d(u0S0)=minvS0w(u0v)=w(u0u1)S1=u0u1P1=u0u1.Step2d(u0S1)=minuS1vS1d(u0u)+w(uv)=d(u0u)+w(uu2)uu0u1S2=u0u1u2P2=u0uu2.Stepk+1d(u0Sk)=minuSkvSkd(u0u)+w(uv)=d(u0u)+w(uuk+1)Sk+1=u0u1uk+1Pk+1=u0uuk+1u0uSn1Piu0ui1()(2)u077118222443
11、36654u5u0u6u7u3u1u2u3-1Step1P1=u0u5Step2P2=u0u5u7Step3P3=u0u5u612Step4P4=u0u1Step5P5=u0u5u6u2Step6P6=u0u5u7u3Step7P7=u0u5u4Dijkstra2.DijkstraDijkstraGV(G)=v1v2vnStep1Gu0l(u0)=0l(v)=v6=u0S0=u0P0=u0Step2Si=u0u1uiP0P1PiSi+1Pi+1(1)vSil(v)l(ui)+w(uiv)l(v)=l(ui)+w(uiv)b(v)=ui(2)ui+1=minvSil(v)Si+1=Siui+1(
12、3)Pi+1=Pb(ui+1)ui+1Step3Step2P1P2Pn1l(ui)u0uiPii=12n12()1u03.DijkstraStep2(1)O(n2)4.Kruskal22.5510.2Gew(e)13KruskalKruskal1.AGStep1Ge1Step2e1e2eiei+1(1)ei+1E(G)e1e2ei(2)Ge1e2eiei+1Step3Step2S=e1e2en1.4.1AGATStep2(2)TT(1)T(2)TAStep22AS=e1eiGSei+1AGSei+1ei+1GSGSSG(1)ei+1GSGSei+1ei+1GSGSei+1ei+1GSAGvkk
13、k=12nei+1GSGSei+1ei+1GSei+1GSei+1AO(m)2.KruskalB(Kruskal1956)GStep1e1w(e1)14Step2e1eiE(G)e1eiei+1(1)Ge1e2eiei+1(2)w(ei+1)(1)Step3Step2S=e1e2en1.1()4-1212233344-14-24-2KruskalStep2(2)KruskalO(n2)KruskalKruskal11Kruskal4.1GTG(1)eE(G)e6E(T)T+eC(2)fE(C)f6=eT=Tf+eG(1)e(1)e=(uv)TT(uv)PP+eT+eT+eC1C115TeE(C1)eE(C2)C1eC2eT(uv)T(2)TGT(1)T+eCfE(C)T=T+efTTeWTeCeWT=T+ef24.2B4.1BGV(G)=v1vnT=Ge1en1TGTGT6=Teiei6E(T)f(T)iei6E(T)TTf(T)f(T)=ke1ek1E(T)ek6E(T)4.1(1)T+ekCCekE(T)ek6E(T)CTT=Tek+ek4.1(2)TGe1ek1ekTGe1ek1ekBStep2(2)w(ek)w(ek)w(T)w(T)Te1e
