Cette publication est accessible gratuitement
Télécharger
Algorithmique et Programmation Projet : Algorithme d’Edmonds pour les couplage maximaux dans un graphe
Ecolenormalesupe´rieure De´partementdinformatique td-algo@di.ens.fr 2011-2012
Dans un graphe arbitraire, uncouplagesnmeutensedontetesarˆbledosse´timertxeselesuttont distinctes.Uncouplagemaximalestuncouplagecontenantleplusgrandnombredarˆetespossible.Dans les graphes bipartis, calculer un couplage maximal est relativement facile, en utilisant des algorithmes deotmaximal.Cestdailleursassezbienconnu,etdiscut´eende´taildansdenombreuxouvrages,dont l’incontournable [1]. Danslesgraphesg´ene´raux,lescouplagesmaximauxsontbiend´enis,etilesttoujourspossibledeles calculerentempspolynomialparunalgorithmeduˆ`aEdmondsen1965,maisquiestbienmoinsconnu. Comme dans l’algorithme de couplage maximal sur les graphes bipartis , il s’agit de construire des couplagesdeplusenplusgrandenajoignantaupr´ece´dentunchemin augmentant.
1 Terminologie ´ Etantdonn´euncouplageM, un sommet est ditlibreuctoneilsetedraeˆucenehuaM. Un chemin dans le graphe est ditalternantmentdansreanitevssnoattlaresteˆeissMet hors deM(donc si une arˆetesurdeuxestdansM). Unchemin augmentanttlestdonrnanalterat´dpestedopnihcnunimetse etdarriv´eesontdeuxsommetslibres.Onpeutde´montrer(etonadmettra)quuncouplageestmaximal silnexistepasdecheminaugmentantparrapporta`lui(cestaussivraidanslesgraphesbipartique dans les graphes ordinaires). On a donc un algorithme simple pour le couplage maximal : 1:functionMaximum-Matching(G) 2:M← ∅ 3:loop 4:PAugmenting-Path(G, M) 5:ifP=then returnMelseMMP 6:end loop 7:end function Ici,MPlaneiges´dener´di´mteecyseiruqunagrrˆaepedleeusxc-diershte-s`(asnltnadiduosseetqs oulautremaispasdanslesdeux).Leprobl`emerestedoncdetrouverdescheminsaugmentants.Autant dansungraphebipartitecestassezsimple`afaireavecunsimpleparcoursenprofondeur,autantdans lesgraphesg´en´erauxcestunpeupluscomplique´. Dansungraphe,lope´rationdeitcartnocerˆetuneaonduvitera`ersietocsnenoitnqeestuearletrˆ a`fusionnerles deux sommetsuetvemrte´usL.semosioixvaudenstsetnatltnecajdauet dev. Unefleurilesdtseneevolppseuqarelroepctduneiolbmesedeagrodsenu´eestitensparlctnose entourentchezcertainsv´eg´etaux.Pourcequinousint´eresse,uneeurestcompose´edunecorolle, qui estlapartiedelaeurform´eeparlensembledesespe´tales,etdunetigevite`acoJevousin.lusnret Wikipe´diapourplusded´etailsbotaniques
2Id´eesous-jascente:lacontractiondeseurs ´ Etantdonn´eungrapheG,counalpup(egofsae´crmentmaximal)MdeG, et un sommet libres, une fleurp)elatranemeluntetmmbrlidntsounermfostecnudee´tlanimehntdeernaueurlong(ee´aprieullevtn stnujqsutelaalet`aunsommvk(c’est latige), et d’un chemin alternant de longueur impaire partant de vktt`raevenanevk(c’est lacorolle). Le sommetvkest labasede la corolle.
1
s v1v2
vk
u
v
Danslecasou`latigenestpastriviale,alorslareˆtedelatigequitouchelabasedelacorolleest ne´cessairementlaseuleOnr.euri´exttemearalpuuqegeteˆocudsommetdeirelieun`euasnmoalocorll 0 conside`relegrapheGcontnuenobtelsseuoetnattartceˆradsetenuoroce(lloquaanvelppreC), en 0 00 appelantccaledtnaitcartnodeonlesommetr´esultC, etMle couplage deGemelamˆunedboet manie`re.Onde´montre(parcequecestutilepour´ecrirelalgorithme)que 0 0 Theore`me1.S’il existe dansGun chemin augmentant pourM, alors il existe dansGun chemin 0 augmentant pourM. D´emonstration.nadannatpceltimehantlacorolleete,tnede´ocpmerssplexitruenemiticOtsnoceln 0 deG. 0 – Sile chemin ne passe pas parcre.iafa`neiraynli, 0 00 – Sicnedeestudscutie´´rmeestxnssomihedin(∙ ∙ ∙xclsroˆraetela,)xcn’appartient pas 0 00 0 a`M. De plus,c`tapprontseiassece´lintmereraarepbrM(sinon le chemin deGne serait pas augmentant).CedernierfaitimpliquequaucunearˆeteducouplageMne touche la corolleC, et doncenparticulierquelabasedelacorolleestlibreparrapport`aM(donc que la tige est triviale). Pour´etendrelechemina`lint´erieurdelacorolle,onchoisitundessommetsdeCa`stjdanecax (disonsy), et on part dans la corolle depuisyan¸cenmmcoen,eˆralerviusraptudetpuocegalM qui toucheytlabasedelacorolteqeaudnnotaetni.sOnrˆartlmeomns.reibanoracelutnietta 0 Onadonce´tendulecheminaugmentantdeMen un chemin augmentant deM. 0 0 – Sile chemin traversec(disons qu’il fait∙ ∙ ∙xcz. . .uedsedenuaylisroal),etesxarˆ 0 0 en contact aveccqui fait partie du couplageMitua(lasestctionete`lpmo´mystneme,qurietncdo 0 onpeutsupposersanspertedeg´en´eralite´quecestxceess´omprd.´)ecefUnsqoionuraauC, on auradoncuneareˆteducouplageentrexet la corolle, ce qui signifie (cf. supra) qu’elle doit toucher la base de la corolle. En fait, dans ce casxlentme´edetmmsotvanacroftsevksur la tige. Partant dela`,onfaitcommedanslecaspr´ec´edentpourbrancherysur la base de la corolle.
Engros,onvaexplorerlegraphea`larechercheduncheminaugmentant.Sionentrouveun,cest bon.Siontrouveuneeur,onlacontracteetonrecommencere´cursivementlexplorationsurungraphe plus petit. Si on ne trouve ni fleur, ni chemin augmentant, c’est que le couplage actuel est maximal. Vu desusammenthaut,cequonvar´ealiserest: 1:functionAugmenting-Path(G, M) 2:Explorer le graphe 3:ifttanntme´euvrocanguehimthen stop 4:ifelolrotreeo´cvuthen 0 5:Gn´´eererGen contractant la corolle 0 0 6:PAugmenting-Path(MG ,) 7:ifP=then returnelse returnrpsecemo´Dsion(P) 8:end function
3 Explorationdu Graphe Pourexplorerlegraphe,onutiliseuneproc´eduredemarquage.Oncommenceavecungraphesans ´etiquettes.
Signification des marques.seosLentdcoivsre¸mmetledsetteuqite´se[meorafx, P, y] (resp. [x, I, y]) qui signifient“accessible depuis le sommet librexpar un chemin alternant de longueur paire (resp. impaire),dontlesommetpre´ce´dentesty.Silasignictaoidnsee´ituqteseterestecspeet´ola,nosrsela invariant suivants : ie[u´rqmaetmmsoUn)s, P,nemete´rp´sicest(etcibreentl´cmeftro]ses). ii) siu[s, P, x]v[s, I, uenlarˆet´enitioolsrapdr]a,uvne fait pas partie du couplage.
2