==== Primeiras definições e algumas equivalências ====

[[.arvGraph |Anteriormente]], introduzimos o conceito básico de Árvores e Florestas. Vamos relembrar alguns pontos importantes aqui para entender algumas equivaléncias.
----

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

À luz desta definição, não é difícil concluir, por exemplo, que o grafo da figura abaixo é uma árvore. 

{{ :grafos:arvore.png?200 |}}

Aliás, não é difícil verificar que esse grafo satisfaz as seguintes propriedades:

  * Entre quaisquer dois de seus vértices existe um único [[.defcaminho | caminho]] que os possui como extremidades;
  * Toda aresta é um [[.separar | separador]] do grafo;
  * Se $x,y$ são dois vértices não adjacentes, o grafo obtido a partir desse com a adição da aresta $xy$ possui um ciclo;
  * Suas quantidades de vértices e de arestas diferem em uma unidade.

Como veremos com o auxílio do resultado abaixo, essas propriedades poderiam ser utilizadas como definições alternativas de árvores:

\\

<WRAP round box 100%>
=== Teorema: Equivalências ===
//Seja $T = (V,A)$ um grafo qualquer. Então, as seguintes afirmações são equivalentes: // 

$(i)$ //$T$ é uma árvore.//

$(ii)$ //Dados $x,y\in V$, existe um único [[.defCaminho|caminho]] em $T$ que possui $x$ e $y$ como extremidades. Tal caminho é comumente denotado por $xTy$.//

$(iii)$ //$T$ é minimalmente [[.conexidad| conexo]], isto é, $T$ é conexo mas $T - e$ é um grafo desconexo para toda aresta $e\in A$.//

$(iv)$ //$T$ é maximalmente acíclico, ou seja, $T$ não possui ciclos como subgrafos, porém, se $x,y \in V$ são vértices não [[grafos:definicaografos#adjacencia | adjacentes]], o grafo $T+xy$ admite um ciclo.//
</WRAP>


<WRAP round box 100%>

**//Demonstração://** 

$(i) \Rightarrow (ii)$ Inicialmente suponha que $T=(V,A)$ é uma árvore e fixe $x,y \in V$ quaisquer. Visto que $T$ é um grafo conexo, certamente existe um caminho em $T$ que possui tais vértices como extremidades. Para argumentarmos sua unicidade, suponha que existam caminhos $P$ e $Q$ distintos que possuem $x$ e $y$ como extremidades.

Enumere ainda os vértices de $P$ como $\{p_1,p_2,\dots,p_n\}$ e os vértices de $Q$ como $\{q_1,q_2,\dots,q_m\}$ de modo que $p_1=q_1 = x$, $p_n=q_m = y$ e $p_ip_{i+1},q_jq_{j+1}\in A$ para quaisquer $1 \leq i < n$ e $1 \leq j < m$. Uma vez que $P$ e $Q$ são distintos, deve haver $1 \leq i < \min \{m,n\}$ tal que $p_{i+1}\neq q_{i+1}$. Fixe $i$ mínimo com tal propriedade. Por outro lado, $y = p_n = q_m $ atesta que o conjunto de índices $\{i < j \leq n : p_j \in Q\}$ é não vazio. Ao tomarmos $j$ também como menor elemento desse conjunto, tem-se que $\{p_i,p_{i+1},p_{i+2},\dots,p_{j-1},p_j\}$ e $\{q_i,q_{i+1}, q_{i+2},\dots, q_{k-1},q_k\}$ são conjuntos de vértices de caminhos de $T$ que são disjuntos a menos de seus extremos, se $k \leq m$ é tomado de modo que $p_j = q_k$. Isso, contudo, contradiz o fato de $T$ não possuir um ciclo como subgrafo. Logo, entre $x$ e $y$ deve haver um único caminho em $T$.

$(ii) \Rightarrow (iii)$ Suponha agora que quaisquer dois vértices de $T$ são extremidades de um único caminho em $T$ e fixe $e\in A$ uma aresta qualquer, denotando por $x$ e $y$ suas extremidades. A aresta $e$, portanto, descreve o único caminho em $T$ entre os vértices $x$ e $y$. Logo, no grafo $T\setminus e$ não deve haver um outro caminho que possui esses mesmos vértices como extremidades. Isto é, $T\setminus e$ é um grafo desconexo, verificando a minimalidade de $T$ como grafo conexo. 

