Appariement à 3 dimensions

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
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 : 3-dimensional matching) 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 à 3 dimensions de taille maximum est un problème NP-complet bien connu en théorie de la complexité informatique.

Définition[modifier | modifier le code]

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

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

Un couplage, ou appariement à 2 dimensions, peut être défini de manière tout à fait analogue : soient et deux ensemble 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[modifier | modifier le code]

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

En théorie de la complexité informatique, le problème de l'appariement à 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[1]. Il existe toutefois des algorithmes polynomiaux pour ce problème dans desl cas particuliers, comme celui des hypergraphes « denses »[2],[3].

Le problème est NP-complet même dans le cas particulier où [1],[4],[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[6].

Problème d'optimisation[modifier | modifier le code]

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

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

Il existe un algorithme polynomial très simple pour calculer une appariement à 3 dimensions avec un facteur d'approximation 3 : il suffit de trouver un appariement à 3 dimensions quelconque qui ne peut être augmenté (un appariement maximal)[9]. 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[modifier | modifier le code]

  1. a et b Karp 1972.
  2. Karpinski, Rucinski et Szymanska 2009
  3. Keevash, Knox et Mycroft 2013
  4. Garey et Johnson 1979, Section 3.1 et Problème SP1 dans Appendix A.3.1.
  5. Korte et Vygen 2006, Section 15.5.
  6. Papadimitriou et Steiglitz 1998, Section 15.7.
  7. a et b Crescenzi et al. 2000.
  8. a et b Ausiello et al. 2003, Problème SP1 de l'Appendice B.
  9. a et b Kann 1991.
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « 3-dimensional matching » (voir la liste des auteurs).

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]