# Teorema de Booth

O Teorema de Booth é um resultado na teoria dos grafos, especificamente no estudo de emparelhamentos em grafos bipartidos. O teorema estabelece uma condição necessária e suficiente para um emparelhamento ser máximo, sendo utilizado em algoritmos de emparelhamento, como o algoritmo de Hopcroft-Karp.

### Enunciado

Seja $G=(U,V,E)$ um grafo bipartido e $M$ um emparelhamento em $G$. Um vértice é denominado deficiente se não está emparelhado em $M$. O teorema afirma que:[
   Um emparelhamento $M$ é máximo se e somente se não existe um caminho alternante que comece e termine em vértices deficientes e tenha um número ímpar de arestas.

### Conceitos Relacionados

* Um caminho alternante é um caminho no qual as arestas alternam entre pertencentes e não pertencentes ao emparelhamento $M$.
* Se existir um caminho alternante entre dois vértices deficientes, então o emparelhamento $M$ não é máximo, ao ser possível aumentá-lo.
* Caso contrário, $M$ é um emparelhamento máximo.
Este teorema está íntimo a algoritmos de emparelhamento máximo em grafos bipartidos, como o algoritmo de Hopcroft-Karp, que resolve o problema em tempo $O(|E|{\sqrt {|V|}})$.

## Introdução

O Teorema de Booth é um resultado na Teoria dos Grafos que caracteriza a existência de um emparelhamento máximo em grafos bipartidos. O teorema estabelece uma condição necessária e suficiente baseada na existência de caminhos alternantes, permitindo determinar se um emparelhamento pode ser expandido.
Este resultado é fundamental para o estudo de emparelhamentos em grafos e possui aplicações em diversos problemas de otimização, como a alocação de recursos, designação de tarefas e problemas de casamento estáveis. Além disso, o teorema é uma peça central em algoritmos eficientes para encontrar emparelhamentos máximos, como o Algoritmo de Hopcroft-Karp, que resolve o problema em tempo $O(|E|{\sqrt {|V|}})$.

## Formulação Matemática

Seja $G=(U,V,E)$ um grafo bipartido, onde $U$ e $V$ são os conjuntos de vértices e $E$ o conjunto de arestas. Um subconjunto de arestas $M\subseteq E$ é um emparelhamento se nenhum vértice pertence a mais de uma aresta em $M$. Um vértice é dito deficiente se não pertence a nenhuma aresta de $M$.
O Teorema de Booth afirma que:
   Um emparelhamento $M$ é máximo se e somente se não existe um caminho alternante de comprimento ímpar entre dois vértices deficientes.
Um caminho alternante é um caminho em que as arestas alternam entre pertencentes e não pertencentes ao emparelhamento $M$.
Se existir um caminho alternante de comprimento ímpar entre dois vértices deficientes, então $M$ não é máximo, por ser possível aumentar o emparelhamento trocando as arestas ao longo do caminho. Caso contrário, $M$ é um emparelhamento máximo.

## Demonstração

A demonstração do Teorema de Booth baseia-se no conceito de caminhos aumentantes e na relação entre emparelhamentos e estruturas alternantes num grafo bipartido.

#### Passo 1: Definições Importantes

Seja $G=(U,V,E)$ um grafo bipartido e $M$ um emparelhamento (ou seja, um subconjunto de $E$ no qual nenhum vértice pertence a mais de uma aresta de $M$).
* Um vértice deficiente é um vértice que não pertence a nenhuma aresta de $M$.
* Um caminho alternante é um caminho no qual as arestas pertencem alternadamente a $M$ e a $E\backslash M$.
* Um caminho aumentante é um caminho alternante que começa e termina em vértices deficientes.

#### Passo 2: Necessidade da Condição

Se existir um caminho aumentante de comprimento ímpar entre dois vértices deficientes, então $M$ não pode ser um emparelhamento máximo. Isso ocorre porque podemos aumentar o número de vértices emparelhados trocando as arestas ao longo do caminho.
Dado um caminho aumentante $P$, podemos construir um novo emparelhamento $M'$ a partir de $M$da seguinte forma:
* Removemos de $M$ todas as arestas de $P$ que pertencem a $M$.
* Adicionamos a $M$ todas as arestas de $P$ que pertencem a $E\backslash M$.
Como $P$ tem um número ímpar de arestas e começa e termina em vértices deficientes, a operação acima aumenta o tamanho de $M$, contradizendo a suposição de que $M$ era máximo.

#### Passo 3: Suficiência da Condição

Agora, suponha que não exista um caminho aumentante de comprimento ímpar. Vamos mostrar que $M$ deve ser um emparelhamento máximo.
Se $M$ não fosse máximo, então existiria um emparelhamento $M'$ tal que $|M'|>|M|$. A diferença entre os dois emparelhamentos $M'\backslash M$ e $M\backslash M'$ forma uma coleção de caminhos alternantes e ciclos alternantes.
* Como $|M'|>|M|$, pelo menos um desses caminhos alternantes conectaria dois vértices deficientes.
* Se esse caminho fosse de comprimento ímpar, ele seria um caminho aumentante, contradizendo a hipótese de que tais caminhos não existem.
Portanto, se não houver caminhos aumentantes de comprimento ímpar, então $M$ deve ser um emparelhamento máximo.

#### Conclusão

O Teorema de Booth está demonstrado, pois provamos que:
* Se existir um caminho alternante de comprimento ímpar entre vértices deficientes, então o emparelhamento $M$ não é máximo.
* Se não existir tal caminho, então $M$ é máximo.
Isso confirma a condição necessária e suficiente do teorema. ∎

## Aplicações do Teorema de Booth

O Teorema de Booth tem diversas aplicações dentro da Teoria dos Grafos, especialmente no estudo de emparelhamentos em grafos bipartidos e em problemas de otimização combinatória. Algumas das principais aplicações incluem:

#### 1. Algoritmos de Emparelhamento Máximo

O teorema fornece a base teórica para a eficiência de algoritmos que encontram emparelhamentos máximos em grafos bipartidos. Um exemplo é o Algoritmo de Hopcroft-Karp, que resolve o problema em tempo $O(|E|{\sqrt {|V|}})$.

#### 2. Designação de Tarefas

Em problemas onde se deseja alocar recursos ou atribuir tarefas de forma ótima, os emparelhamentos máximos são usados para encontrar a melhor distribuição possível. Exemplos incluem:
* Atribuição de trabalhadores a projetos (onde um trabalhador só pode executar certas tarefas).
* Distribuição de alunos a turmas com base em preferências e restrições.

#### 3. Problemas de Casamento Estável

Embora o Problema do Casamento Estável (Stable Marriage Problem) tenha abordagens diferentes, o teorema de Booth auxilia na formulação de problemas relacionados, como emparelhamentos ótimos entre conjuntos de agentes.

#### 4. Redes de Fluxo e Transporte

Os emparelhamentos máximos desempenham um papel importante na otimização de fluxos em redes, ajudando a resolver problemas como:
* Planeamento logístico, onde mercadorias devem ser distribuídas eficientemente.
* Gestão de tráfego, otimizando conexões entre pontos de uma rede.

#### 5. Bioinformática e Comparação de Estruturas

Na análise de sequências genéticas, os algoritmos baseados em emparelhamentos são usados para comparar estruturas moleculares e prever interações entre proteínas.
O Teorema de Booth é, portanto, uma ferramenta essencial para uma ampla gama de aplicações práticas, especialmente quando se trata de problemas de emparelhamento em grafos bipartidos.

## Conteúdos Relacionados

* Teorema de Hall
* Teorema de König
* Algoritmo de Hopcroft-Karp
* Teorema de Berge
* Algoritmos de Fluxo Máximo
* Teorema de Ford-Fulkerson

## Generalizações e Extensões
#### 1. Grafos Não Bipartidos

Embora o teorema tenha sido formulado especificamente para grafos bipartidos, muitos dos seus princípios podem ser estendidos para grafos gerais. No entanto, nesses casos, o problema do emparelhamento máximo torna-se mais complexo, exigindo abordagens diferentes, como o Algoritmo de Edmonds (Blossom Algorithm) para encontrar emparelhamentos máximos em grafos gerais.

#### 2. Emparelhamentos Ponderados

Uma extensão natural do teorema ocorre quando as arestas do grafo possuem pesos associados, levando ao problema do emparelhamento máximo de peso máximo. Algoritmos como o Hungarian Algorithm (Algoritmo Húngaro) podem ser utilizados para resolver essa variação, essencial em problemas de otimização, como atribuição de tarefas ou alocação de recursos.

#### 3. Fluxos em Redes e Caminhos Aumentantes

O conceito de caminhos aumentantes usado no Teorema de Booth tem uma forte ligação com problemas de fluxo máximo em redes, como o Teorema de Ford-Fulkerson. Isso leva a extensões do teorema para problemas que envolvem restrições de capacidade, onde cada aresta possui um limite máximo de fluxo permitido.

#### 4. Aplicações em Correspondências Estáveis

Embora o Teorema de Booth se concentre em emparelhamentos máximos, ele pode ser estendido para problemas que envolvem preferências entre os vértices, como no problema do casamento estável e no problema de alocação ótima (exemplo: alocação de estudantes a universidades com base em preferências e cotas).

#### 5. Generalizações para Hipergráfos

Outra possível extensão ocorre no contexto de hipergráfos, onde as arestas podem conectar mais de dois vértices. Aqui, o conceito de emparelhamento máximo torna-se mais complexo, e técnicas baseadas no Teorema de Booth podem ser adaptadas para encontrar coberturas mínimas e emparelhamentos ótimos.

#### 6. Algoritmos Paralelos e Computação Distribuída

Com o avanço da computação distribuída, o problema de encontrar emparelhamentos máximos em grandes grafos pode ser abordado usando algoritmos paralelos. Algumas técnicas baseadas no Teorema de Booth usam-se para projetar algoritmos eficientes para sistemas distribuídos, como redes de comunicação e processamento massivo de dados.