$(iii) \Rightarrow (iv)$ Suponha agora que $T$ é um grafo minimalmente conexo. Por um momento, suponha que existam $v_1,v_2,\dots,v_n\in V$ vértices que, nessa ordem, configuram um ciclo em $T$. Denote por $e$ a aresta entre os vértices $v_1$ e $v_n$ e fixe $x,y\in V$ quaisquer. Como $T$ é um grafo conexo, existe $u_1,u_2,\dots,u_m \in V$ vértices que, nessa ordem, são um caminho entre $x = u_1$ e $y = u_m$. Se $e \neq u_iu_{i+1}$ para todo $1 \leq i < m$, então $x$ e $y$ são vértices da mesma componente conexa de $T\setminus e$. Caso contrário, para algum $1 \leq i < m$, tem-se que (sem perda de generalidade) $u_i = v_1$ e $u_{i+1} = v_n$. Portanto, em $T\setminus e$, vale que:
  * $x$ e $v_1$ pertencem à mesma componente conexa, como atestado pelo caminho formado pelos vértices $u_1,u_2,\dots,u_i$.
  * $v_1$ e $v_n$ pertencem à mesma componente conexa, como atestado pelo caminho formado pelos vértices $v_1,v_2,\dots,v_n$.
  * $v_n$ e $y$ pertencem à mesma componente conexa, como atestado pelo caminho formado pelos vértices $u_{i+1},u_{i+2},\dots,u_m$.
Portanto, $x$ e $y$ são vértices de uma mesma componente conexa de $T\setminus e$. Ou seja, provamos que o grafo $T\setminus e$ é conexo, contradizendo a minimalidade de $T$. Logo, $T$ não pode conter um ciclo como subgrafo. Além disso, mesmo que $x,y \in V$ sejam vértices não adjacentes em $T$, a conexidade desse grafo nos garante que existe $P$ um caminho em $T$ que possui esses dois vértices como extremos. A adição de uma aresta entre $x$ e $y$ no grafo, consequentemente, torna este caminho um ciclo. Logo, $T$ é um grafo maximalmente acíclico. 

$(iv) \Rightarrow (i)$Finalmente, suponha que $T$ é um grafo maximalmente acíclico. Em particular, $T$ é uma floresta, de modo que, para provarmos que essa é uma árvore, resta-nos concluir que $T$ é conexo. Para tanto, sejam $x,y\in V$ quaisquer. Se $xy \in A$, há trivialmente um caminho de $G$ que os possui como extremidades. Se não, o grafo $T+xy$ admite um ciclo $C$ por hipótese. Como $T$ não possui ciclos como subgrafos, podemos tomar $C$ como tendo conjunto de vértices $\{v_1,v_2,v_3,\dots,v_n\}$ conectados nessa ordem e de modo que $v_1 = x$ e $v_2 = y$. Assim, $v_1,v_2,\dots,v_n$ são vértices que, nessa ordem, define um caminho que possui $x$ e $y$ como extremidades. Isso finaliza a verificação de que $T$ é conexo, e portanto, $T$ é uma árvore.

<wrap right>$\square$</wrap>
</WRAP>

O Teorema acima é responsável por diversas consequências no estudo de árvores. Por exemplo, dado $G$ um grafo conexo, um subgrafo [[.defgerador | gerador]] de $G$ minimalmente conexo deve ser uma árvore, pelo item $(iii)$ do teorema acima. Tal árvore é comumente dita ser uma **árvore geradora** de $G$. Na grafo da figura abaixo, por exemplo, uma árvore geradora está indicada com as arestas em vermelho.

{{ :grafos:exemplogeradora.png?200 |}}  


\\
----

Como outras consequências, o Teorema acima nos permite descrever um algoritmo para a construção de qualquer árvore (finita) e caracterizar esses grafos em termos de seus números de vértices e arestas:

\\

<WRAP round box 100%>
=== Corolário: Ordenação de vértices ===
// Seja $T = (V,A)$ uma árvore. Se $T$ tem $n$ vértices, podemos escrever $V = \{v_1,v_2,\dots,v_n\}$ de modo que, para todo $1 < i \leq n$, $v_i$ tem exatamente um vizinho em $\{v_1,v_2,\dots,v_{i-1}\}$.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**// 

