Diferenças

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

--- grafos:treepacking [2022/05/03 20:52] – edição externa 127.0.0.1
+++ grafos:treepacking [2022/05/03 21:06] (atual) – edição externa 127.0.0.1
@@ Linha 141: / 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
+\]