CCT-UFCA/Ciência da Computação/Teoria dos Grafos/Árvores:

Definições fundamentais

Definição: Uma árvore é um grafo conexo e acíclico.

Obs.: Toda árvore é um grafo bipartido. Uma vez que uma árvore não possui ciclos, então não possui ciclos ímpares, o que equivale a ser bipartido.

Definição: Uma floresta é um grafo acíclico.

Definição: Uma ponte, ou aresta de corte, é uma aresta cuja remoção aumenta o número de componentes conexas de um grafo em exatamente uma unidade.

Analogamente, uma articulação é um vértice cuja remoção aumenta o número de componentes conexas em uma ou mais unidades.

Definição: Uma folha em uma árvore $T=(V,E)$ é um vértice de grau 1.

Definição: Um corte de vértices em um grafo $G$ é um conjunto de vértices cuja remoção aumenta o número de componentes conexas de $G$ em pelo menos uma unidade. Analogamente, definimos corte de arestas.

Definição: Uma árvore geradora de um grafo $G=(V,E)$ é um subgrafo gerador de $G$ que é uma árvore.

Teoremas relacionados

Teorema 1: Um grafo $T=(V,E)$ é uma árvore se e somente se existe um único caminho entre qualquer par de vértices.

Prova (ida): Seja $T$ uma árvore. Vamos mostrar por absurdo que, dada uma árvore, só existe um caminho entre qualquer par de vértices.

Seja $T$ uma árvore e suponha por absurdo que existem vértices $u,v\in V(T)$ tais que $u$ e $v$ são conectados por caminhos $P_{1}$ e $P_{2}$ distintos. Nesse caso, claramente existe pelo menos um ciclo entre $u$ e $v$ em $T$ , o que é absurdo, já que assumimos que $T$ é uma árvore, e por definição, uma árvore é um grafo acíclico e conexo.

Prova (volta): Vamos mostrar por absurdo que, se $G$ é um grafo tal que $\forall u,v\in V(G)$ , existe um único caminho entre $u$ e $v$ , então $G$ é uma árvore.

Seja $G$ um grafo que atende à premissa e suponha por absurdo que $G$ não é uma árvore. Como em $G$ existe um único caminho entre qualquer par de vértices, então $G$ é conexo. Como $G$ não é uma árvore, então podemos assumir que em $G$ há um ciclo $C$ entre dois vértices $u,v\in V(G)$ arbitrários. Logo, existem caminhos internamente disjuntos $P_{1}$ e $P_{2}$ entre $u$ e $v$ , o que é um absurdo, visto que assumimos que em $G$ $G$ só há um caminho entre qualquer par de vértices.

Assim, temos que $G$ é conexo e acíclico, isto é, uma árvore.

Teorema 2: Seja $T=(V,E)$ um grafo conexo. $T$ é uma árvore se e somente se $\forall e\in E(G)$ , $e$ é uma ponte.

Prova (ida): Vamos mostrar por absurdo que se $T$ é uma árvore, toda aresta de $T$ é ponte.

Seja $T$ uma árvore e suponha por absurdo que existe $e=uv\in E(T)$ que não é ponte. Logo, existe um caminho $P$ que não contém $uv$ entre $u$ e $v$ . Logo, temos que $P+uv$ forma um ciclo em $T$ , o que é um absurdo, pois assumimos inicialmente que $T$ é uma árvore.

Prova (volta): Vamos mostrar por absurdo que se $G$ é um grafo em que toda aresta $uv\in E(G)$ é ponte, então $G$ é uma árvore. Como $G$ é conexo, basta mostrar que $G$ é acíclico, então teremos mostrado que $G$ é uma árvore.

Seja $G=(V,E)$ um grafo conexo e suponha por absurdo que $G$ não é uma árvore, isto é, que $G$ possui um ciclo $C$ e seja $u$ e $v$ dois vértices consecutivos de $C$ . Assim, existe um caminho $P$ entre $u$ e $v$ e, além disso, $u$ e $v$ são adjacentes através de $e=uv$ .

Logo, em $E(T)-e$ , $u$ e $v$ continuam conectados através de $P$ , o que é um absurdo, já que $e$ é uma ponte. Portanto, $G$ é uma árvore.

Teorema 3: Para toda árvore $T=(V,E)$ , temos que $m=n-1$ .

Prova (ida): Vamos mostrar que se $T$ é uma árvore, então $m=n-1$ , por indução em $m$ .

Caso base: Para $m=0$ , temos que $T\approx K_{1}$ e, claramente, $m=0=n-1=1-1$ .

Passo indutivo: Suponha que o teorema é válido para toda árvore com até $m=k$ arestas. Vamos mostrar que o teorema vale para toda árvore com até $m=k+1$ arestas.

Seja $T=(V,E)$ uma árvore com $m=k+1$ . Seja $e=uv$ uma aresta de $T$ . Pelo resultado anterior, sabemos que $e$ é uma ponte de $T$ . Além disso, pelo exercício, sabemos que o número de componentes de $T-e$ é exatamente igual a 2.

