Cobertura de caminho
Vamos voltar mais uma vez ao teorema da dualidade de Konig para grafos bipartidos. Se orientarmos cada aresta de $G$ de $A$ para $B$, o teorema nos diz quantos caminhos disjuntos direcionados precisamos para cobrir todos os vértices de $G$: todo caminho direcionado tem comprimento $0$ ou $1$, e claramente o número de caminhos em tal uma 'cobertura de caminho' é menor quando contém tantos caminhos de comprimento $1$ quanto possível, em outras palavras, quando contém uma combinação de cardinalidade máxima.
Coloquemos a questão acima de forma mais geral: quantos caminhos em um determinado grafo direcionado serão suficientes para cobrir todo o seu conjunto de vértices? Claro, isso também pode ser feito para grafos não direcionados. Como se vê, no entanto, o resultado que provaremos é bem mais trivial no caso não direcionado, e o caso direcionado também terá um corolário interessante.
Um caminho direcionado é um grafo $P \neq \emptyset$ direcionado com vértices distintos $x_0, \dots, x_{k}$ e arestas $e_0, \dots, e_{k-1}$ tais que $e_{i}$ é uma aresta direcionada de $x_{i}$ para $x_{i+1}$, para todo $i < k$. Nesta seção, caminho sempre significará 'caminho direcionado'. O vértice $x_{k}$ acima é o último vértice do caminho $P$, e quando $\mathcal{P}$ é um conjunto de caminhos escrevemos $ter(\mathcal{P})$ para o conjunto de seus últimos vértices. Uma cobertura de caminho de um grafo direcionado $G$ é um conjunto de caminhos disjuntos em $G$ que juntos contém todos os vértices de $G$.
Teorema (Gallai & Milgram 1960)
Todo grafo direcionado $G$ tem uma cobertura de caminho $\mathcal{P}$ e um conjunto independente de vértices $\{v_{P} \mid P \in \mathcal{P}\}$ tal que $v_{P} \in P$ para cada $P \in \mathcal{P}$.
Demonstração:
Claramente, $G$ tem uma cobertura de caminho, por exemplo, por caminhos triviais. Provamos por indução em $|G|$ que para toda cobertura de caminho $\mathcal{P} = \{P_1, \dots,P_{m}\}$ com $ter(\mathcal{P})$ mínimo existe um conjunto $\{v_{P} \mid P \in \mathcal{P}\}$ como reivindicado. Para cada $i$, deixe $v_{i}$ denotar o último vértice de $P_{i}$.
Se $ter(\mathcal{P}) = \{v_1, \dots, v_{m}\}$ é independente não há mais nada a mostrar, então assumimos que $G$ tem uma aresta de $v_2$ a $v_1$. Como $P_2v_2v_1$ é novamente um caminho, a minimalidade de $ter(\mathcal{P})$ implica que $v_1$ não é o único vértice de $P_1$; seja $v$ o vértice que precede $v_1$ em $P_1$. Então, $\mathcal{P}' := \{P_1v, P_2, \dots, P_{m}\}$ é uma cobertura de caminho de $G' := G-v_1$.
Claramente, qualquer conjunto independente de representantes para $\mathcal{P}'$ em $G'$ também funcionará para $\mathcal{P}$ em $G$, então tudo o que temos a verificar é que podemos aplicar a hipótese de indução a $\mathcal{P}'$. Assim, resta mostrar que $ter(\mathcal{P}') = \{v,v_2, \dots, v_{m}\}$ é mínimo entre os conjuntos de últimos vértices das coberturas de caminhos de $G'$.
Suponha então que $G'$ tenha uma cobertura de caminho $\mathcal{P}''$ com $ter(\mathcal{P}'') \subsetneq ter(\mathcal{P}')$. Se um caminho $P \in \mathcal{P}''$ termina em $v$, podemos substituir $P$ em $\mathcal{P}''$ por $Pvv_1$ para obter uma cobertura de caminho de $G$ cujo conjunto de últimos vértices é um subconjunto próprio de $ter(\mathcal{P})$, contrariando a escolha de $\mathcal{P}$. Se um caminho $P \in \mathcal{P}''$ termina em $v_2$ (mas nenhum em $v$), nós similarmente substituímos $P$ em $\mathcal{P}''$ por $Pv_2v_1$ para obter uma contradição com a minimalidade de $ter(\mathcal{P})$. Portanto, $ter(\mathcal{P}'') \subseteq \{v_3, \dots, v_{m}\}$. Mas agora $\mathcal{P}''$ e o caminho trivial $\{v_1\}$ juntos formam uma cobertura de caminho de $G$ que contraria a minimalidade de $ter(\mathcal{P})$.
Como corolário do Teorema acima, obtemos um resultado clássico da teoria das ordens parciais. Lembre-se de que um subconjunto de um conjunto parcialmente ordenado $(P, \leq)$ é uma cadeia em $P$ se seus elementos são comparáveis aos pares; é uma anticadeia se eles são incomparáveis aos pares.
Corolário (Dilworth 1950)
Em todo conjunto finito parcialmente ordenado $(P, \leq)$, o número mínimo de cadeias com união $P$ é igual à máxima cardinalidade de uma anticadeia em $P$.
Demonstração:
Se $A$ é uma anticadeia em $P$ de máxima cardinalidade, então claramente $P$ não pode ser coberto por menos de $|A|$ cadeias. O fato de que as $|A|$ cadeias serão suficientes decorre do teorema anterior aplicado ao grafo direcionado em $P$ com o conjunto de arestas $\{(x,y) \mid x < y\}$.
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 52-53. Acesso em 15/05/2023.