《Graph Classes A Survey.ppt》由会员分享，可在线阅读，更多相关《Graph Classes A Survey.ppt（37页珍藏版）》请在金锄头文库上搜索。
1、GraphClassesASurvey 張貿翔中正大學資訊工程學系 MeetingRoomReservation OnemeetingroomReservation Gary10 00 11 00Mary10 30 12 00Jones13 30 14 30Amy14 00 15 30David11 00 12 30Tom12 00 14 30Tosatisfyasmanyaspossible Theconflictgraph ThemaximumIndependentSetProbleminGraphs Anindependentset Anotherindependentset Amaxi
2、mumindependentset Themeetingroomreservationproblemisreducedtothemaximumindependentsetproblemingraphs ThemaximumindependentsetproblemingeneralgraphsisNP hard MostofoptimizationproblemsingraphsareNP hard Itturnsoutthattheconflictgraphofameetingroomreservationproblemisanintervalgraph Themaximumindepend
3、entsetproblemcanbesolvedinO n timeinintervalgraphsifendverticesaresorted GraphClasses Agraphiscalleda graphifitsatisfiesproperty Forexample agraphhavingnoinducedcycleoflengthgreaterthan3iscalledachordalgraph 4 Achordofcycle5 7 8 6 4 5 Intervalgraphs 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 CircleGraphs 1 2 3
4、 4 5 6 7 8 1 2 3 4 5 6 7 8 PlanarGraphs K5andK3 3arenotplanargraphs Toomanygraphclasses Therearealmost200graphclassesdescribedinthebook GraphClasses ASurvey byBrandst dt Le andSpinrad publishedin1999 D S Johnsonremarkedthat manygraphtheoristshavemadecareersoutofinventingandcharacterizingnewclassesof
5、graphs therearebynowfartoomanyclassesforasinglecolumntosurvey in TheNP completenesscolumn anongoingguide J Algorithm 6 1985 Distance Hereditary SomeGraphClasses TheIntervalgraphRecognitionProblem GivenagraphG testwhetherthereexistsanintervalmodel 官兵捉強盜 TheGraphSearchingProblem Thegraphsearchingprobl
6、emisagraph theoreticalgameplayedonanundirectedgraphconsideredasasystemoftunnelsinwhichallthetunnelsareinitiallycontaminatedbyagas Therearethreekindsofmovesinedgesearching 1 placingasearcheronavertex 2 removingasearcherfromavertex and 3 clearanedgebyeither 3 1 movingasearcherfromonevertextoanotheralo
7、nganedgeor 3 2 placingtwosearchersonthetwoendpointsoftheedge Aclearededgemayberecontaminatedoncethereisapathwithoutanysearchersconnectingtheedgewithacontaminatedone Thegoalofthisgameistodiscoverasequenceofmoves calledstrategy clearthegraphwiththeleastnumberofsearchers TheGraphSearchingProblem Cont T
8、hegraphsearchingproblemispolynomial timesolvableonintervalgraphsandsplitgraphs etc LongestIncreasingSubsequences Input asequence 12 3 10 9 8 13 14 1 11 Output alongestsubsequenceSubsequences 3 10 9or10 13 14etc Increasingsubsequences 3 8 11or12 13 14 or3 10 13 14Longestincreasingsubsequence 3 10 13
9、14or3 9 13 14etc 12 3 10 9 8 13 14 1 11 1 12 2 3 3 10 4 9 5 8 6 13 7 14 8 1 9 11 1 2 3 4 5 6 7 8 9 1 3 8 9 10 11 12 13 14 Thelongestincreasingsubsequencecanbereducedtothemaximumindependentsetprobleminpermutationgraphs ApermutationgraphG AmatchingdiagramofG AnApproachtoDesigningGraphAlgorithms Mostof
10、problemsingraphsareNP hard Manyproblemsingraphsbecomepolynomial timesolvableifthegraphsconsideredsatisfysomeniceproperty Forexample themaximumindependentsetproblemisNP hardingeneralgraphsbutpolynomial timesolvableinchordalgraphs intervalgraphs andpermutationgraphs etc Chromosome Cutrelativelysmall r
11、andompiecesofthechromosome Runchemicalexperimentsonthesmallpiecestogetaccurateinformationaboutthese Thisallowsresearcherstogetinformationaboutfragmentsandfrequenciesoftypesoffragments butlossinformationabouthowthefragmentsareorderedonthechromosome Eachfragmentshouldformanintervalonthechromosome itis
12、naturaltomodelthisproblemasanintervalgraphproblemwithfragmentscorrespondingtovertices Forthismodeltobeuseful theremustbeawaytodeterminewhichfragmentsshouldoverlapinthechromosome correspondingtowhichverticesshouldbeadjacentintheintervalmodel Suchtestshavebeendeveloped whichmakesitseemsimpletouseinter
13、valgraphtechniquestosolvethegenereconstructionproblem Thetestsmayproduceerrors Errorscomeintwoforms Falsepositive Thetestssaythatfragmentsoverlapwhentheydonot Falsenegative Thetestssaythatfragmentsdonotoverlapwhentheyreallydo Dependingonwhichtestisusedandwhatthresholdsareset falsepositivesmaybemuchm
14、orecommonthatfalsenegatives muchlesscommon orbothmayoccurwithrelativelyequalprobability Ifweassumethatallerrorsarefalsenegatives wewanttoknowtheminimumnumberofedgeswecanaddtomakethegraphintervalgraph Thisproblemiscalledtheintervalgraphcompletionproblem Ifweassumeallerrorsarefalsepositives wewanttokn
15、owtheminimumnumberofoverlapswecandeletefromthetestresultstogetanintervalgraph thisiscalledthemaximumintervalsubgraphproblem Iferrorscanbefalsepositivesorfalsenegatives wewanttominimizethenumberofedgedeletionsandadditionssothattheresultisanintervalgraph thisiscalledtheintervalgraphmodificationproblem
16、 Assumethattherearenoerrorsinthetests Ifwehavenfragments andwewanttoreconstructtheentireintervalgraph themethoddescribedcallsfor n2 chemicalteststodeterminewhetherfragmentsoverlap Asubsetofthefragmentsareselectedtobe probes andtheremainingfragmentsarecallednonprobes Insteadoftestingoverlaprelationshipsbetweenpairsoffragments testsareonlymadebetweenaprobeandanotherfragment Theoverlapgraphoffragmentsobtainedinthiswaycanbemadeintoanintervalgraphbyaddingedgesbetweensomenonprobes ThePartitionedProbeG
