==== Algumas propriedades de árvores normais ====


Anteiormente, estudamos a definição do que consiste uma [[.arvorenormal | árvore normal]]. Nesta seção, explicitaremos algumas propriedades que elas podem ter.

Uma árvore normal $T$ em $G$ pode ser uma ferramenta poderosa para examinar a estrutura de $G$, porque $G$ reflete as propriedades de separação de $T$:

<WRAP round box 100%>
=== Lema ===
//Seja $T$ uma árvore normal em $G$. Temos://

$(i)$ //Quaisquer dois vértices $x,y \in T$ são separados em $G$ pelo conjunto [[.deffechobaixo |$\lceil x\rceil\cap \lceil y\rceil$]];//

$(ii)$ //Se $S \subseteq V(T) = V(G)$, ou seja, se $T$ é [[.defgerador | árvore geradora]] de $G$, e $S$ é [[.deffechobaixo | fechado para baixo]] , então as [[.defcompcon | componentes conexas]] de $G-S$ são geradas pelos conjuntos [[.deffechocima | $\lfloor x\rfloor$]] com $x$ minimal em $T-S$. Isto é, todo $C$ componente conexa de $G-S$ satisfaz $V(C)=\lfloor x\rfloor$ com $x$ minimal em $C$//.

</WRAP>

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

$(i)$ Seja $P$ um [[.defCaminho|caminho]] qualquer de $x$ a $y$ em $G$, vamos mostrar que $P$ passa por $\lceil x\rceil \cap \lceil y\rceil$. Se $x$ é comparável a $y$, acabamos, pois $y \in \lceil x\rceil$ ou $x \in \lceil y\rceil$.

Caso contrário, seja $t_1,...,t_n$ uma sequência minimal de vértices em $P\cap T$ tais que $t_1=x$ e $t_n = y$ satisfazendo $t_i$ comparável a $t_{i+1}$ para todo $i$ na ordem de $T$. (Esta sequêcia existe, haja vista que o conjunto de todos os vértices em $P \cap T$,em sua ordem natural conforme ocorrem em $P$, tem esta propriedade porque  $T$ é normal e todo segmento $t_iPt_{i+1}$ está contido em $T$ ou é em um $T$-caminho)

(Note ainda que cada $t_i$, que não seja $x$ ou $y$, está na "bifurcação" dos "ramos" visto que para ir de um "ramo" para outro por vértices satisfazendo $t_i$ comparável a $t_{i+1}, \forall i$, se faz necessário passar por estas "bifurcações".)

Observe, por sua vez, que em nossa sequência mínima não podemos ter $t_{i-1}<t_i>t_{i+1}$, para qualquer $i$, pois teríamos a existência de $rTt_{i-1}Tt_i$ e de $rTt_{i+1}Tt_i$, mas como $rTt_i$ há de ser um caminho único, ou $\exists rTt_{i-1}Tt_{i+1}$ ou $\exists rTt_{i+1}Tt_{i-1}$, de qualquer maneira, $t_{i-1}$ é comparável com $t_{i+1}$, o que faz $t_i$ ser desnecessário, contrariando a proposição da sequência ser minimal.

Tem-se, portanto:

$$x=t_1>...>t_k<...<t_n=y$$

Para algum $k \in \{1,...,n\}$. Como $t_k \in \lceil x\rceil \cap \lceil y\rceil \cap V(P)$ , a prova segue.

$(ii)$ Seja $C$ uma componente conexa de $G-S$, e seja $x$ um elemento minimal de $V(C)$. Note que $V(C)$ não possui outro elemento minimal, pois se este fosse o caso e $x'$ também fosse minimal, teríamos $x$ e $x'$ incomparáveis e portanto ligados por um elemento $y$ tal que $y<x$ e $y<x'$, com $y\in S$ (já que são minimais), porém, como $C$ é conexo, existe um caminho $x-x'$ em $C$. Note que por $T$ ser árvore normal em $G$ isto gera uma contradição, pois ou há um ciclo em $T$, ou um [[.HCaminho|$T$-caminho]] ligando elementos incomparáveis.

Portanto, como todo vértice de $C$ está acima de algum elemento mínimo de $V(C)$, ele está acima de $x$.  Em outras palavras, todo elemento de $C$ é comparável a $x$, já que $T$ é árvore geradora de $G$. Por outro lado, todo vértice $y \in \lfloor x \rfloor$  está em $C$, pois como $S$ é fechado para baixo, o caminho ascendente está em $xTy$ está em $T-S$. Assim, $V(C) = \lfloor x \rfloor$.

Mostremos agora que $x$ é minimal não somente em $V(C)$, mas também em $T-S$. De fato isso acontece,pois os vértices abaixo de $x$ formam uma cadeia $\lceil t \rceil$ em $T$. 

Como $t$ é vizinho de $x$,a maximalidade de $C$ como uma componente conexa de $G-S$ implica que $t \in S$ e $t \notin \lfloor x \rfloor$,nos dando $\lceil t \rceil \subseteq S$, desde que $S$ seja fechado para baixo. Isso completa a prova de que cada componente de $G-S$ é gerado por um conjunto $\lfloor x \rfloor$ com $x$ minimal em $T-S$.

Reciprocamente, se $x$ é qualquer elemento minimal de $T-S$, ele também é claramente minimal na componente conexa $C$ de $G-S$ à qual pertence. Então, $V(C) \in \lfloor x \rfloor$ como antes, isto é, $\lfloor x \rfloor = C$. 

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

\\
----

As árvores geradoras normais também são chamadas de **árvores de pesquisa em profundidade**, devido à maneira como surgem em pesquisas feitas sobre grafos nos computadores. Este fato é frequentemente usado para provar sua existência.  A seguinte prova construtiva esclarece melhor como as árvores normais capturam a estrutura de seus grafos hospedeiros


<WRAP round box 100%>
=== Proposição ===
//Todo grafo [[.defconexo | conexo]] contém uma árvore geradora normal com qualquer um de seus vértices como [[.defraiz | raiz]].//
</WRAP>

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


Seja $G$ um grafo conexo e $r \in G$ um seu vértice qualquer. Seja $T$ a árvore maximal normal com raiz em $r$, vamos mostrar que $V(T)=V(G)$.


Suponha que não, e seja $C$ um componente de $G-T$. Como $T$ é normal, $N(C)$ é uma cadeia em $T$(se não fosse e existissem vértices incomparáveis em $N(C)$ existiria um $T$-caminho ligando-os por $C$). Seja, então, $x \in N(C)$ uma folha de $T$, isto é, seu maior elemento, e $y \in C$ adjacente a $x$. Mostraremos que $T':=T \cup \{y\}$ (com a aresta $x-y$) com raiz em $r$ é também árvore normal em $G$.

Seja $P$ um $T'$-caminho em $G$. Se as extremidades de $P$ estão em $T$, então $P$ é um $T$-caminho e como $T$ é normal em $G$ as extremidades são comparáveis. Se não, uma das extremidades é $y$. Suponhamos que $P$ ligue $y$ a um elemento $z \in T \subset T'$ incomparável a $y$, então existiria $T$-caminho $P'$ tal que $zP'yP'x$, contradição! Portanto $T'$ é normal em $G$, contrariando $T$ maximal e terminamos.

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

----



[[.tessssteee | teste]]