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. 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 \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 (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
À 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.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement