Acoplamento (teoria dos grafos)
Na teoria dos grafos um acoplamento, emparelhamento ou conjunto de arestas independentes em um grafo G é um conjunto de arestas sem vértices em comum. Em outras palavras, dado um grafo G, um acoplamento M é subconjunto de arestas de G tal qual todo vértice em G é extremo de, no máximo, uma aresta em M. G pode ser ainda um grafo inteiro consistindo de arestas sem vértices comuns.
Dado um grafo G = (V,E), um acoplamento M em G é um conjunto arestas não-adjacentes par-a-par; ou seja, duas arestas de M não compartilham um mesmo vértice. Um vértice é dito acoplado (ou saturado) se for incidente a uma aresta no acoplamento. Caso contrário o vértice é não-acoplado.
Acoplamento Maximal
Um acoplamento maximal é um acoplamento M de um grafo G com a propriedade de que se qualquer aresta que não está em M é adicionada à M, deixa de ser um acoplamento, ou seja, M é maximal se não é um subconjunto próprio de qualquer outro acoplamento no grafo G. Em outras palavras, um acoplamento M de um grafo G é máximal se cada aresta em G tem uma intersecção não vazia com pelo menos uma aresta em M. A figura a seguir mostra exemplos de acoplamentos maximais (em vermelho) em três grafos.
Acoplamento Máximo
Um acoplamento máximo é um subconjunto M de um dado grafo G que contém o maior número possível de arestas. Pode haver muitos acoplamentos máximos. O número de acoplamento ν ( G ) {\displaystyle \nu (G)} de um grafo G {\displaystyle G} é o tamanho do acoplamento máximo. Note que todo acoplamento máximo é maximal, mas nem todo acoplamento maximal é um acoplamento máximo. A figura a seguir mostra exemplos de acoplamentos máximos (em vermelho) em três grafos.
Acoplamento Perfeito
Um acoplamento perfeito é um subconjunto M de arestas de um grafo G que contém todos os vértices de G. Isto é, cada vértice do grafo é incidente a exatamente uma aresta no acoplamento. A Figura (b) acima é um exemplo de acoplamento perfeito. Todo acoplamento perfeito é máximo e portanto maximal. Em algumas literaturas, o termo acoplamento completo é usado. Na figura acima, somente a parte (b) mostra um acoplamento perfeito. Um acoplamento perfeito é também uma cobertura de arestas de tamanho mínimo. Assim, ν ( G ) ≤ ρ ( G ) {\displaystyle \nu (G)\leq \rho (G)} , ou seja, o tamanho de um acoplamento máximo não é maior do que o tamanho de uma cobertura de arestas mínima.
Acoplamento Quase Perfeito
Um acoplamento quase perfeito é aquele em que exatamente um vértice é não-acoplado. Isso só pode ocorrer quando o grafo tem um número ímpar de vértices, e tal acoplamento deve ser máximo. Na figura acima, a parte (c) mostra um acoplamento quase-perfeito. Se, para cada vértice em um grafo, há um acoplamento quase perfeito que omite somente aquele vértice, o grafo é também chamado de fator-crítico.
Caminhos e o Acoplamento
Pode-se provar que o acoplamento é máximo se e somente se ele não tem nenhum caminho de aumento. Este resultado é muitas vezes chamado de lema de Berge.
Em qualquer grafo sem vértices isolados, a soma do número de acoplamento e o número de cobertura de arestas é igual ao número de vértices. Se houver um acoplamento perfeito, então tanto o número de acoplamento quanto o número de cobertura de arestas são |V|/2. Se A e B são dois acoplamentos maximais, então |A| ≤ 2|B| e |B| ≤ 2|A|. Para ver isto, observe que cada aresta em A \ B pode ser adjacente até um máximo de duas arestas em B \ A porque B é um acoplamento. Como cada aresta em B \ A é adjacente a uma aresta em A \ B por maximalidade, vemos que Em particular, isso mostra que qualquer acoplamento máximo é uma 2-aproximação de um acoplamento máximo e também uma 2-aproximação de um acoplamento maximal mínimo. Essa desigualdade é apertada: por exemplo, se G é um caminho com 3 arestas e 4 nodos, o tamanho de um acoplamento maximal mínimo é 1 e o tamanho de um acoplamento máximo é de 2.
Uma função geradora do número de acoplamentos de k-arestas em um grafo é chamada acoplamento polinomial. Seja G um grafo e mk o número de acoplamentos de k-arestas. Um acoplamento polinomial de G é Outra definição dá o acoplamento polinomial como
Acoplamentos máximos em grafos bipartidos
Problemas de acoplamento são frequentemente relativos a grafos bipartidos. Encontrar um acoplamento bipartido máximo (frequentemente chamado um acoplamento bipartido de máxima cardinalidade) em um grafo bipartido G = ( V = ( X , Y ) , E ) {\displaystyle G=(V=(X,Y),E)} é talvez o mais simples problema. O algoritmo de caminho aumentado encontra-o, encontrando um caminho de aumento de cada x ∈ X {\displaystyle x\in X} para Y {\displaystyle Y} e adicionando-o ao acoplamento se ele existe. Como cada caminho pode ser encontrade em tempo O ( E ) {\displaystyle O(E)} , o tempo de execução é O ( V E ) {\displaystyle O(VE)} . Esta solução é equivalente a adicionar uma super fonte s {\displaystyle s} com arestas para todos os vértices em X {\displaystyle X} , e um super sumidouro t {\displaystyle t} com arestas de todos os vértices em Y {\displaystyle Y} para t {\displaystyle t} , e encontrar um fluxo máximo de s {\displaystyle s} para t {\displaystyle t} . Todas as arestas com o fluxo de X {\displaystyle X} para Y {\displaystyle Y} então constituem um acoplamento máximo. Uma melhoria em relação a isso é o algoritmo de Hopcroft-Karp, que executa em tempo O ( V E ) {\displaystyle O({\sqrt {V}}E)} . Outra abordagem é baseada no algoritmo rápido de produto de matrizes e tem complexidade O ( V 2.376 ) {\displaystyle O(V^{2.376})} o que é melhor, em teoria, para grafos suficientemente densos, mas na prática o algoritmo é mais lento.
