grafos:treepacking

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]$ empacota¹⁾ $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 ²⁾. 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 \]

¹⁾

E portanto é conexo.

²⁾

Interprete $r$ como $\{0,\ldots,r-1\}$ (conjunto com $r$ cores/elementos). Equivalente a $r$-partição.

Tabela de conteúdos

Empacotamento, recobrimento e arboricidade

Teorema do recobrimento por empacotamento

O teorema de Nash-Williams