Acoplamento (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde janeiro de 2014).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.

Na teoria dos grafos um acoplamento, emparelhamento ou conjunto de arestas independentes em um grafo é um conjunto de arestas sem vértices em comum, pode ser ainda um grafo inteiro consistindo de arestas sem vértices comuns.

Definição[editar | editar código-fonte]

Dado um grafo G = (V,E), um acoplamento M em G é um conjunto arestas não-adjacentes par-a-par[1] ; 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.

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.

Maximal-matching.svg

Um acoplamento máximo é um acoplamento que contém o maior número de arestas possível. Pode haver muitos acoplamentos máximos. O número de acoplamento \nu(G) de um grafo 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.

Maximum-matching-labels.svg

Um acoplamento perfeito é um acoplamento que acopla todos os vértices do grafo. 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, \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.

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.

Dado um acoplamento M,

  • um caminho alternado é um caminho no qual as arestas pertencem alternativamente ao acoplamento e fora do acoplamento[2] .
  • um caminho de aumento é um caminho alternado que inicia e termina em vértices livres (não acoplados). Em outras palavras, um caminho alternado diz-se de aumento se ligar vértices não cobertos por M[2] .

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.)

Propriedades[editar | editar código-fonte]

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[3] . 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

|A \setminus B| \le 2|B \setminus A|.

Além disso temos que

|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|.

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.

Acoplamentos polinomiais[editar | editar código-fonte]

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 é

\sum_{k\geq0} m_k x^k.

Outra definição dá o acoplamento polinomial como

\sum_{k\geq0} (-1)^k m_k x^{n-2k},

onde n é o número de vértices no grafo.

Algoritmos e complexidade computacional[editar | editar código-fonte]

Acoplamentos máximos em grafos bipartidos[editar | editar código-fonte]

Problemas de acoplamento são frequentemente relativos a grafos bipartidos. Encontrar um acoplamento bipartido máximo[4] (frequentemente chamado um acoplamento bipartido de máxima cardinalidade) em um grafo bipartido 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 \in X para Y e adicionando-o ao acoplamento se ele existe. Como cada caminho pode ser encontrade em tempo O(E), o tempo de execução é O(V E). Esta solução é equivalente a adicionar uma super fonte s com arestas para todos os vértices em in X, e um super sumidouro t com arestas para todos os vértices em Y, e encontrar um fluxo máximo de s para t. Todas as arestas com o fluxo de X para 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(\sqrt{V} E). Outra abordagem é baseada no algoritmo rápido de produto de matrizes e tem complexidade O(V^{2.376})[5] o que é melhor, em teoria, para grafos suficientemente densos, mas na prática o algoritmo é mais lento.

Em um grafo bipartido ponderado, cada aresta tem um valor associado. Um acoplamento máximo ponderado bipartido[4] é definido como um acoplamento perfeito em que a soma dos valores das arestas no acoplamento tem um valor máximo. Se o grafo não é completamente bipartido, as arestas que faltam são inseridas com o valor zero. Encontrar tal acoplamento é conhecido como o problema da atribuição.

Referências

  1. BOAVENTURA NETTO, Paulo Oswaldo. Grafos. São Paulo: Edgard Blücher, 2001. ISBN 85-212-0292-X
  2. a b CERDEIRA, J. Orestes. Umas coisitas de grafos e uma introdução informal à complexidade computacional pp. 3. Página visitada em 2010-10-28.
  3. GALLAI, Tibor. (1959). "Über extreme Punkt- und Kantenmengen". Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2: 133–138.
  4. a b WEST, Douglas Brent. Introduction to Graph Theory. 2ª ed. [S.l.]: Prentice Hall, 1999. Capítulo: 3. , ISBN 0-13-014400-2
  5. Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination", Proc. 45st IEEE Symp. Foundations of Computer Science, pp. 248–255, http://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf