Diferenças

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

--- grafos:treepacking [2022/05/03 20:30] – edição externa 127.0.0.1
+++ grafos:treepacking [2022/05/03 21:06] (atual) – edição externa 127.0.0.1
@@ Linha 120: / Linha 120: @@
 </WRAP>
-** Teorema: ** Um grafo pode ser $k$-recoberto por árvores geradoras se, e somente se, para todo subconjunto de vértices $U$ temos que $|E(G[U])| \leq k(|U|-1)$.
+<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
+\]