grafos:treepacking [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
====== 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 : 

<WRAP center round info 90%>
Um **empacotamento** de grafos ([[grafos:defarvore|árvores]]) $T_1,...,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,...,T_n$ são cópias isomorfas destes grafos, realizados como subgrafos de $G$, cobrindo todas as arestas  de $G$. 
</WRAP>

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$**.

<WRAP center round info 90%>
Seja $\mathcal{T} \doteq (T_1,...,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,...,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}}$.
</WRAP>


** Lema: ** Seja $e_0,...,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((E portanto é conexo.)) $k$ árvores geradoras.
  * A contração $G/U$ pode ser recoberta por $k$ árvores geradoras.

===== O teorema de Nash-Williams =====

<WRAP center round info 90%>
Seja $c:\mathrm{V}(G) \to r$ uma coloração (( Interprete $r$ como $\{0,...,r-1\}$ (conjunto com $r$ cores/elementos). Equivalente a $r$-partição.)). Uma aresta é dita **de cruzamento** se suas extremidades tem cores distintas.
</WRAP>

** 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.
  * [[grafos:inflacao_minor|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],...,[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.

<WRAP center round tip 90%>
<WRAP group>
Temos as seguintes condições necessárias para empacotamento de $k$-árvores geradoras:
<WRAP half column>
  * **[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.
</WRAP>
<WRAP half column>
  * **[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. 
</WRAP>
</WRAP>
</WRAP>

<WRAP group>
<WRAP half column>

** 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. 

</WRAP>
<WRAP half column>

** 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.

</WRAP>
</WRAP>

<WRAP center round tip 90%>
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. 
</WRAP>

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$.

<WRAP center round info 90%>
A **arboricidade** de um grafo $G$ é a menor quantidade de árvores geradoras de $G$ necessárias para recobrí-lo.
</WRAP>

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
\]