===== Árvores =====
<WRAP tip>
Fazer a lista de [[lista:conexidade|conexidade]] será bem proveitoso.
</WRAP>

<WRAP info>
Dizemos que um grafo $T = (V,A)$ é uma **floresta** se não possui ciclos como subgrafos. Uma floresta conexa é dita ser uma **árvore**. 
</WRAP>

**~~#~~** Observe o grafo cujo conjunto de vértices corresponde aos pontos pretos abaixo e cujas arestas estão todas representadas. Esse grafo é uma floresta? Ele possui uma floresta como subgrafo? Mais do que isso, ele possui uma floresta como subgrafo induzido? Alguma de suas componentes conexas é uma árvore? Se sim, quantas?
{{ :lista:exemploarvore.png?400 |}}

**~~#~~** Mostre que um grafo $G = (V,A)$ é uma floresta se, e somente se, dados $x,y \in V$, existe no máximo um caminho de $G$ ligando $x$ e $y$.

**~~#.#~~** Conclua que  $G = (V,A)$ é uma árvore se, e somente se, dados $x,y \in V$, existe exatamente um caminho de $G$ ligando $x$ e $y$.

<WRAP info>
Dado $G = (V,A)$ um grafo, considere uma aresta $e \in A$ e tome $C_e$ a componente conexa do grafo que contém as duas extremidades de $e$. Denote por $G[C_e] = (V',E')$ o subgrafo de $G$ induzido a $C_e$. Dizemos que $e$ é uma **ponte** de $G$ se o grafo $C_e\setminus e : = (V',E'\setminus \{e\})$ é desconexo.
</WRAP>

**~~#~~** Verifique que as arestas do grafo abaixo representadas por linhas tracejadas são pontes.
{{ :lista:pontes.png?400 |}}


**~~#~~** Mostre que um grafo $G$ é uma floresta se, e somente se, todas as suas arestas são pontes. Conclua que um grafo conexo é uma árvore se, e somente se, todas as suas arestas são pontes.

**~~#.#~~** Seja $G$ um grafo conexo. Mostre que $G$ admite uma árvore como um subgrafo que contém todos os seus vértices. Uma árvore como essa é conhecida como **árvore geradora** de $G$. Ela é única?

**~~#~~** Mostre que, se $T$ é uma árvore com $n$ vértices, então $T$ possui $n-1$ arestas.

**~~#.#~~** Mostre que, se um grafo possui $n$ vértices e $n-1$ arestas, então ele possui ao menos dois vértices de grau $1$.

**~~#.#~~** Mostre que um grafo conexo com conjunto de vértices finito é uma árvore se, e somente se, possui $n$ vértices e $n-1$ arestas.