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

Description

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

Informations

• Publié par: pefav
• Nombre de lectures: 171
• Langue: Français

Extrait

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

Ecolenormalesupe´rieure De´partementd’informatique [e-mail] 2011-2012

Dans un graphe arbitraire, uncouplagesnmeutensedontetes’arˆbledosse´timertxeselesuttont distinctes.Uncouplagemaximalestuncouplagecontenantleplusgrandnombred’arˆetespossible.Dans les graphes bipartis, calculer un couplage maximal est relativement facile, en utilisant des algorithmes deflotmaximal.C’estd’ailleursassezbienconnu,etdiscut´eende´taildansdenombreuxouvrages,dont l’incontournable [1]. Danslesgraphesg´ene´raux,lescouplagesmaximauxsontbiend´efinis,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 ditlibreuctoneils’etedraeˆucenehuaM. Un chemin dans le graphe est ditalternantmentdansreanitevssnoattlaresteˆeissMet hors deM(donc si une arˆetesurdeuxestdansM). Unchemin augmentanttlestdonrnanalterat´dpestedopnihcnunimetse etd’arriv´eesontdeuxsommetslibres.Onpeutde´montrer(etonadmettra)qu’uncouplageestmaximal s’iln’existepasdecheminaugmentantparrapporta`lui(c’estaussivraidanslesgraphesbipartique dans les graphes ordinaires). On a donc un algorithme simple pour le couplage maximal : 1: functionMaximum-Matching(G) 2: M← ∅ 3: loop 4: P←Augmenting-Path(G, M) 5: ifP=∅then returnMelseM←M⊕P 6: end loop 7: end function Ici,M⊕Planeiges´denerff´di´mteecyseiruqunagrrˆaepedleeusxc-d’iershte-s`(asn’ltnadiduosseetqs oul’autremaispasdanslesdeux).Leprobl`emerestedoncdetrouverdescheminsaugmentants.Autant dansungraphebipartitec’estassezsimple`afaireavecunsimpleparcoursenprofondeur,autantdans lesgraphesg´en´erauxc’estunpeupluscomplique´. Dansungraphe,l’ope´rationdeitcartnocerˆetuneaond’u↔vitera`ersietocsnenoitnqeestue’arletrˆ a`fusionnerles deux sommetsuetvemrte´usL.semosioixvaudenstsetnatltnecajdauet dev. Unefleurilesdtseneevolppseuqarelroepctduneiolbmesedeagrodsenu´eestit’ensparlctnose entourentchezcertainsv´eg´etaux.Pourcequinousint´eresse,unefleurestcompose´ed’unecorolle, qui estlapartiedelafleurform´eeparl’ensembledesespe´tales,etd’unetigevite`acoJevousin.lusnret Wikipe´diapourplusded´etailsbotaniques

2Id´eesous-jascente:lacontractiondesfleurs ´ Etantdonn´eungrapheG,counalpup(egofsae´crmentmaximal)MdeG, et un sommet libres, une fleurp)elatranemeluntetmmbrlid’ntsounermfostecnu’dee´tlanimehntdeernaueurlong(ee´aprieullevtn stnujqs’utelaalet`aunsommv k (c’est latige), et d’un chemin alternant de longueur impaire partant de v k tt`raevenanev k (c’est lacorolle). Le sommetv k est labasede la corolle.

1