Teorema de Booth

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 | | V | ) {\displaystyle O(|E|{\sqrt {|V|}})} .

Seja G = ( U , V , E ) {\displaystyle G=(U,V,E)} um grafo bipartido, onde U {\displaystyle U} e V {\displaystyle V} são os conjuntos de vértices e E {\displaystyle E} o conjunto de arestas. Um subconjunto de arestas M ⊆ E {\displaystyle M\subseteq E} é um emparelhamento se nenhum vértice pertence a mais de uma aresta em M {\displaystyle M} . Um vértice é dito deficiente se não pertence a nenhuma aresta de M {\displaystyle M} . Um emparelhamento M {\displaystyle 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 {\displaystyle M} . Se existir um caminho alternante de comprimento ímpar entre dois vértices deficientes, então M {\displaystyle M} não é máximo, por ser possível aumentar o emparelhamento trocando as arestas ao longo do caminho. Caso contrário, M {\displaystyle M} é um emparelhamento máximo.

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. Seja G = ( U , V , E ) {\displaystyle G=(U,V,E)} um grafo bipartido e M {\displaystyle M} um emparelhamento (ou seja, um subconjunto de E {\displaystyle E} no qual nenhum vértice pertence a mais de uma aresta de M {\displaystyle M} ). Se existir um caminho aumentante de comprimento ímpar entre dois vértices deficientes, então M {\displaystyle 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 {\displaystyle P} , podemos construir um novo emparelhamento M ′ {\displaystyle M'} a partir de M {\displaystyle M} da seguinte forma: Como P {\displaystyle 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 {\displaystyle M} , contradizendo a suposição de que M {\displaystyle M} era máximo.

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: 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 | | V | ) {\displaystyle O(|E|{\sqrt {|V|}})} . 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: 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. Os emparelhamentos máximos desempenham um papel importante na otimização de fluxos em redes, ajudando a resolver problemas como:

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