===== Árvores e Florestas =====
=== Definição: Floresta e Árvore ===
//Classicamente, um grafo acíclico, que não contém nenhum [[.defCiclo|ciclo]], é chamado de [[.deffloresta | Floresta]]. Assim, uma floresta é um grafo que também não possui ciclos como [[.subgrafos| subgrafos]], de modo que suas [[.defCompCon|componentes conexas]] são chamadas [[.defarvore | Árvores]].//
Os vértices de grau 1 em uma árvore são suas [[.folhas |folhas]], os outros são seus [[.vertinter | vértices internos]]. Toda árvore não trivial possui uma folha. Considere, por exemplo, as extremidades de um [[.defCaminho|caminho]] mais longo. Este pequeno fato costuma ser útil, especialmente em provas de indução sobre árvores: se removermos uma folha de uma árvore, o que resta ainda é uma árvore.
----
=== Teorema ===
//Um grafo $G$ é uma árvore se, e somente se, existir um e apenas um caminho entre cada par de vértices.//
//**Demonstração:**//
$(\Rightarrow)$ Se $G$ é uma árvore, então, por definição, $G$ é conexo e sem circuitos. Como $G$ é conexo, então existe um caminho entre cada par de vértices. Precisamos mostrar que este caminho é único. Vamos supor que existam dois caminhos distintos entre um par de vértices. Ora, se existem dois caminhos distintos entre um par de vértices então a união destes caminhos contém um circuito. Mas por hipótese, o grafo não possui circuitos, portanto existe apenas um caminho entre cada par de vértices.
$(\Leftarrow)$ Vamos mostrar que se existe um, e apenas um, caminho entre cada par de vértices, então $G$ é uma árvore. Como existe um caminho entre cada par de vértices, temos que $G$ é conexo. Vamos supor que $G$ contenha um circuito. A existência de um circuito no grafo implica que existe pelo menos um par de vértices $a, b$ tais que existem dois caminhos distintos entre $a$ e $b$. Mas por hipótese existe um e apenas um caminho entre cada par de vértices e portanto o grafo não tem circuitos. Por definição, um grafo conexo e sem circuitos é uma árvore
==== Raízes e Árvoes Enraizadas ====
=== Definição ===
//Uma árvore na qual podemos distinguir um determinado vértice, denominado vértice [[.defraiz |raiz]], é chamada de árvore enraizada.//
Observemos, por exemplo, as árvores de 4 vértices abaixo são enraizadas.
{{ :grafos:arv_enraiz.png?450 |}}
Em geral, o vértice raiz aparece naturalmente com a aplicação que o grafo representa. Além disso, uma árvore não enraizada é chamada de **árvore livre**.
Se representarmos uma árvore enraizada com o vértice raiz posicionado na parte superior da figura, podemos definir níveis na
árvore. Considere, por exemplo, a seguinte árvore enraizada:
{{ :grafos:arv_ex.png?400 |}}
Dizemos que o vértice raiz, $c$, está no nível zero; os vértices $b$ e $d$ no nível $1$; os vértices $a$ e $e$ no nível $2$; os vértices $f , g, h$ e $i$ no nível $3$; e $j, k, l$ e $m$ no nível $4$.
----
=== Definição: Nível e Altura ===
//O **nível** de um vértice $x$ em uma árvore enraizada é igual à [[.distancia|distância]] entre o vértice raiz e o vértice $x$.//
//A altura de uma árvore enraizada é o comprimento do maior
caminho existente na árvore a partir do vértice raiz.//
----
=== Veja também: ===
Para mais informações sobre este tópico acesse também: [[.defarvores | Árvores e Florestas: Primeiras definições e algumas equivalências]].
=== Referências ===
* Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 13–14. Acesso em 08/02/2023.
* Valeriano A. de Oliveira, Socorro Rangel, Silvio A. de Araújo. [[https://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/socorro/arvores.pdf |"Teoria dos Grafos: Árvores"]]. Acesso em 08/02/2023.