Uma vez que $T$ é conexo, [[.enuconexo | sabemos]] que é possível escrever $V = \{v_1,v_2,\dots,v_n\}$ de modo que $T[v_1,v_2,\dots,v_i]$ é conexo para todo $1 \leq i \leq n$. Além disso, como $T$ não possui [[.defCiclo|ciclos]] como [[.subgrafos|subgrafos]], $T[v_1,v_2,\dots,v_i]$ também não possui, de modo que essa é também uma árvore para todo $1 \leq i \leq n$. No caso em que $i > 1$, a conexidade de  $T[v_1,v_2,\dots,v_i]$ implica que $v_i$ tem um vizinho em $T[v_1,v_2,\dots,v_{i-1}]$. Como esse grafo é também conexo, o item [[grafos:defarvores#teoremaequivalencias |$(iii)$]] da caracterização acima, se aplicado à árvore $T[v_1,v_2,\dots,v_i]$, nos garante que $v_i$ não pode ter mais que um vizinho em $T[v_1,v_2,\dots,v_{i-1}]$. Logo, $v_i$ tem exatamente um vizinho em $\{v_1,v_2,\dots,v_{i-1}\}$.

<wrap right>$\square$</wrap>
</WRAP>

----
\\

<WRAP round box 100%>
=== Corolário 1 ===
//Se $T$ é uma árvore e $G$ é um grafo com $\delta(G) \geq |T|-1$, então $G$ possui $T$ como subgrafo. //
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Conforme garantido pelo Corolário acima, é possível escrever $V(T) = \{v_1,v_2,\dots,v_n\}$ de modo que $v_i$ tem exatamente um vizinho em $\{v_1,v_2,\dots,v_{i-1}\}$ para todo $1 < i \leq n$, em que $n = |V(T)|$. Assim, para cada $1 \leq i \leq n$ e cada $2 \leq j \leq n$, escolha $u_i \in V(G)$ e $e_j \in A(G)$ recursivamente como se segue:
  * Considere $u_1 \in V(G)$ um vértice qualquer.
  * Suponha que, para algum $i > 1$, os vértices $u_1,u_2,\dots,u_{i-1}\in V(G)$ estão definidos. Seja $1 \leq k \leq i-1$ o índice do único vizinho de $v_i$ em $\{v_1,v_2,\dots,v_{i-1}\}$. Como $\delta(G) \geq n-1$ e $u_k$ tem no máximo $i-2 \leq n-2 < n-1$ vizinhos entre os vértices $\{u_1,u_2,\dots,u_{k-1},u_{k+1},\dots,u_n\}$, escolha um vértice qualquer $u\in N(u_k) \setminus \{u_1,u_2,\dots,u_{k-1},u_{k+1},\dots,u_n\}$ e defina $u_i = u$. Considere $e_i$ como a aresta de pontas $u_k$ e $u_i$. 

Pela escolha da enumeração $\{v_1,v_2,\dots,v_n\}$, tem-se que o subgrafo de $G$ dado por $(\{u_1,u_2,\dots,u_n\}, \{e_2,e_3,\dots,e_n\})$ é uma cópia de $T$.

<wrap right>$\square$</wrap>
</WRAP>

----
\\

<WRAP round box 100%>
=== Corolário 2 ===
//Um grafo conexo com $n$ vértices é uma árvore se, e somente se, possui $n-1$ arestas. //
</WRAP>

<WRAP round box 100%>
//**Demonstração:**// 

$(\Rightarrow)$ Suponha inicialmente que $G = (V,A)$ é uma árvore de $n$ vértices. Como antes, é então possível escrever $V = \{v_1,v_2,\dots,v_n\}$ de modo que $v_i$ compartilha apenas uma aresta com algum vértice de $\{v_1,v_2,\dots,v_{i-1}\}$ se $1 < i \leq n$. Logo, como toda aresta $v_iv_j$ (com $i < j$) é contabilizada nessa enumeração pelo vizinho de $v_j$ em $\{v_1,v_2,\dots,v_n\}$, calcula-se que $G$ tem $n-1$ arestas.

$(\Leftarrow)$ Reciprocamente, suponha que $G$ é um grafo conexo com $n$ vértices e $n-1$ arestas. Fixe $T$ uma árvore geradora de $G$. Pela definição de [[.defgerador | conjunto gerador]], $T$ também tem $n$ vértices. Logo, pelo que acabamos de provar, $T$ tem $n-1$ arestas. Em outras palavras, todas as arestas de $G$ são também arestas de $T$. Logo, $G$ e $T$ são o mesmo grafo, provando que $G$ é uma árvore.   

<wrap right>$\square$</wrap>
</WRAP>