Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:treepacking [2022/05/03 20:13] – gustavo
+++ grafos:treepacking [2022/05/03 21:06] (atual) – edição externa 127.0.0.1
@@ Linha 1: / Linha 1: @@
-====== Empacotamento de árvores ======
+====== 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** das [[grafos:defarvore|árvores]] $T_1,...,T_n$ em um grafo $G$ são cópias isomorfas, que denotaremos por $S_i \approx T_i$, destas árvores cujas arestas são duas a duas disjuntas.
+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 destas árvores cobrindo todas as arestas ((Apenas grafos conexos nos interessam, então cobrimos os vértices também.)) de $G$.
+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>
-E suponha que podemos empacotar $k$ árvores geradoras em $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$.
@@ Linha 114: / Linha 119: @@
 </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
+\]