grafos:arboricitypacking [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.
===== O Teorema do Empocatamento-Cobertura e Arbocidade ====

Agora, consideramos o empacotamento e a cobertura em termos de arestas em vez de vértices. Quantas árvores geradoras **arestas-disjuntas** podemos encontrar em um determinado grafo conexo? E quantas árvores, não necessariamente arestas-disjuntas, são suficientes para cobrir todas as suas arestas? Essas duas perguntas têm dois teoremas clássicos para respondê-las. Mas, em vez de provar esses teoremas diretamente, obteremos ambos como corolários de uma bela unificação recente devida a Bowler e Carmesin: o **//Teorema da Embalagem-Cobertura//**.

Para motivar o problema de empacotamento de árvores, assuma por um momento que nosso grafo representa uma rede de comunicação e que, para cada escolha de dois vértices, queremos ser capazes de encontrar $k$ caminhos arestas-disjuntos entre eles. O [[.TeoremaMenger|Teorema de Menger]] nos diz que tais caminhos existem assim que nosso grafo for $k$-aresta-conexo, o que claramente também é necessário. Este é um bom teorema, mas não nos diz como encontrar esses caminhos; em particular, depois de encontrá-los para um par de vértices finais, não estamos necessariamente em melhor posição para encontrá-los para outro par. Se nosso grafo tiver $k$ árvores geradoras arestas-disjuntas, no entanto, sempre haverá $k$ caminhos conônicos, um em cada árvore. Uma vez armazenadas essas árvores em nosso computador, sempre seremos capazes de encontrar rapidamente os $k$ caminhos entre qualquer par de vértices.

Quando um grafo $G$ tem $k$ árvores geradoras arestas-disjuntas? Se possui, claramente deve ser $k$-aresta-conexo. A recíproca, entretanto, é facilmente vista como falsa (tente $k=2$); de fato, nem mesmo está claro que qualquer aresta-conectividade implicará a existência de $k$ árvores geradoras arestas-disjuntas. (Mas veja o Corolário $1$ abaixo).

Aqui está outra condição necessária. Se $G$ tem $k$ árvores geradoras arestas-disjuntas, então com relação a qualquer partição de $V(G)$ em $r$ conjuntos, cada árvore geradora de $G$ tem pelo menos $r-1$ **arestas-cruzadas**, arestas cujas extremidades estão em diferentes conjuntos de partições. Assim, se $G$ tem $k$ árvores geradoras arestas-disjuntas, ele tem pelo menos $k(r-1)$ arestas-cruzadas. Esta condição também é suficiente:

<WRAP round box 100%>
=== Teorema do empacotamente (Nash-Williams 1961; Tutte 1961) === 
//Um multigrafo contém $k$ árvores geradoras arestas-disjuntas se, e somente se, para cada partição $P$ de seu conjunto de vértices ele possui pelo menos $k(|P|-1)$ arestas-cruzadas.//
</WRAP>

----

O Teorema acima tem um corolário impressionante: a $2k$-aresta-conectividade é suficiente para garantir a existência de $k$ árvores geradoras arestas-disjuntas.

<WRAP round box 100%>
=== Corolário 1 ===
//Todo multigrafo $2k$-aresta-coneco tem $k$ árvores geradoras arests-disjuntas.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Cada classe em uma partição de vértice de $G$ é unida a outras classes de partição por pelo menos $2K$ arestas. Portanto, para qualquer partição em $r$ conjuntos, $G$ tem pelo menos $\frac{1}{2} \sum_{i=1}^{r} 2k=kr$ arestas-cruzadas. A afirmação segue do teorema do empacotamento acima.
</WRAP>

----

Observe que a condição quantitativa sobre arestas-cruzadas no Teorema do empacotamento acima é equivalente a perguntar o mesmo apenas para partições em conjuntos de vértices conectados: qualquer outra partição é refinada por tal partição, e se a última tiver arestas-cruzadas suficientes (mesmo que tenha mais classes) então claramente o primeiro também tem. O **teorema do empacotamento de árvores** diz, portanto, que um multigrafo tem $k$ árvores geradoras arestas-disjuntas assim que todos os seus minores de contração tiverem arestas suficientes para suportar $k$ árvores geradoras arestas-disjuntas.

Voltaremos a encontrar o Teorema $1$ acima quando falarmos sobre **Grafos Infinitos**, onde provaremos uma analogia infinita. Isso não se baseia em árvores geradoras comuns (para as quais o resultado é falso), mas em **árvores geradoras topológicas**: as estruturas análogas em um espaço topológico formado pelo grafo junto com suas extremidades, pontos no infinito que o tornam compacto.

Passemos agora ao **problema da cobertura**. Para trazer à tona sua dualidade com o problema de empacotamento, começamos reformulando o último. Digamos que alguns subgrafos dados de um multigrafo $G$ formam uma **//aresta-decomposição//** de $G$ se suas arestas definem a partição $E(G)$. Nosso problema de árvore geradora pode agora ser reformulado da seguinte forma: em quantos subgrafos geradores conexos podemos aresta-decompor $G$? Uma vez que um subgrafo gerador é conexoo se, e somente se, tiver uma aresta em cada ligação, o problema de empacotamento nesta nova forma tem uma 'dupla' reminiscência do [[grafos:defarvores#teoremaequivalencias| Teorema]] e do [[grafos:algebralinbas#teorema_1| Teorema]]: em quantos subgrafos //acíclicos//, aqueles cujo complemento atende a todos seus circuitos, podemos aresta-decompor $G$?

Digamos que alguns grafos dados, não necessariamente subgrafos de $G$, //cobrem suas arestas// se todas as arestas de $G$ estiverem em pelo menos uma delas. Nosso problema duplo, então, é para quais multigrafos $G$ podemos cobrir suas arestas por no máximo $k$ árvores.

Uma condição necessária óbvia é que todo conjunto $U \subseteq V(G)$ induz no máximo $k(|U|-1)$ arestas, não mais que $|U|-1$ para cada árvore. Ou, expressando duplamente para a condição de empacotamento da árvore, que nenhuma 'deleção minor' (subgrafo) de $G$ tem arestas demais para serem cobertas por $k$ árvores.

Mais uma vez, esta condição acaba por ser suficiente também:

<WRAP round box 100%>
=== Teorema da cobertura (Nash-Williams 1964)===
//As arestas de um multigrafo $G=(V,E)$ podem ser cobertas por no máximo $k$ árvores se, e somente se, $||G[U]|| \leq k(|U|-1)$ para todo conjunto não vazio $U \subseteq v$.//
</WRAP>

----

O menor número de árvores que podem cobrir as arestas de um grafo é a sua **//arboricidade//**. Pelo teorema da cobertura logo acima, a arboricidade de um grafo é uma medida para sua densidade local máxima: ele tem arboricidade pequena se, e somente se, 'não é denso em nenhum lugar' no sentido de que não possui subgrafo $H$ com $\varepsilon (H)$ grande.

Finalmente chegamos ao //teorema da empacotamento-cobertura//. Lembre-se que quando formamos uma contração minor $G/P$ de um multigrafo $G$, mantemos todas as arestas de $G$ entre diferentes classes de partição: arestas entre as mesmas duas classes $U,U' \in P$ tornam-se arestas paralelas de $G/P$.

<WRAP round box 100%>
=== Teorema do empacotamento-cobertura ===
//Para todo multigrafo conexo $G =(V,E)$ e todo $k \in \mathbb{N}$ existe uma partição $P$ de $V$ tal que todo $G[U]$ com $U \in P$ tem $k$ árvores geradoras arestas-disjuntas e as arestas de $G/P$G podem ser cobertas por $k$ árvores geradoras.//
</WRAP>

----

Antes de provarmos o teorema do empacotamento-cobertura, vamos deduzir, pelo teorema do empacotamento-cobertura enunciado acima, o teorema do empacotamento e o teorema da cobertura, respectivamente:

<WRAP round box 100%>
**//Demonstração do Teorema do empacotamento://**

Suponha que um multigrafo $G$ tenha pelo menos $k(|P|-1)$ arestas-cruzadas para cada partição $P$ de $V(G)$. Seja $P$ a partição fornecida pelo Teorema do empacotamento-cobertura acima, e sejam $T_1, \dots, T_{k}$ árvores geradoras de $G/P$ cobrindo suas arestas. Uma vez que $||G/P|| \geq k(|P|-1)$ , eles devem ser arestas-disjuntos. Combinando-os com as árvores geradoras disjuntas em $G[U]$ que também são fornecidas pelo teorema do emapcotamento-cobertura aacima, obtemos as $k$ árvores geradoras desejadas de $G$.
</WRAP>
----
<WRAP round box 100%>
**//Demonstração do Teorema da cobertura://**

Suponha que todo $U \subseteq V$ induz no máximo $k(|U|-1)$ arestas em $G$. Seja $C$ uma componente de $G$, e $P$ a partição de $V(C)$ fornecida pelo teorema do empacotamento-cobertura. Para cada $U \in P$, cada uma das $k$ árvores geradoras arestas-disjuntas de $G[U]$ que o teorema fornece tem $|U|-1$ arestas, de modo que todas as arestas de $G[U]$ estão nessas árvores. Combinando essas árvores com as árvores geradoras de $C/P$ que cobrem suas arestas, também fornecidas pelo Teorema do empacotamento-cobertura, obtemos $k$ árvores geradoras de $C$ cobrindo suas arestas. Estes podem ser combinados com $k$ florestas cobrindo as arestas de $G$. Adicione arestas para transformá-las nas $k$ árvores desejadas.

</WRAP>

----

Dado o poder do teorema do empacotamento-cobertura, sua prova é surpreendentemente curta e elegante. Para preparar alguma notação, considere uma árvore geradora $T$ de $G$, uma corda $e$ e uma aresta $f \in T$ em seu ciclo fundamental $C_{e}$. Então $T' = T+e-f$ é outra árvore geradora: isso é imediato do [[grafos:defarvores#corolario_2|Corolário]], porque $T'$ ainda é coneco e tem o mesmo número de arestas que $T$. Diz-se que $T'$ é obtido de $T$ **trocando** $f$ por $e$.

Agora, seja $\mathcal{T} = (T_1, \dots, T_{k})$ uma família de árvores geradoras de $G$. Chame uma sequência $e_0, \dots, e_{n}$ de arestas de **cadeia de troca** para $\mathcal{T}$ iniciada por $e_0$ se $e_{n}$ não estiver em nenhuma dessas árvores, mas para todo $i < n$ existe $j =: j(i)$ tal que $e_{i} \in \mathcal{T}$ enquanto $e_{i+1}$ é uma corda de $\mathcal{T}_{j}$ cujo ciclo fundamental em relação a $\mathcal{T}_{j}$ contém $e_{i}$.

Vamos escrever $E(\mathcal{T}) := \bigcup \{E(T) \mid T \in \mathcal{T}\}$ para qualquer uma dessas famílias.

----

<WRAP round box 100%>
=== Lema ===
//Se $e_0$ inicia uma cadeia de troca por $\mathcal{T}$ e está em duas de suas árvores, então existe uma família $\mathcal{T}'$ de $k$ árvores geradoras de $G$ tal que $E(\mathcal{T}) \subsetneq E(\mathcal{T}')$.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Escolha $e_0, \dots, e_{n}$ de comprimento mínimo entre as cadeias de troca para $\mathcal{T}$ que começam com $e_0$. Então nenhum $e_{i}$ está no ciclo fundamental, com relação a qualquer árvore em $\mathcal{T}$, de qualquer $e_{\ell}$ com $\ell > i+1$: caso contrário, poderíamos encurtar a sequência pulando de $e_{i}$ direto para $e_{\ell}$ ou $e_{\ell +1}$.

Começando com $\mathcal{T}^0 = \mathcal{T}$ defina $\mathcal{T}^{i+1}$ indutivamente para $i= , \dots, n-1$ substituindo em $\mathcal{T}^{i} = (T_{1}^{i}, \dots , T_{k}^{i})$ a árvore $T_{j}^{i}$ com $T_{j}^{i} + e_{i+1} - e_{i} =: T_{j}^{i+1}$ por $j = j(i)$ e deixando $T_{j}^{i+1} := T_{j}^{i}$ para todos os outros $j$. Observe que, para $j = j(i)$, a minimalidade de nossa sequência implica que toda aresta $e$ de $T_{j}$ em seu ciclo fundamental para $e_{i+1}$ ainda está em $T_{j}^{i}$: caso contrário, $e = e_{i'}$ para algum $i' < i$, com uma contradição para $\ell := i+1 > i'+1$. Assim, se $T_{j}^{i}$ é uma árvore geradora de $G$, como podemos assumir indutivamente, então $T_{j}^{i+1}$ também é.

Claramente, $\mathcal{T}' := (T_{1}^{n}, \dots, T_{k}^{n})$ satisfaz $E(\mathcal{T}') = E(\mathcal{T}) \cup \{e_{n}\}$.
</WRAP>

----

Agora sim podemos provar o Teorema do empacotamento-cobertura:



































<WRAP round box 100%>
//**Demonstração do Teorema do empacotamento-cobertura:**//

Seja $\mathcal{T} = (T_1, \dots, T_{k})$ uma família de $k$ árvores geradoras de $G$, escolhidas com $E(\mathcal{T})$ maximal. Seja $D$ o conjunto de todas as arestas de $G$ que iniciam uma cadeia de troca para $\mathcal{T}$. Estas incluem todas as arestas que não estão em $E(\mathcal{T})$, pois formam cadeias de troca solteiras. Seja $P$ a partição de $V$ nos vértices dos componentes de $(V,D)$.

Para a afirmação de teorema do empacotamento, seja dado $U\ in P$. Para todo $j=1, \dots, k$, seja $S_{j}$ o subgrafo de $T_{j}[U]$ formado por suas arestas em $D$. Essas florestas $S_{j}$ são arestas-disjuntas, pois, pela maximalidade de $\mathcal{T}$ e o Lema anunciado logo acima, nenhuma aresta em $D$ está em mais de um $T_{j}$. Vamos mostrar que os $S_{j}$ são conexos.

Como as arestas de $D$ formam um submultigrafo conexo em $U$, basta mostrar que para cada aresta $uu' \in D$ com $u,u' \in U$ existe um $u-u'$ caminho em $S_{j}$. Isso fica claro se $uu'$ estiver em $T_{j}$ e, portanto, em $S_{j}$. Se não estiver, então o caminho $uT_{j}u'$ ainda tem todas as suas arestas $e$ em $D$ e, portanto, está em $S_{j}$: se $e_0, \dots, e_{n}$ é uma cadeia de troca testemunhando que $e_0 = uu' \in D$, então $e, e_0, \dots, e_{n}$ é uma cadeia de troca colocando $e$ em $D$, porque $e$ está no ciclo fundamental de $e_0$ com respeito para $T_{j}$.

Como todo $T_{j}$ induz subgrafos conexos $S_{j}$ nas classes de partição de $P$, a contração desses $S_{j}$ transforma os $T_{j}$ em árvores geradoras $T_{j}'$ de $G/P$. Esses $T_{j}'$ cobrem todas as arestas de $G/P$, pois $E \setminus E(\mathcal{T}) \subseteq D$.
</WRAP>
----

O teorema do empacotamento-cobertura difere do teorema do empacotamento da árvore e do teorema da cobertura da árvore de maneira fundamental. As direções não triviais dos dois últimos teoremas obtêm, cada uma, uma afirmação estrutural sobre um grafo, a existência de um empacotamento ou cobertura, como consequência de suposições quantitativas sobre todos os seus minores de certo tipo: minores de contração para o teorema do empacotamento e deleção minores, ou seja, subgrafos, para o teorema da cobertura. Esse formato os torna interessantes: eles oferecem informações estruturais valiosas para um grafo em troca de informações quantitativas menos valiosas sobre muitos grafos menores.

O teorema do empacotamento-cobertura, em contraste, faz uma afirmação estrutural sobre cada grafo: sem necessidade de quaisquer suposições, nem quantitativas nem qualitativas.

----

<WRAP round info>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch2.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 48-51. Acesso em 15/05/2023.

</WRAP>