Sejam $T_{1}$ e $T_{2}$ tais componentes de $T-e$ . Como $T$ é acíclico, temos que $T_{1}$ e $T_{2}$ são ambos acíclicos e, além disso, conexas. Logo, são árvores com no máximo $k$ arestas. Por hipótese indutiva, temos que $m_{1}=n_{1}-1$ e $m_{2}=n_{2}-1$ , onde $m_{1}$ e $m_{2}$ são os números de arestas em $T_{1}$ e $T_{2}$ , respectivamente.

Além disso, sabemos que $m=m_{1}+m_{2}$ e $n=n_{1}+n_{2}$ . Temos, então que:

$m=m_{1}+m_{2}$ $m=(n_{1}-1)+(n_{2}-1)$ $m=(n_{1}+n_{2})-1$ $m=n-1$

Prova (volta): Vamos mostrar por absurdo que, se um grafo $G$ conexo possui $m=n-1$ arestas, então $G$ é uma árvore. Nesse sentido, como $G$ é conexo, para mostrar que $G$ é uma árvore, basta mostrar que $G$ é acíclico.

Seja $G$ um grafo com $m=n-1$ arestas tal que $G$ não é uma árvore. Como $G$ não é uma árvore, então $G$ é cíclico, possuindo pelo menos um ciclo C formado pelos caminhos $P_{1}$ e $P_{2}$ distintos entre um par de vértices $u$ e $v$ arbitrário em $G$ . Ao removermos, sem perda de generalidade, uma aresta $e$ do caminho $P_{1}$ , em $G$ , obtemos um grafo $G'=G-e$ conexo, onde $u$ e $v$ estão ainda conectados por $P_{2}$ . Se $G$ tem mais de um ciclo, então podemos repetir o processo de remoção de arestas até que obtenhamos $G'$ sem ciclos e conexo, isto é, uma árvore. Como o processo não envolve remoção de vértices, temos que $G'$ é uma árvore que possui exatamente $n$ vértices e, pela prova da ida deste mesmo teorema, sabemos que uma árvore deve possuir exatamente $n-1$ arestas. No entanto, como $G'$ possui pelo menos uma aresta a menos que $G$ , então temos que $m'<n-1$ , e como $G'$ é uma árvore, pela prova da ida deste mesmo teorema, sabemos que isso é absurdo. Logo, $G$ é uma árvore.

Teorema 4: Toda árvore com ao menos dois vértices possui pelo menos duas folhas.

Prova: Vamos mostrar por absurdo o teorema em questão.

Seja $T$ uma árvore e suponha por absurdo que $T$ possui no máximo uma folha. Além disso, seja $P$ um caminho de comprimento máximo de $T$ e sejam $u$ e $v$ as extremidades de $P$ . Assuma, sem perda de generalidade, que $d(u)\geq 2$ . Assim, $u$ possui um vizinho $w$ em $P$ e um outro vizinho $w'\neq w$ . Caso $w'\notin P$ , então obtemos um caminho $P'$ de $w'$ a $v$ maior que $P$ . Logo, $w'$ deve pertencer a $P$ . Mas o caminho $P[u,w']$ juntamente a aresta $uw'$ forma um ciclo em $T$ , o que é uma contradição, já que $T$ é uma árvore.

Logo, $u$ possui apenas $w$ como vizinho, e pelo mesmo raciocínio, podemos mostrar que $v$ possui apenas um vizinho em $T$ . Logo $u$ e $v$ são folhas de $T$ .

Corolário - Teorema 4: Toda árvore com ao menos dois vértices possui pelo menos duas folhas.

Prova: Sabemos que:

$\sum _{v\in V(T)}d(v)=2m=2(n-1)=2n-2$

Suponha por contradição que $T$ possui no máximo uma folha. Assim, teríamos que:

$\sum _{v\in V(T)}d(v)\geq 1+2(n-1)=2n-2+1=2n-1$

Isso porque, todo vértice folha possui exatamente vizinho. Se $T$ possui uma folha a menos, então possui um vértice a menos com no máximo um vizinho, o que aumenta a soma dos graus de $T$ em pelo menos uma unidade.

Com isso, as duas expressões acima são contraditórias. Ou seja, $T$ possui ao menos duas folhas.

Teorema 5: Seja $G=(V,E)$ um grafo conexo e $E'$ um corte de arestas de $G$ . Então toda árvore geradora $T$ de $G$ é tal que $E(T)\cap E'\neq \varnothing$ .

Prova: Suponha por absurdo que $E(T)\cap E'=\varnothing$ , para alguma árvore geradora $T$ e corte de arestas $E'$ de $G$ .

Sejam $G_{1}$ e $G_{2}$ duas componentes de $G$ obtidas pela remoção das arestas de $E'$ . Além disso, sejam $u\in V(G_{1})$ e $v\in V(G_{2})$ .

Como $E(T)\cap E'=\varnothing$ , então $u$ e $v$ pertencem a componentes distintas em $T$ , uma contradição.