Potrivire tridimensională

În matematică , în special în teoria graficelor , o potrivire tridimensională (în engleză: potrivire tridimensională ) este o generalizare a cuplării (numită și împerechere în 2D ) la o situație ternară care, din punct de vedere tehnic, este cea a hipergrafelor numite 3 uniforme . Găsirea unei potriviri tridimensionale de dimensiuni maxime este o problemă binecunoscută NP-hard în teoria complexității de calcul .

Definiție

Fie și să fie trei mulțimi finite disjuncte și să fie un subset de . Deci, este compus din triplete , cu și . O parte este o pereche de 3-dimensionale , dacă următoarea proprietate este adevărată: pentru orice pereche de tripleți și distincte de , avem , și . Cu alte cuvinte, dacă două triplete diferă pe o componentă, acestea trebuie să difere pe toate componentele lor. $X Y$ $Z$ $T$ ${\ displaystyle X \ times Y \ times Z}$ $T$ $(X Y Z)$ ${\ displaystyle x \ în X, y \ în Y}$ $z \ în Z$ ${\ displaystyle M \ subseteq T}$ ${\ displaystyle (x_ {1}, y_ {1}, z_ {1})}$ ${\ displaystyle (x_ {2}, y_ {2}, z_ {2})}$ $M$ ${\ displaystyle x_ {1} \ neq x_ {2}}$ ${\ displaystyle y_ {1} \ neq y_ {2}}$ ${\ displaystyle z_ {1} \ neq z_ {2}}$

Exemplu

Figura din dreapta ilustrează o împerechere tridimensională. Întregul este reprezentat de puncte roșii , puncte albastre și puncte verzi. Figura (a) prezintă setul dat; fiecare triplet este desenat într-o zonă gri. Figura (b) prezintă o împerechere tridimensională formată din două elemente, iar Figura (c) prezintă o împerechere formată din trei elemente. $X$ $Da$ $Z$ $T$

Împerecherea figurii (c) are dimensiunea maximă : nu există o dimensiune mai mare, în timp ce împerecherea figurii (b), deși nu este de dimensiunea maximă, este maximă : nu poate fi mărită într-o împerechere mai mare.

Comparație cu cuplaj

O cuplare , sau o asociere bidimensională , poate fi definită într-un mod complet analog: let și două mulțimi finite disjuncte și fie o parte a . O parte este o cuplare dacă, pentru orice pereche de perechi distincte și de , avem și . $X$ $Da$ $T$ $X \ ori Y$ ${\ displaystyle M \ subseteq T}$ $(x_ {1}, y_ {1})$ $(x_ {2}, y_ {2})$ $M$ ${\ displaystyle x_ {1} \ neq x_ {2}}$ ${\ displaystyle y_ {1} \ neq y_ {2}}$

În cazul potrivirii bidimensionale, setul poate fi interpretat ca setul de margini ale unui grafic bipartit , fiecare margine de conectare a unui vârf de la un vârf de . O împerechere bidimensională este apoi o împerechere în grafic , adică un set de margini neadiacente două la două. $T$ ${\ displaystyle G = (X \ cup Y, T)}$ $T$ $X$ $Da$ $G$

La fel, o împerechere tridimensională poate fi interpretată ca o generalizare a cuplajelor la hipergrafe : mulțimile și conțin vârfurile, fiecare triplu este o hiper-muchie, iar setul este format din două până la două hiper-margini. disjunct, adică fără un vârf comun. $X Y$ $Z$ $T$ $M$

Comparație cu ambalajul setat

O pereche de 3-dimensional este un caz special de set de ambalare : putem interpreta fiecare triplet de ca un subset al ; o împerechere tridimensională constă atunci din subseturi disjuncte două la două. $(X Y Z)$ $T$ ${\ displaystyle \ {x, y, z \}}$ ${\ displaystyle X \ cup Y \ cup Z}$ $M$

Problema deciziei

În teoria complexității de calcul , problema de potrivire tridimensională este denumirea următoarei probleme de decizie : dat un set și un număr întreg k ; decideți dacă există o pereche tridimensională cu cel puțin k elemente. $T$ ${\ displaystyle M \ subseteq T}$

