grafos:arvgraph [WikiMat]

===== Árvores e Florestas =====

<WRAP round box 100%>
=== 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]].//
</WRAP>

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.

----

<WRAP round box 100%>
=== Teorema ===
//Um grafo $G$ é uma árvore se, e somente se, existir um e apenas um caminho entre cada par de vértices.//
</WRAP>

<WRAP round box 100%>
//**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

</WRAP>

==== Raízes e Árvoes Enraizadas ====

<WRAP round box 100%>
=== Definição ===
//Uma árvore na qual podemos distinguir um determinado vértice, denominado vértice [[.defraiz |raiz]], é chamada de árvore enraizada.//
</WRAP>

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$.

----
<WRAP round box 100%>
=== 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.//

</WRAP>
----

<WRAP round tip box 100%>
=== 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]].
</WRAP>

<WRAP round info 100%>
=== 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.
</WRAP>