- Couplage (théorie des graphes)
-
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
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
Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes. Un graphe peut posséder plusieurs couplages maximum.
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.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
Un graphe, même fini, ne possède pas toujours de couplage parfait.
Tout couplage parfait est maximum et tout couplage maximum est maximal (mais les réciproques sont fausses). Il est possible de trouver un couplage maximum en temps polynomial dans un graphe fini quelconque grâce à l'algorithme d'Edmonds (en).
Catégorie :- Concept en théorie des graphes
Wikimedia Foundation. 2010.
