vignette|Appariement à 3 dimensions. (a) Donnée T. (b)–(c) Deux solutions. (c) est de taille maximum. En mathématiques, et notamment en théorie des graphes, un appariement à 3 dimensions (en anglais : ) est une généralisation du couplage (aussi appelé appariement en dimension 2 ) à une situation ternaire qui, techniquement, est celle des hypergraphes dits 3-uniformes. Trouver un appariement à de taille maximum est un problème NP-difficile bien connu en théorie de la complexité informatique.

Définition Soient et trois ensembles finis disjoints, et soit un sous-ensemble de . Ainsi, est composé de triplets , avec et . Une partie est un appariement à 3 dimensions si la propriété suivante est vérifiée : pour toute paire de triplets et distincts de , on a , et . En d'autres termes, si deux triplets diffèrent sur une composante, ils doivent différer sur toutes leurs composantes.

Exemple La figure à droite illustre un appariement à 3 dimensions. L'ensemble est représenté par des points rouges, par des points bleus et par des points verts. La figure (a) montre l'ensemble donné ; chaque triplet est dessiné dans une zone grisée. La figure (b) montre un appariement à 3 dimensions composé de deux éléments, et la figure (c) montre un appariement composé de trois éléments.

L'appariement de la figure (c) est de taille maximum : il n'en existe pas de taille plus grande, alors que l'appariement de la figure (b), tout en n'étant pas de taille maximum, est maximal : il ne peut pas être agrandi en un appariement plus grand.

Comparaison avec le couplage Un couplage, ou appariement à 2 dimensions, peut être défini de manière tout à fait analogue : soient et deux ensembles finis disjoints, et soit une partie de . Une partie est un couplage si, pour toute paire de couples distincts et de , on a et .

Dans le cas de l’appariement en dimension 2, l'ensemble peut être interprété comme l'ensemble des arêtes d'un graphe biparti , chaque arête de reliant un sommet de à un sommet de . Un appariement à 2 dimensions est alors couplage dans le graphe , c'est-à-dire un ensemble d'arêtes deux-à-deux non adjacentes.

De même, un appariement à 3 dimensions peut être interprété comme une généralisation des couplages aux hypergraphes : les ensembles et contiennent les sommets, chaque triple de est une hyper-arête, et l'ensemble est formé d'hyper-arêtes deux-à-deux disjointes, c'est-à-dire sans sommet commun.

Comparaison avec le set packing Un appariement à 3 dimensions est un cas particulier du set packing: on peut interpréter chaque triplet de comme un sous-ensemble de ; un appariement à 3 dimensions consiste alors en des sous-ensembles deux-à-deux disjoints.

Problème de décision En théorie de la complexité informatique, le problème de lappariement à 3 dimensions est le nom du problème de décision suivant : étant donné un ensemble et un entier k; décider s'il existe un appariement à 3 dimensions avec au moins k éléments.

Ce problème de décision est connu pour être NP-complet : c'est l'un des fameux 21 problèmes NP-complets de Karp.. Il existe toutefois des algorithmes polynomiaux pour ce problème dans des cas particuliers, comme celui des hypergraphes « denses ».

Le problème est NP-complet même dans le cas particulier où , Section 3.1 et Problème SP1 dans Appendix A.3.1., Section 15.5.. Dans ce cas, un appariement à 3 dimensions n'est pas seulement un set packing mais aussi un problème de la couverture exacte : l'ensemble couvre chaque élément de et une fois exactement, Section 15.7..

Problème d'optimisation Un appariement à 3 dimensions maximum est un appariement à 3 dimensions de taille maximum. En théorie de la complexité, c'est aussi le nom du problème d'optimisation combinatoire suivant : étant donné , trouver un appariement à 3 dimensions de taille maximum.

Comme le problème de décision est NP-complet, le problème d'optimisation est NP-difficile, et il n'existe donc vraisemblablement pas d'algorithme polynomial pour trouver un appariement à 3 dimensions maximum, alors qu'il existe des algorithmes efficaces en temps polynomial pour la dimension 2, comme l'algorithme de Hopcroft et Karp.

Algorithmes d'approximation Le problème est APX-complet ; en d'autres termes, il est difficile de l'approximer avec un facteur constant., de l'... En revanche, pour toute constante , il existe un algorithme d'approximation en temps polynomial de facteur .

Il existe un algorithme polynomial très simple pour calculer une appariement à avec un facteur d'approximation 3 : il suffit de trouver un appariement à quelconque qui ne peut être augmenté (un appariement maximal). Il n'est pas forcément maximum, mais tout comme une couplage maximal est un couplage maximum à un facteur 1/2 près, un appariement à 3 dimensions maximal est maximum à un facteur 1/3 près.

Notes et références

Voir aussi Articles connexes Théorie des graphes Couplage (théorie des graphes) Liste de problèmes NP-complets

Bibliographie . . . .

. . . .

Catégorie:Couplage (théorie des graphes) Catégorie:Problème NP-complet Catégorie:Combinatoire