Algorithmique et Programmation Projet Algorithme d'Edmonds pour les couplage maximaux dans un graphe

Publié par

Algorithmique et Programmation Projet : Algorithme d'Edmonds pour les couplage maximaux dans un graphe Ecole normale superieure Departement d'informatique 2011-2012 Dans un graphe arbitraire, un couplage est un ensemble d'aretes dont les extremites sont toutes distinctes. Un couplage maximal est un couplage contenant le plus grand nombre d'aretes possible. Dans les graphes bipartis, calculer un couplage maximal est relativement facile, en utilisant des algorithmes de flot maximal. C'est d'ailleurs assez bien connu, et discute en detail dans de nombreux ouvrages, dont l'incontournable [1]. Dans les graphes generaux, les couplages maximaux sont bien definis, et il est toujours possible de les calculer en temps polynomial par un algorithme du a Edmonds en 1965, mais qui est bien moins connu. Comme dans l'algorithme de couplage maximal sur les graphes bipartis , il s'agit de construire des couplages de plus en plus grand en ajoignant au precedent un chemin augmentant. 1 Terminologie Etant donne un couplage M , un sommet est dit libre s'il ne touche aucune arete de M . Un chemin dans le graphe est dit alternant si ses aretes sont alternativement dans M et hors de M (donc si une arete sur deux est dans M). Un chemin augmentant est un chemin alternant dont les points de depart et d'arrivee sont deux sommets libres.

  • couplage maximal de maniere comprehensible

  • complexite de l'algorithme

  • sommet libre

  • meme ancetre

  • end function

  • numeros des voisins

  • algorithme d'edmonds pour les couplage maximaux


Publié le : mardi 19 juin 2012
Lecture(s) : 133
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.