# Acoplamento tridimensional

Na disciplina matemática de teoria dos grafos, um acoplamento tridimensional é uma generalização do acoplamento bipartido (mais conhecido como acoplamento bidimensional) para hipergrafos triuniformes. Encontrar o maior acoplamento tridimensional é um problema NP-difícil bem conhecido na Teoria da Complexidade computacional.

## Definição

Sejam X, Y, e Z, conjuntos disjuntos finitos, e seja T um subconjunto de X × Y × Z. Isto é, T consiste de triplas (x, y, z) de forma que x ∈ X, y ∈ Y, and z ∈ Z. Dessa forma M ⊆ T é uma acoplamento tridimensional se obedece às seguintes regras: para quaisquer duas triplas distintas (x$_1$, y$_1$, z$_1$) ∈ M e (x$_2$, y$_2$, z$_2$) ∈ M, temos que x$_1$ ≠x$_2$, y$_1$ ≠y$_2$, and z$_1$ ≠z$_2$.

### Exemplo

A figura à direita ilustra combinações tridimensionais. O conjunto X é marcado com pontos vermelhos, Y é marcado com pontos azuis, e Z é marcado com pontos verdes. A Figura (a) mostra o conjunto T (áreas cinzas). A Figura (b) mostra um acoplamento tridimensional M com |M| = 2, e a Figura (c) mostra uma combinação tridimensional M com |M| = 3.
O acoplamento M ilustrado na Figura (c) é um acoplamento tridimensional máximo, isto é, ele maximiza |M|. O acoplamento ilustrado nas figuras (b)–(c) são acoplamentos tridimensionais maximais, isto é, eles não podem ser estendidos adicionando mais elementos a partir de T.

### Comparação com acoplamento bipartido

Um acoplamento bidimensional pode ser definido de uma forma completamente análoga. Sejam X e Y, conjuntos disjuntos finitos, e seja T um subconjunto de X × Y. Sendo assim M ⊆ T é um acoplamento bidimensional se obedece as seguintes regras: para quaisquer dois pares distintos (x$_1$, y$_1$) ∈ M e (x$_2$, y$_2$) ∈ M, temos x$_1$ ≠x$_2$ e y$_1$ ≠y$_2$.
No caso de um acoplamento bidimensional, o conjunto T pode ser interpretado como um conjunto de arestas em um grafo bipartido G = (X, Y, T); cada aresta em T conecta um vértice em X para um vértice em Y. Um acoplamento bidimensional é então um acoplamento no grafo G, que é um conjunto de arestas emparelhadas não-adjacentes.
Consequentemente, acoplamentos tridimensionais podem ser interpretados como uma generalização de combinações para hipergrafos: os conjuntos X, Y, e Z vértices, cada elemento de T é uma hiper-aresta, e o conjunto M consiste de arestas emparelhadas não-adjacentes (arestas que não possuem um vértice comum).

### Comparação com empacotamento de conjunto (set packing)

Um acoplamento tridimensional é um caso especial de empacotamento de conjunto: podemos interpretar cada elemento (x, y, z) de T como um subconjunto {x, y, z} de X ∪ Y ∪ Z; então um acoplamento tridimensional M consiste de subconjuntos disjuntos emparelhados.

## Problema de decisão

Em Teoria da Complexidade, acoplamento tridimensional é também o nome do seguinte problema de decisão: dado um conjunto T e um inteiro k, decida se existe um acoplamento tridimensional M ⊆ T com |M| ≥ k.
Esse problema de decisão é conhecido por ser NP-completo; é um dos 21 problemas NP-completos de Karp. Não obstante, existem algoritmos de tempo polinomiais para esse problema, para hipergrafos densos.
O problema é NP-completo até no caso especial em que k = |X| = |Y| = |Z|. Nesse caso, um acoplamento tridimensional (dominante) não é só um empacotamento de conjunto, mas também um problema de cobertura exata: o conjunto M cobre cada elemento de X, Y, e Z exatamente uma vez.

## Problema de otimização

Um acoplamento tridimensional máximo é o maior acoplamento tridimensional possível. Na teoria da Complexidade, é também o nome do seguinte problema de otimização: dado um conjunto T, encontre um acoplamento tridimensional M ⊆ T que maximize |M|.
Sendo o problema de decisão descrito acima NP-completo, esse problema de otimização é NP-difícil, e consequentemente parece que não há algoritmo de tempo polinomial para encontrar um acoplamento tridimensional máximo. Contudo, há algoritmos de tempo polinomial eficientes para encontrar um acoplamento bipartido máximo (acoplamento bidimensional máximo), por exemplo, o algoritmo de Hopcroft–Karp.

### Algoritmos de aproximação

O problema é APX-completo, ou seja, é difícil criar um Algoritmo de aproximação que difira do resultado exato apenas por uma constante. No lado positivo, para qualquer constante ε > 0 há um algoritmo de aproximação de tempo polinomial (3/2 + ε) para acoplamento tridimensional.
Há um algoritmo de aproximação tridimensional de tempo polinomial muito simples para o acoplamento tridimensional: encontrar qualquer acoplamento tridimensional máximo. Assim como um acoplamento máximo está na ordem de um polinômio de grau 2 em relação a um acoplamento máximo, um acoplamento tridimensional máximo está na ordem de um polinômio de grau 3 em relação a um acoplamento tridimensional máximo.