b'\n_START_ARTICLE_\nAcoplamento (teoria dos grafos)\n_START_SECTION_\nDefini\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nDado um grafo G = (V,E), um acoplamento M em G \xc3\xa9 um conjunto arestas n\xc3\xa3o-adjacentes par-a-par; ou seja, duas arestas de M n\xc3\xa3o compartilham um mesmo v\xc3\xa9rtice. _NEWLINE_Um v\xc3\xa9rtice \xc3\xa9 dito acoplado (ou saturado) se for incidente a uma aresta no acoplamento. Caso contr\xc3\xa1rio o v\xc3\xa9rtice \xc3\xa9 n\xc3\xa3o-acoplado.\n_START_SECTION_\nAcoplamento Perfeito\n_START_PARAGRAPH_\nUm acoplamento perfeito  \xc3\xa9 um subconjunto M de arestas de um grafo G que cont\xc3\xa9m todos os v\xc3\xa9rtices de G. Isto \xc3\xa9, cada v\xc3\xa9rtice do grafo \xc3\xa9 incidente a exatamente uma aresta no acoplamento._NEWLINE_A Figura (b) acima \xc3\xa9 um exemplo de acoplamento perfeito. Todo acoplamento perfeito \xc3\xa9 m\xc3\xa1ximo e portanto maximal. Em algumas literaturas, o termo acoplamento completo \xc3\xa9 usado. Na figura acima, somente a parte (b) mostra um acoplamento perfeito. Um acoplamento perfeito \xc3\xa9 tamb\xc3\xa9m uma cobertura de arestas de tamanho m\xc3\xadnimo. Assim, , ou seja, o tamanho de um acoplamento m\xc3\xa1ximo n\xc3\xa3o \xc3\xa9 maior do que o tamanho de uma cobertura de arestas m\xc3\xadnima.\n_START_SECTION_\nAcoplamento Quase Perfeito\n_START_PARAGRAPH_\nUm acoplamento quase perfeito \xc3\xa9 aquele em que exatamente um v\xc3\xa9rtice \xc3\xa9 n\xc3\xa3o-acoplado. Isso s\xc3\xb3 pode ocorrer quando o grafo tem um n\xc3\xbamero \xc3\xadmpar de v\xc3\xa9rtices, e tal acoplamento deve ser m\xc3\xa1ximo. Na figura acima, a parte (c) mostra um acoplamento quase-perfeito. Se, para cada v\xc3\xa9rtice em um grafo, h\xc3\xa1 um acoplamento quase perfeito que omite somente aquele v\xc3\xa9rtice, o grafo \xc3\xa9 tamb\xc3\xa9m chamado de fator-cr\xc3\xadtico.\n_START_SECTION_\nAcoplamentos m\xc3\xa1ximos em grafos bipartidos\n_START_PARAGRAPH_\nProblemas de acoplamento s\xc3\xa3o frequentemente relativos a grafos bipartidos. Encontrar um acoplamento bipartido m\xc3\xa1ximo (frequentemente chamado um acoplamento bipartido de m\xc3\xa1xima cardinalidade) em um grafo bipartido  \xc3\xa9 talvez o mais simples problema. O algoritmo de caminho aumentado encontra-o, encontrando um caminho de aumento de cada  para  e adicionando-o ao acoplamento se ele existe. Como cada caminho pode ser encontrade em tempo , o tempo de execu\xc3\xa7\xc3\xa3o \xc3\xa9  . Esta solu\xc3\xa7\xc3\xa3o \xc3\xa9 equivalente a adicionar uma super fonte  com arestas para todos os v\xc3\xa9rtices em , e um super sumidouro  com arestas de todos os v\xc3\xa9rtices em  para , e encontrar um fluxo m\xc3\xa1ximo de  para . Todas as arestas com o fluxo de  para  ent\xc3\xa3o constituem um acoplamento m\xc3\xa1ximo. Uma melhoria em rela\xc3\xa7\xc3\xa3o a isso \xc3\xa9 o algoritmo de Hopcroft-Karp, que executa em tempo . Outra abordagem \xc3\xa9 baseada no algoritmo r\xc3\xa1pido de produto de matrizes e tem complexidade  o que \xc3\xa9 melhor, em teoria, para grafos suficientemente densos, mas na pr\xc3\xa1tica o algoritmo \xc3\xa9 mais lento._NEWLINE_Em um grafo bipartido ponderado, cada aresta tem um valor associado. Um acoplamento m\xc3\xa1ximo ponderado bipartido \xc3\xa9 definido como um acoplamento perfeito em que a soma dos valores das arestas no acoplamento tem um valor m\xc3\xa1ximo. Se o grafo n\xc3\xa3o \xc3\xa9 completamente bipartido, as arestas que faltam s\xc3\xa3o inseridas com o valor zero. Encontrar tal acoplamento \xc3\xa9 conhecido como o problema da atribui\xc3\xa7\xc3\xa3o.'