Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

3 pages
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


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin