Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Couplage (théorie des graphes)
Résumé
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.
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. 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.
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).
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.
Il est possible de trouver un couplage de cardinal maximum en temps polynomial dans un graphe quelconque grâce à l'algorithme d'Edmonds.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.