En la disciplina matemática de la teoría de grafos , una coincidencia tridimensional es una generalización de la coincidencia bipartita (también conocida como coincidencia bidimensional) a hipergrafos tridimensionales , que consisten en hiperaristas, cada una de las cuales contiene 3 vértices (en lugar de aristas que contienen 2). vértices en un gráfico habitual).
La coincidencia tridimensional, a menudo abreviada como 3DM , es también el nombre de un problema computacional muy conocido: encontrar la coincidencia tridimensional más grande en un hipergráfico determinado. 3DM es uno de los primeros problemas que resultó ser NP-duro .
Sean X , Y y Z conjuntos finitos y sea T un subconjunto de X × Y × Z . Es decir, T consta de tripletas ( x , y , z ) tales que x ∈ X , y ∈ Y y z ∈ Z . Ahora M ⊆ T es una coincidencia tridimensional si se cumple lo siguiente: para dos triples distintos cualesquiera ( x 1 , y 1 , z 1 ) ∈ M y ( x 2 , y 2 , z 2 ) ∈ M , tenemos x 1 ≠ x 2 , y 1 ≠ y 2 , y z 1 ≠ z 2 .
La figura de la derecha ilustra coincidencias tridimensionales. El conjunto X está marcado con puntos rojos, Y está marcado con puntos azules y Z está marcado con puntos verdes. La figura (a) muestra el conjunto T (áreas grises). La figura (b) muestra una M coincidente tridimensional con | METRO | = 2, y la Figura (c) muestra una coincidencia tridimensional M con | METRO | = 3.
La coincidencia M ilustrada en la Figura (c) es una coincidencia tridimensional máxima , es decir, maximiza | M |. Las coincidencias ilustradas en las Figuras (b) a (c) son coincidencias tridimensionales máximas , es decir, no se pueden ampliar agregando más elementos de T.
Aquí hay un ejemplo de visualización interactiva en javascript.
De forma totalmente análoga se puede definir una adaptación bidimensional . Sean X e Y conjuntos finitos y sea T un subconjunto de X × Y. Ahora M ⊆ T es una coincidencia bidimensional si se cumple lo siguiente: para dos pares distintos cualesquiera ( x 1 , y 1 ) ∈ M y ( x 2 , y 2 ) ∈ M , tenemos x 1 ≠ x 2 e y 1 ≠ y 2 .
En el caso de coincidencia bidimensional, el conjunto T se puede interpretar como el conjunto de aristas en un gráfico bipartito G = ( X , Y , T ); cada arista en T conecta un vértice en X con un vértice en Y. Una coincidencia bidimensional es entonces una coincidencia en el gráfico G , es decir, un conjunto de aristas no adyacentes por pares.
Por lo tanto, las coincidencias tridimensionales pueden interpretarse como una generalización de las coincidencias con hipergrafos: los conjuntos X , Y y Z contienen los vértices, cada elemento de T es una hiperarista y el conjunto M consta de aristas no adyacentes por pares (aristas que no tienen un vértice común). En el caso de una coincidencia bidimensional, tenemos Y = Z.
Una coincidencia tridimensional es un caso especial de empaquetado de conjuntos : podemos interpretar cada elemento ( x , y , z ) de T como un subconjunto { x , y , z } de X ∪ Y ∪ Z ; entonces una coincidencia tridimensional M consta de subconjuntos disjuntos por pares.
En la teoría de la complejidad computacional, la coincidencia tridimensional (3DM) es el nombre del siguiente problema de decisión : dado un conjunto T y un número entero k , decidir si existe una coincidencia tridimensional M ⊆ T con | METRO | ≥k .
Se sabe que este problema de decisión es NP-completo ; es uno de los 21 problemas NP completos de Karp . [1] Es NP-completo incluso en el caso especial de que k = | X | = | Y | = | Z | y cuando cada elemento está contenido en como máximo 3 conjuntos, es decir, cuando queremos una coincidencia perfecta en un hipergrafo de 3 regulares. [1] [2] [3] En este caso, una coincidencia tridimensional no es solo un conjunto de empaquetadura, sino también una cobertura exacta : el conjunto M cubre cada elemento de X , Y y Z exactamente una vez. [4] La prueba es por reducción de 3SAT . Dada una instancia 3SAT, construimos una instancia 3DM de la siguiente manera: [2] [5]
Existen algoritmos de tiempo polinómico para resolver 3DM en hipergráficos densos. [6] [7]
Una coincidencia tridimensional máxima es una coincidencia tridimensional más grande. En la teoría de la complejidad computacional, este es también el nombre del siguiente problema de optimización : dado un conjunto T , encontrar una coincidencia tridimensional M ⊆ T que maximice |M| .
Dado que el problema de decisión descrito anteriormente es NP-completo, este problema de optimización es NP-difícil y, por lo tanto, parece que no existe un algoritmo de tiempo polinomial para encontrar una coincidencia tridimensional máxima. Sin embargo, existen algoritmos de tiempo polinomial eficientes para encontrar una coincidencia bipartita máxima (coincidencia bidimensional máxima), por ejemplo, el algoritmo Hopcroft-Karp .
Existe un algoritmo de aproximación tridimensional en tiempo polinomial muy simple para la coincidencia tridimensional: encuentre cualquier coincidencia tridimensional máxima. [8] Así como una coincidencia máxima está dentro del factor 2 de una coincidencia máxima, [9] una coincidencia tridimensional máxima está dentro del factor 3 de una coincidencia tridimensional máxima.
Para cualquier constante ε > 0 existe un algoritmo de aproximación de tiempo polinómico (4/3 + ε) para coincidencia tridimensional. [10]
Sin embargo, lograr mejores factores de aproximación probablemente sea difícil: el problema es APX-completo , es decir, es difícil aproximarlo dentro de alguna constante. [11] [12] [8]
Es NP-difícil lograr un factor de aproximación de 95/94 para una coincidencia máxima en 3D y un factor de aproximación de 48/47 para una coincidencia máxima en 4D. La dureza se mantiene incluso cuando se restringe a instancias con exactamente dos apariciones de cada elemento. [13]
Existen varios algoritmos para la coincidencia tridimensional en el modelo de cálculo masivamente paralelo . [14]
{{citation}}: Mantenimiento CS1: fecha y año ( enlace ).