2. Emparelhamentos (matchings)

• Emparelhamento:  conjunto de arestas duas a duas não adjacentes (ou seja, cada vértice do grafo é ponta de no máximo uma aresta do emparelhamento).
• Emparelhamento de um conjunto U de vértices:  cada elemento de U é ponta de alguma aresta do emparelhamento.
• Um emparelhamento satura um conjunto U de vértices se cada elemento de U é ponta de alguma aresta do emparelhamento. Um emparelhamento é perfeito se satura V(G).
• Que cara têm grafos dotados de emparelhamento perfeito?  Como caracterizar um emprelhamento máximo?  Essas perguntas são muito fáceis quando restritas a grafos bipartidos, mas muito mais difíceis em geral.
• Paridade (par versus ímpar) é um tema central neste capítulo.

2.1  Grafos bipartidos

• Esta seção trata de grafos bipartidos. Vamos denotar por {A, B} a bipartição de nosso grafo bipartido típico G.
• Teorema 2.1.1 (König):  Em qualquer grafo bipartido,  max |M| = min |U| , onde max é sobre todos os emparelhamentos M e min é sobre todas as coberturas U.
• Cobertura (= vertex cover):  conjunto de vértices que contém pelo menos uma das pontas de cada aresta do grafo.
• Parte S de A satisfaz a condição de Hall se |N(S)| ≥ |S|.
• Teorema 2.1.2 (Hall):  Existe emparelhamento que satura A  se e só se  todo subconjunto de A satisfaz a condição de Hall.
• Corolário 2.1.3:  Todo grafo bipartido G é k-regular com k ≥ 1 tem um emparelhamento perfeito.

2.2  Grafos arbitrários

• Nesta seção, os grafos são arbitrários. O número de componentes ímpares de um grafo G será denotado por q(G).
• Parte S de A satisfaz a condição de Tutte se q(G−S) ≤ |S|.
• Teorema 2.2.1 (Tutte):  G tem emparelhamento perfeito  se e só se  todo conjunto de vértices satisfaz a condição de Tutte.
• Como caracterizar a maximalidade de um emparelhamento? O teorema seguinte vai levar à resposta.
• Teorema 2.2.3 (versão simplificada do teorema de Gallai e Edmonds):  Todo G tem um conjunto S de vértices tal que
  1. algum emparelhamento é subconjunto de E(S, V−S) e satura S,
  2. todo componente de G − S é hipoemparelhável.
• G é hipoemparelhável (= factor-critical) se, para todo vértice v, o grafo G−v tem emparelhamento perfeito.
• Corolário do Teorema 2.2.3:  G tem emparelhamento perfeito  se e só se  |S| = |G−S| no enunciado do Teorema 2.2.3.
• Corolário XY do Teorema 2.2.3:  Existe um emparelhamento M, um conjunto X de vértices, e uma partição Y₁, … , Y_k de V(G) − X  tais que não existe aresta de Y_i a Y_j quando i ≠ j  e

  |M| = |X|  +  ⌊½|Y₁|⌋ + …  + ⌊½|Y_k|⌋ ,

  onde ⌊x⌋ é o maior inteiro abaixo de x.

2.3  Coberturas por caminhos

• Esta seção estuda os teorema de Dilworth e de Gallai & Milgram. Esses teoremas tratam de uma generalização do conceito de emparelhamento em que as arestas do emparelhamento são substituídos por caminhos orientados. Para tratar desse assunto, é preciso trocar grafos por grafos orientados.
• Um grafo orientado é um objeto que tem a mesma definição que um grafo com uma exceção: as arestas são pares ordenados de vértices. Um caminhos é orientado se todas as suas arestas apontam do vértice anterior para o seguinte do caminho. Um ciclo orientado é definido de maneira análoga. Usaremos as palavras digrafo, dicaminho e diciclo como sinônimos de grafo orientado, caminho orientado e ciclo orientado respectivamente.

  Dois vértices x e y de um digrafo são independentes se não são adjacentes.  Um conjunto de vértices é independente se seus elementos são dois a dois independentes.  O tamanho de um conjunto independente máximo em um digrafo G é denotado por alpha(G).

• Uma cobertura-por-dicaminhos de um digrafo é coleção de dicaminhos tal que cada vértice do digrafo pertence a um e um só dicaminho da coleção. Em outras palavras, uma cobertura-por-dicaminhos é uma coleção disjunta de dicaminhos que satura todos os vértices do digrafo.  [Teria sido melhor usar a expressão partição-em-dicaminhos (= paths-partition) no lugar de cobertura-por-dicaminhos.]
• Problema: Determinar uma cobertura-por-dicaminhos mínima.
• Teorema 2.3.1 (Gallai & Milgram): Todo digrafo G tem uma cobertura-por-dicaminhos P tal que |P| ≤ alpha(G).

  Outra formulação do teorema: existe uma cobertura-por-dicaminhos e um conjunto independente X tais que |X ∩ V(P)| ≥ 1 para todo elemento P da cobertura.

• Corolário 2.3.2 (Dilworth): Em todo digrafo acíclico transitivo, min |P| = max |A| onde min é tomado sobre todas as coberturas-por-dicaminhos e max sobre todas as anticadeias A.

  Um digrafo é acíclico se não tem diciclos.  Um digrafo é transitivo se, para cada par (xy, yz) de arestas, xz também é aresta.

  Uma anticadeia (= antichain) num digrafo é um conjunto A de vértices tal que para cada par (x, y) de elementos de A não existe dicaminho de x para y.

2.4  Teorema de Gallai sobre caminhos disjuntos

• Para qualquer conjunto A de vértices de um grafo, um A-caminho é um caminho com pelo menos uma aresta que começa e termina em A mas não tem vértices internos em A.
• Um split é uma coleção disjunta Y₁, … , Y_k de subconjuntos de V(G).  Um split é forte se não existe aresta ligando Y_i a Y_j para i ≠ j.
• A A-largura de um split é o número  |V(G)| − |Y₁| − … − |Y_k|  +  ⌊½|A ∩ Y₁|⌋ + … + ⌊½|A ∩ Y_k|⌋ .
• Teorema 2.4.1 (Gallai):  O número máximo de A-caminhos disjuntos é igual à A-largura de um split forte de largura mínima.