Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Árvores geradoras de grafos

Esta página trata apenas de grafos.  Os conceitos aqui discutidos não fazem sentido em digrafos não simétricos.

Árvore geradora

Uma subárvore de um grafo G é qualquer árvore T que seja subgrafo de G. Em outras palavras, um árvore T é subárvore de G se todo vértice de T é vértice de G e toda aresta de T é aresta de G.

Uma  subárvore geradora  ou  árvore geradora  (= spanning tree)  de um grafo G é qualquer subárvore de G que contenha todos os vértices de G.

É claro que somente grafos conexos têm árvores geradoras.  Reciprocamente, todo grafo conexo tem uma árvore geradora.  (Em geral, um grafo conexo tem muitas árvores geradoras diferentes.)

Exercícios

1. Exiba uma árvore geradora do grafo   0-2 0-5 1-2 3-4 4-5 3-5 1-3.
2. Exiba uma árvore geradora em cada componente do grafo definido pelo conjunto de arestas abaixo.

   3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4

3. Seja C um ciclo não trivial num grafo conexo G. Seja T uma árvore geradora de G. É verdade que todas as arestas de C exceto uma estão em T?

Algoritmos que calculam árvores geradoras

É fácil calcular uma árvore geradora de um grafo conexo:  a busca em profundidade e a busca em largura fazem isso.  Mais precisamente, qualquer das duas buscas calcula uma arborescência que contém um dos arcos de cada aresta de uma árvore geradora do grafo.

Primeira propriedade da troca de arestas

Seja G um grafo e H um subgrafo gerador de G.  Para qualquer aresta h de H, vamos denotar por  H−h  o grafo que se obtém quando h é removida de H  (aplique a função GRAPHremoveE).   Para qualquer aresta e de G, vamos denotar por  H+e  o grafo que se obtém quando e é inserida em H  (aplique a função GRAPHinsertE.)

Primeira Propriedade da Troca:  Seja T uma árvore geradora de um grafo G. Para qualquer aresta e de G que não esteja em T, o grafo  T + e  tem um único ciclo não trivial.  Para qualquer aresta t desse ciclo, o grafo   T + e − t   é uma árvore geradora de G.

Exemplo:  Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja e a aresta 0-1. O único ciclo não trivial de T+e é 0-1-5-4-0. Para qualquer aresta t desse ciclo, T+e−t é uma árvore geradora.

                              0---------------1
                              |\             /|
                              | \           / |
                              |  \         /  |
                              |   4-------5   |
                              |  /         \  |
                              | /           \ |
                              |/             \|
                              3---------------2

Segunda propriedade da troca de arestas

Seja T uma árvore geradora de um grafo G.  Para toda aresta t de T, as duas componentes de T−t definem um corte em G.  Diremos que esse é o corte determinado por T−t.  A única aresta de T que atravessa o corte é t.

Segunda Propriedade da Troca:  Seja T uma árvore geradora de um grafo G.  Para qualquer aresta t de T e qualquer aresta  e  de G que atravesse o corte determinado por T−t, o grafo   T − t + e   é uma árvore geradora de G.

Exemplo:  Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta 4-5. O corte determinado por T−t tem três arestas: 0-1, 4-5 e 3-2. Se e é uma qualquer dessas arestas então T−t+e é uma árvore geradora.

                              0---------------1
                              |\             /|
                              | \           / |
                              |  \         /  |
                              |   4-------5   |
                              |  /         \  |
                              | /           \ |
                              |/             \|
                              3---------------2

Exercícios

4. Prove a seguinte caracterização de grafos conexos:  Um grafo G é conexo se e somente se todo corte em G tem pelo menos uma aresta.
5. Mostre que um grafo é bipartido se e somente se algum corte contém todas as arestas do grafo.