Definição: Floresta e Árvore

Classicamente, um grafo acíclico, que não contém nenhum ciclo, é chamado de Floresta. Assim, uma floresta é um grafo que também não possui ciclos como subgrafos, de modo que suas componentes conexas são chamadas Árvores.

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

Definição

Uma árvore na qual podemos distinguir um determinado vértice, denominado vértice raiz, é chamada de árvore enraizada.

Definição: Nível e Altura

O nível de um vértice $x$ em uma árvore enraizada é igual à 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.