Couplage (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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[modifier | modifier le code]

Soit 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 \forall (a,a') \in M^2,\qquad a\ne a'\Rightarrow a\cap a'=\varnothing~.

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 des couplages maximums.

Maximum-matching-labels.svg

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, M\cup\{a\} n'est plus un couplage de G. Les images suivantes montrent des couplages maximaux.

Maximal-matching.svg

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[modifier | modifier le code]

Un 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).

Aspects algorithmiques[modifier | modifier le code]

Il est possible de trouver un couplage maximum en temps polynomial dans un graphe fini quelconque grâce à l'algorithme d'Edmonds[1]. Le problème où l'on se restreint à des graphes bipartis est appelé problème d'affectation, et possède quelques algorithmes spécialisés comme l'algorithme hongrois.

Applications[modifier | modifier le code]

Un couplage peut être utilisé dans les problèmes d'affectation des taches et ce pour avoir une efficacité maximale, par exemple, chaque tache est attribuée à une seule machine ou vis versa. La recherche d'un couplage maximum dans un graphe biparti est d'ailleurs appelé le problème d'affectation.

Un couplage peut aussi utilisé pour résoudre ou approcher des problèmes plus complexe comme celui du voyageur de commerce avec l'algorithme de Christofides.

Notes et références[modifier | modifier le code]

  1. Article original : Jack Edmonds, « Paths, trees, and flowers », Canad. J. Math., vol. 17,‎ 1965, p. 449–467 (DOI 10.4153/CJM-1965-045-4)

Articles connexes[modifier | modifier le code]