Se știe că această problemă de decizie este NP-completă : este una dintre faimoasele 21 probleme ale NP-Karp ale Karp . Cu toate acestea, există algoritmi polinomiali pentru această problemă în cazuri speciale, precum cel al hipergrafelor „dense”.

Problema este NP-completă chiar și în cazul special . În acest caz, o împerechere tridimensională nu este doar un set de ambalare, ci și o problemă a acoperirii exacte : setul acoperă fiecare element din și o dată exact. ${\ displaystyle k = | X | = | Y | = | Z |}$ $M$ $X Y$ $Z$

Problemă de optimizare

Un maxim de 3-dimensional meci este un meci de dimensiune maximă de 3-dimensionale. În teoria complexității, este, de asemenea, numele următoarei probleme de optimizare combinatorie : dat , găsiți o potrivire tridimensională de dimensiune maximă. $T$ $M$

Deoarece problema deciziei este NP-completă , problema de optimizare este NP-dificilă și, prin urmare, probabil că nu există algoritm polinomial pentru a găsi o potrivire tridimensională maximă, în timp ce există algoritmi eficienți în timp polinomial pentru dimensiunea 2, cum ar fi Hopcroft și Algoritm Karp .

Algoritmi de aproximare

Problema este completă cu APX ; cu alte cuvinte, este dificil să o aproximăm cu un factor constant. Pe de altă parte, pentru orice constantă , există un algoritm de aproximare a timpului polinomial al factorului . $\ varepsilon> 0$ ${\ displaystyle 3/2 + \ varepsilon}$

Există un algoritm polinomial foarte simplu pentru a calcula o potrivire tridimensională cu un factor de aproximare 3: este suficient să găsiți orice potrivire tridimensională care nu poate fi mărită (o potrivire maximă). Nu este neapărat maxim, dar la fel cum o cuplare maximă este o cuplare maximă la un factor de 1/2, o potrivire tridimensională maximă este maximă la un factor de 1/3.

Note și referințe

Karp 1972 .
Karpinski, Rucinski și Szymanska 2009
Keevash, Knox și Mycroft 2013
Garey și Johnson 1979 , secțiunea 3.1 și problema SP1 din apendicele A.3.1.
Korte și Vygen 2006 , secțiunea 15.5.
Papadimitriou și Steiglitz 1998 , secțiunea 15.7.
Crescenzi și colab. 2000 .
Ausiello și colab. 2003 , SP1 Problema din Anexa B .
Kann 1991 .

(ro) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „ 3-dimensional matching ” ( vezi lista autorilor ) .

Vezi și tu

Articole similare

Bibliografie

Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela și Marco Protasi , Complexitate și aproximare: probleme de optimizare combinatorie și proprietățile lor de aproximabilitate , Springer ,2003.
Pierluigi Crescenzi , Viggo Kann , Magnús Halldórsson , Marek Karpinski și Gerhard Woeginger , „potrivire maximă tridimensională” , într- un compendiu de probleme de optimizare NP ,2000( citește online ).
(ro) Michael Garey și David S. Johnson , Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
Viggo Kann , „ Potrivirea maximă tridimensională delimitată este MAX SNP-complet ”, Information Processing Letters , vol. 37, n o 1,1991, p. 27–35 ( DOI 10.1016 / 0020-0190 (91) 90246-E ).
(ro) Richard M. Karp , „Reducibility Among Combinatorial Problems” , în Raymond E. Miller și James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , citit online ) , p. 85-103
Marek Karpinski , Andrzej Rucinski și Edyta Szymanska , „ Complexitatea problemelor de potrivire perfectă asupra hipergrafelor dense ”, ISAAC '09 Proceedings of the 20th International Symposium on Algorithms ,2009, p. 626-636 ( DOI 10.1007 / 978-3-642-10631-6_64 ).
Peter Keevash , Fiachra Knox și Richard Mycroft , „ Polynomial-Time perfect matchings in dense hypergraphs ”, STOC '13 Proceedings of the patruzeci și cinci simpozion anual ACM ,2013, p. 311-320 ( DOI 10.1145 / 2488608.2488647 ).
Bernhard Korte și Jens Vygen , Optimizare combinatorie: teorie și algoritmi , Springer ,2006, 3 e ed..
Christos H. Papadimitriou și Kenneth Steiglitz , Combinatorial Optimization: Algorithms and Complexity , Dover Publications ,1998.