尋找高連通子圖的近似算法.pdf

1、華中科技大學(xué)碩士學(xué)位論文尋找高連通子圖的近似算法姓名：劉芝梅申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：曹炬20061027華中科技大學(xué)碩士學(xué)位論文華中科技大學(xué)碩士學(xué)位論文IIAbstractTheproblemoffindinghighlyconnectedsubgraphsisanurgentproblemthatisverydifficultincomputationtheybuthasbeenwidelyusedinpractic

2、e.Twoproblemsoffindingedgeconnectedsubgraphsvertexconnectedsubgraphsarestudiedfromtheaspectsofmathematicalmodelofoptimization.Accdingtothenaturesoffindinghighlyconnectedsubgraphsseveralapproximationalgithmsarepresented.F

3、irstseveralalgithmsarepresentedfthesimple2edgeconnectedsubgraphs.Basedontheideaofdepthfirstsearchbymeansofthemaximumspanningtreeadepthfirstalgithmarepresented.Thealgithmissimplemanageablefast.Fthecomplexgraphs“D2”(Degree

4、2)algithmiseffective.Dosomepreprocessingfirstsimplifythegraphsmakeuseofthemaximumbrachestoobtainasolution.theapproximationrationisimproved.Theremovingedgealgithmisabsolutelydifferentfromtheprevioustwo.Itintroducestheidea

5、ofremovingedges.Itbreaksuptheiginalgraphthenaddsvertexesremovesedgestoget2edgeconnectedspanningsubgraphs.Experimentshowsitwouldbemeeffectivefsimplegraphs.FinallycombiningthedepthfirstalgithmtheideaofthealgithmgivenbyNaga

6、mochi和Ibarakioneeffectivealgithmfλ?edgeconnectedsubgraphsisobtained.Somealgithmsarepresentedf2vertexconnectedsubgraphs.Basedonthedepthfirstalgithmf2edgeconnectedsubgraphsthedepthfirstalgithmf2vertexconnectedsubgraphsisob

7、tainedbyslightchanges.thealgithmisimprovedbysomechangestoimprovingtheapproximationration.Basedonthe“D2”algithmf2edgeconnectedsubgraphsusingthesimilarideaapproximationalgithmf2vertexconnectedsubgraphsisobtained.Atlastallt