Couplage (théorie des graphes)
Pour les articles homonymes, voir Couplage et Appariement.
En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun.
Définitions
modifierSoit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que
Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes. Un graphe peut posséder plusieurs couplages maximum. Les images suivantes montrent (en rouge) des couplages maximums.
Un couplage maximal est un couplage M du graphe tel que toute arête du graphe possède au moins une extrémité commune avec une arête de M. Ceci équivaut à dire dans l'ensemble des couplages du graphe, M est maximal au sens de l'inclusion, i.e. que pour toute arête a de A qui n'est pas dans M, n'est plus un couplage de G. Les images suivantes montrent des couplages maximaux.
Un couplage parfait ou couplage complet est un couplage M du graphe tel que tout sommet du graphe est incident à exactement une arête de M.
Propriétés et théorèmes
modifierUn graphe, même fini, ne possède pas toujours de couplage parfait (en particulier, un graphe ayant un nombre impair de sommets ne peut avoir un couplage parfait). Tout couplage parfait est maximum et tout couplage maximum est maximal (mais les réciproques sont fausses).
Le théorème de Hall ou lemme des mariages donne une condition nécessaire et suffisante pour l'existence d'un couplage parfait dans un graphe biparti.
Le théorème de König énonce l'égalité, dans un graphe biparti, de la taille du transversal minimum (i. e. de la couverture par sommets minimum) et de la taille du couplage maximum.
Le théorème de Petersen énonce que tout graphe cubique sans isthme possède un couplage parfait[1].
Aspects algorithmiques
modifierIl est possible de trouver un couplage de cardinal maximum en temps polynomial dans un graphe quelconque grâce à l'algorithme d'Edmonds[2]. Le cas particulier des graphes bipartis peut être résolu en utilisant des chemins augmentants, ou par l'algorithme de Hopcroft-Karp. Des heuristiques plus rapides et plus simples ont aussi été étudiées, avec des ratios d'approximation un peu meilleurs que le 1/2 obtenu pour n'importe quel couplage maximal[3].
Étant donné un graphe biparti dont les arêtes sont valuées, le problème qui consiste à trouver un couplage de cardinal maximum et de poids minimum (ou couplage parfait de poids minimum) est appelé problème d'affectation. Il existe plusieurs algorithmes pour ce problème dont l'algorithme hongrois.
Applications
modifierUn couplage peut être utilisé dans les problèmes d'affectation des tâches et ce pour avoir une efficacité maximale, par exemple, chaque tâche est attribuée à une seule machine ou vice versa. La recherche d'un couplage maximum dans un graphe biparti est d'ailleurs appelé le problème d'affectation.
Les couplages peuvent aussi être utilisés pour la publicité en ligne ciblée[4] et pour la comparaison de structure de protéines[5].
Un couplage peut aussi être utilisé pour résoudre ou approcher des problèmes plus complexes comme celui du voyageur de commerce avec l'algorithme de Christofides.
Notes et références
modifier- (de) Julius Peter Christian Petersen, « Die Theorie der regulären Graphs », Acta Mathematica, no 15, , p. 193–220 (DOI 10.1007/BF02392606, lire en ligne).
- Article original : (en) Jack Edmonds, « Paths, trees, and flowers », Canad. J. Math., vol. 17, , p. 449–467 (DOI 10.4153/CJM-1965-045-4).
- (en) Bert Besser, « Approximation Bounds For Minimum Degree Matching », CoRR, vol. abs/1408.0596, .
- (en) Aranyak Mehta, Amin Saberi, Umesh V. Vazirani et Vijay V. Vazirani, « AdWords and generalized online matching », Journal of the ACM, vol. 54, no 5, .
- (en) Bonnie Berger, Rohit Singh et Jinbo Xu, « Graph algorithms for biological systems analysis », dans Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, , p. 142-151.
Bibliographie
modifier- László Lovász et Michael D. Plummer, Matching Theory, North Holland (Elsevier), coll. « Annals of Discrete Mathematics » (no 29), , 543 p. (ISBN 9780080872322, présentation en ligne).
