Empacotamento, recobrimento e arboricidade
O teorema de Menger associa o grau de conexidade de um grafo a existência de caminhos disjuntos (arestas). Entretanto o teorema não fornece uma maneira de encontrar tais caminhos. Considere a seguinte definição :
Um empacotamento de grafos (árvores) $T_1,\ldots,T_n$ em um grafo $G$ são subgrafos $S_i \approx T_i$ de $G$ cujas arestas são duas a duas disjuntas.
Analogamente um recobrimento de $G$ por (árvores) $T_1,\ldots,T_n$ são cópias isomorfas destes grafos, realizados como subgrafos de $G$, cobrindo todas as arestas de $G$.
Podemos nos perguntar se existe
- empacotamento ou recobrimento,
- deste ou daquele tamanho,
- por grafos desta ou daquela classe.
Suponha que podemos empacotar $k$ árvores geradoras de $G$ em $G$.
- Fixe dois vértices $a,b \in \mathrm{V}(G)$.
- Para cada $i$, temos um $T_i$-caminho entre $a$ e $b$.
- Eles serão disjuntos com relação as arestas.
Logo se temos tais árvores, ficaria fácil construir estes caminhos. Isso nos motiva a encontrar bons empacotamentos de árvores com boas propriedades.
Teorema do recobrimento por empacotamento
Seja $T$ uma árvore geradora de $G$.
- Entre dois vértices de $G$ existe um único caminho.
- Chamemos qualquer arestas fora de $T$ de corda.
- Adicionando uma corda, introduzimos um circuito $C_e$ fundamental, que inclui $e = \{a,b\}$ e todo o $T$-caminho $P$ entre $a$ e $b$.
- Note que removendo qualquer aresta $f$ de $P$ e adicionando $e$ às arestas de $T$, obtemos outra árvore geradora $T_{e,f}$, a árvore $T$ troca $e$ por $f$.
Seja $\mathcal{T} \doteq (T_1,\ldots,T_k)$ uma coleção (ordenada) de árvores. A coleção de arestas $E(\mathcal{T})$ é a reunião das arestas de cada uma destas árvores.
Uma cadeia de troca de arestas é uma sequencia de arestas $(e_0,\ldots,e_n)$ se
- $e_n$ não está em nenhuma das $T_i$.
- Para todo $i<n$, existe $1\leq j\leq k$ tal que:
- $e{i+1}$ é corda de $T_j$.
- $e_i$ é aresta de $ C_{e_{i+1}}$.
Lema: Seja $e_0,\ldots,e_n$ sequencia de troca de arestas para $\mathcal{T}$. Se $e_0$ pertence a duas árvores, então podemos encontrar família $\mathcal{T}'$ com $E(\mathcal{T}) \subsetneq E(\mathcal{T}')$.
Teorema do recobrimento por empacotamentos [Bowler-Carmesin]: Para todo multigrafo e todo $k \in \mathbb{N}$, existe uma partição $\mathcal{P}$ de $\mathrm{V}(G)$ tal que
- Para todo $U \in \mathcal{P}$, $G[U]$ empacota1) $k$ árvores geradoras.
- A contração $G/U$ pode ser recoberta por $k$ árvores geradoras.
O teorema de Nash-Williams
Seja $c:\mathrm{V}(G) \to r$ uma coloração 2). Uma aresta é dita de cruzamento se suas extremidades tem cores distintas.
Lema das arestas de cruzamento: Uma $r$-coloração de uma árvore gera ao menos $r-1$ arestas de cruzamento em $T$.
Demonstração:
- Considere $\sim$ a relação $a \sim b$ se, e somente se, o $T$-caminho que une $a$ a $b$ tem apenas vértices de mesma cor, $a$ e $b$ inclusos.
- Isso forma uma equivalência entre os vértices.
- O grafo induzido pelas classes são conexos.
- A contração de $T$, identificando estes vértices, gera uma árvore.
- A conexidade de $T$ é preservada sobre cada contração, logo o grafo resultante é conexo.
- De um ciclo $[v_1],[v_2],\ldots,[v_n]=[v_1]$ construiríamos um ciclo em $T$, um absurdo.
- Existem ao menos $r$ classes, pois $T$ foi colorido com pelo menos $r$ cores, e cores distintas produzem classes distintas.
- Temos ao menos $r-1$ arestas.
- Cada uma destas arestas foram induzidas de arestas de cruzamento.
Temos as seguintes condições necessárias para empacotamento de $k$-árvores geradoras:
- [1] Um grafo que empacota $k$ árvores geradoras é $k$-conexo.
- De fato, entre quaisquer vértices existem $k$-caminhos disjuntos (arestas).
- Removendo menos que $k$ arestas, ao menos um destes caminhos fica intacto.
- Este caminho testemunha a conexidade do grafo, removido destas arestas.
- Concluímos a $k$-conexidade.
- [2] Toda $r$-coloração gera $k(r-1)$ arestas de cruzamento.
- Como argumentamos acima, cada uma das $k$ árvores geradores terá $r-1$ arestas de cruzamento.
- Como elas estão empacotadas, não há repetição de arestas entre as árvores.
- Concluímos que existem pelo menos $k(r-1)$ arestas de cruzamento.
Teorema de Nash-Williams: A condição [2] é suficiente para que exista empacotamento de $k$ árvores geradoras.
Demonstração:
- Dado $r \in \mathbb{N}$, aplique o teorema do recobrimento por empacotamentos e obtenha uma $r$-[coloração/partição].
- O teorema conclui que
- $G[\text{vértices de certa cor}]$ é conexo, e empacota $k$ árvores geradoras.
- $G/[\text{classes dos monocromáticos}]$ é coberto por $k$ árvores geradores.
- Cada árvore tem $r-1$ arestas.
- Todas as árvores, em conjunto, tem então no máximo $k(r-1)$ arestas.
- As arestas dessas árvores correspondem à arestas de cruzamento da coloração, que por hipótese são no mínimo $k(r-1)$.
- Concluímos que as árvores são disjuntas.
- Combinando as árvores do grafo contraído com as árvores geradoras dos subgrafos monocromáticos, obtemos as árvores procuradas.
Corolário: Todo grafo $2k$-conexo por arestas empacota $k$ árvores geradoras.
Demonstração:
- À maneira do lema das arestas de cruzamento, dada uma coloração, particione os vértices em classes conexas maximais.
- Olhando agora para a contração, cujos vértices são estas classes:
- O grau dos vértices aqui devem ser no mínimo $2k$.
- Não fosse, teríamos vértices com grau $\leq 2k-1$, e remover estas $2k-1$ arestas testemunharia não $2k$-conexidade de $G$.
- As arestas acima correspondem as arestas de cruzamento desta coloração.
- Temos então no mínimo $r$ classes, com $2k$ arestas de cruzamento saindo de cada uma, o que totaliza no mínimo $\frac{1}{2}\sum_{i=1}^r 2k = kr>k(r-1)$ arestas.
- Satisfazemos então a hipótese do teorema de Nash-Williams, e portanto $G$ empacota $k$ árvores geradoras.
Suponha que $G$ (conexo) pode ser recoberto por $k$ árvores geradoras (de $G$).
- Seja $U$ coleção de vértices, e $T$ uma destas árvores geradoras.
- Note que $T[U]$ é árvore com $|U|$ vértices, e portanto $|U|-1$ arestas.
- Nesse caso o grafo $G[U]$, recoberto pelas arestas $T[U]$ com $T$ uma das $k$ árvores geradoras do recobrimento, tem no máximo $k(|U|-1)$ arestas.
O teorema a seguir afirma que a condição necessária obtida acima, para que um grafo possua recobrimento por $k$ de suas árvores geradoras, é na verdade suficiente.
Teorema: Um grafo pode ser recoberto por $k$ de suas árvores geradoras se, e somente se, para todo subconjunto de vértices $U$ temos que $|E(G[U])| \leq k(|U|-1)$.
Demonstração :
- Seja $G$ grafo tal que, para todo $U \subset \mathrm{V}(G)$, temos $|E(G[U])| \leq k(|U|-1)$.
- Seja $C$ componente conexa de $G$.
- Aplique o teorema do recobrimento por empacotamento ao grafo $C$ e natural $k$.
- O teorema fornece $\mathcal{P}$ partição dos vértices de $C$ tal que
- Toda componente monocromática admite empacotamento por $k$ árvores geradoras.
- $C/\mathcal{P}$ é coberto por $k$ árvores geradoras.
- Para cada $U \in \mathcal{P}$, note que as arestas das $k$ árvores resultam em $k(|U|-1)$ arestas, oque devem ser todas as arestas de $G[U]$.
- Combinando estas árvores com as árvores de $C/\mathcal{P}$, obtemos cobertura de $C$ por $k$ árvores geradoras de $C$.
A arboricidade de um grafo $G$ é a menor quantidade de árvores geradoras de $G$ necessárias para recobrí-lo.
Note que o teorema acima nos diz que a arboricidade de $G$ é \[ \left\lceil \sup \left\{ \frac{|E(G[U])|}{|U|-1} \, : \, U \subset \mathrm{V}(G) \right\} \right\rceil \]