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 $\mathrm{\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 $\mathrm{\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^{\prime }=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^{\prime }$ sem ciclos e conexo, isto é, uma árvore. Como o processo não envolve remoção de vértices, temos que $G^{\prime }$ é 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^{\prime }$ possui pelo menos uma aresta a menos que $G$, então temos que $m^{\prime }<n-1$, e como $G^{\prime }$ é 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)\ge 2$. Assim, $u$ possui um vizinho $w$ em $P$ e um outro vizinho $w^{\prime }\ne w$. Caso $w^{\prime }\notin P$, então obtemos um caminho $P^{\prime }$ de $w^{\prime }$ a $v$ maior que $P$. Logo, $w^{\prime }$ deve pertencer a $P$. Mas o caminho $P[u,w^{\prime }]$ juntamente a aresta $u{w}^{\prime }$ 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)\ge 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^{\prime }$ um corte de arestas de $G$. Então toda árvore geradora $T$ de $G$ é tal que $E(T)\cap E^{\prime }\ne \varnothing$.

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

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

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