Ata de Aula: 18/09/2002
Redator: Guilherme Luiz Aguiar Pedrosa
Um fator de um grafo G é um subgrafo gerador de G. Um
k-fator é um subgrafo gerador k-regular. Um componente ímpar de
um grafo é um componente de ordem ímpar. O número de componentes ímpares de um
grafo H é indicado por o(H).
Para se ter um 1-fator (ou emparelhamento perfeito), existe
uma condição óbvia necessária também suficiente (TONCAS), descoberta por Tutte,
que diz que se um grafo G tem um 1-fator, então para todos conjuntos S contidos
no conjunto de vértices de G, os componentes ímpares de G – S terão um vértice
para algo fora dele, que só poderá ser S.
Resumindo a condição: “Para todo S
subconjunto de
V(G), temos o(G – S) ≤
|S|”
Assim, com o teorema de Tutte, nós podemos exibir certificados curtos tanto quando um grafo tem um 1-fator quanto quando não tem. Se o grafo tem um 1-fator, basta exibir um emparelhamento perfeito. Se o grafo não tem um 1-fator, basta exibir um subconjunto S de V(G) cuja remoção deixa componentes ímpares em excesso.
O grafo junção de dois grafos simples G e H, escrita como G v H, é obtido ligando-se todos os vértices de um a todos do outro, preservando-se cada um dos grafos originais e respectivas arestas.
Diz que o máximo número de vértices saturados por um
emparelhamento em G é dado por minS contido em V(G){n(G) – d(S)}, onde d(S) = o(G – S) -
|S|.
Intuição: o fator d dá o número de componentes
ímpares em excesso. Através desse excesso, é possível
saber o tamanho do emparelhamento máximo.
Todo grafo regular com grau par positivo tem um 2-fator.
Algoritmo para se obter em tempo polinomial (o algoritmo original custava O(n4) o problema de se achar emparelhamento máximo em grafos, através de sucessivas contrações de blossoms (“corolas”) e resolvendo-se um problema reduzido.