Árvores


Um grafo G=(V, A) diz-se completo, quando quaisquer que sejam dois dos vértices em V, há uma aresta em A que os liga, isto é, cada vértice é adjacente de todos os outros.

Um grafo completo com 3 vértices V={A, B, C} tem pelo menos 3 arestas: {AB, AC , BC} é parte de A. Um grafo completo de 4 vértices A, B, C e D tem pelo menos 6 arestas: AB, AC, AD, BC, BD, CD.

No que segue e em todos os problemas apresentados, quando falamos de grafo completo estamos a falar de grafos em que entre dois vértices quaisquer só há uma aresta que os une (e não nos preocupa o sentido) - poderíamos falar de configuração completa mínima.

Um grafo G=(V, A) é uma árvore quando é conexo e sem circuitos. De outro modo, podemos dizer que G é uma árvore ou quando é conexo e o seu número de arestas é igual ao número de vértices subtraído de uma unidade (tem #V -1 arestas). Uma árvore é um grafo tal que por adição de uma aresta admite um circuito.

Dado um qualquer grafo conexo, G=(V, A), tem interesse particular a consideração do subgrafo conexo que, sendo árvore, contém todos os vértices de G. Chama-se a este subgrafo árvore abrangente de G=(V, A).

Dado o grafo completo

são exemplos de árvores abrangentes desse grafo

Podemos desenhar outras árvores abrangentes sobre esse grafo. Vale a pena ainda verificar que a cada uma dessas árvores corresponde um circuito de Hamilton sobre o grafo inicial, bastando para isso considerar um aresta de fecho.

À árvore da esquerda A-B-D-C basta acrescentar a aresta CA para obtermos um circuito hamilotniano sobre o grafo de partida. Assim, determinar (e contar) árvores abrangentes é determinar (contar) circuitos hamiltonianos.

Dado um grafo G=(V, A) completo de quatro vértices como o considerado acima, podemos determinar a totalidade das árvores abrangentes a começar em A por um processo já conhecido de todos. Assim:

sendo que os circuitos hamiltonianos (a começar e a acabar em A) correspondentes são

 

Pelo mesmo processo, se obtêm as árvores a começar em B, .... Ao todo (árvores, ou correspondentes circuitos hamiltonianos),

(3x2 a começar em A, 3x2 a começar em B, 3x2 a começar em C, 3x2 a começar em D)

4x3x2 = 24 árvores (ou circuitos hamiltonianos). Se não considerarmos os sentidos, os circuitos ABCA é o mesmo que ACBA. E é por isso que consideramos que o número de circuitos hamiltonianos num grafo completo de 4 vértices, o número de circuitos hamiltonianos diferentes é metade de 4x3x2, isto é 12. É claro que (a começar e a acabar em vértices diferentes, embora) muitos destes circuitos são repetidos quando pensamos que eles utilizam as mesmas arestas (considerados como subgrafos, diriamos que eles representam subgrafos isomorfos...)

De um modo geral, dizemos que para um grafo completo de n vértices encontramos n(n-1)(n-2)...3.2 árvores abrangentes e n(n-1)(n-2)....3 circuitos hamiltonianos diferentes.


Tarefas 2.2.2

(a)Prove que as diferentes definições de árvore são equivalentes.

 (b)

 

 

 

 

 

 

 
Quantos pentágonos estão desenhados na figura?
Quantas arestas? Podia saber quantas eram sem as contar?
 
Será que este grafo ao lado (que é planar) é isomorfo do grafo do dodecaedro de William Hamilton?
Indique uma árvore abrangente do grafo bem como o correspondente circuito de Hamilton.
Este grafo não é completo. Porquê? Para que um grafo de 20 vértices seja completo, quantas arestas no mínimo deve ter ? Um grafo conexo completo de 20 vértices quantos circuitos de Hamilton admite.
Este grafo não admite um circuito de Euler. Porquê?


voltar ao sumário