Diferenças

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

--- grafos:treepacking [2022/05/03 20:50] – gustavo
+++ grafos:treepacking [2022/05/03 21:06] (atual) – edição externa 127.0.0.1
@@ Linha 121: / Linha 121: @@
 <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 árvore geradora. 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.
+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 $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)$.
+** 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 : **
@@ Linha 138: / Linha 141: @@
           * 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
+\]