Árvores geradoras de grafos não-dirigidos

Este capítulo trata de duas propriedades básicas de árvores geradoras de grafos não-dirigidos. As propriedades são a base das condições de otimalidade usadas pelos algoritmos que constroem árvores geradoras de custo mínimo (MSTs).

Árvores geradoras

Uma subárvore de um grafo não-dirigido G é qualquer subgrafo de G que seja uma árvore (isto é, um grafo não-dirigido conexo sem circuitos). Uma subárvore de um grafo não-dirigido G é geradora (= spanning) se contém todos os vértices de G. (Quem sabe subárvore abrangente, ou esqueleto, seria um nome melhor.) É comum suprimir o sub e usar a expressão árvore geradora de G.

Como árvores são conexas, todo grafo não-dirigido dotado de árvore geradora é conexo. Reciprocamente, todo grafo não-dirigido conexo tem (pelo menos) uma árvore geradora. Toda árvore geradora de um grafo não-dirigido com V vértices tem exatamente V−1 arestas.

É fácil calcular uma árvore geradora de um grafo não-dirigido conexo: a busca em profundidade e a busca em largura fazem isso. Mais precisamente, qualquer das duas buscas calcula uma árvore radicada que contém um dos dois arcos de cada aresta de uma árvore geradora do grafo.

Exercícios 1

Exiba uma árvore geradora do grafo não-dirigido da figura.
Exiba uma árvore geradora do grafo não-dirigido cujas arestas são 0-2 0-5 1-2 3-4 4-5 3-5 1-3 .
[Sedgewick 17.4] Exiba uma árvore geradora de cada componente conexa do grafo não-dirigido definido pelo conjunto de arestas 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 .
Use o algoritmo de busca em profundidade para calcular uma árvore geradora do grafo não-dirigido cujas arestas são 1-4 0-5 5-2 2-9 0-6 4-9 2-6 6-4 . Repita o exercício usando busca em largura.
Seja C um circuito num grafo não-dirigido conexo G. Seja T uma árvore geradora de G. É verdade que todas as arestas de C exceto uma estão em T?
[Sedgewick 20.15] Considere o grafo não-dirigido definido pela matriz a seguir. Agora considere a árvore geradora cujas arestas são 0-2 4-3 5-3 7-4 7-0 7-6 7-1. Para cada vértice s, escreva o vetor de pais da árvore em relação à raiz s.
```
-  1  1  -  -  1  1  1
1  -  -  -  -  -  -  1
1  -  -  -  -  -  -  -
-  -  -  -  1  1  -  -
-  -  -  1  -  1  1  1
1  -  -  1  1  -  -  -
1  -  -  -  1  -  -  1 
```
Seja G um grafo não-dirigido representado por listas de adjacência. Seja T uma árvore geradora de G representada por um vetor de pais. Escreva uma função CheckMST() que receba essas informações e verifique se o vetor de pais de fato representa uma árvore geradora de G.

Cortes

O conceito de corte é muito útil no estudo de árvores geradoras de grafos não-dirigidos. Informalmente, um corte é o conjunto de arestas que liga alguma parte do grafo ao resto.

Para uma definição mais formal, começamos com o conceito de leque. O leque de um conjunto X de vértices de um grafo não-dirigido é o conjunto de todas as arestas que têm uma ponta em X e outra no complemento de X. (O complemento de X é o conjunto X de todos os vértices do grafo que não estão em X.) É claro que o leque de X é igual ao leque de X. Se X é trivial, o leque de X é vazio. (Um conjunto X de vértices é trivial se X é vazio ou X é vazio.)

Um corte (= cut) é o leque de algum conjunto não-trivial X de vértices. Dizemos que X é uma margem do corte. É claro que X também é uma margem do corte.

Exemplo A. Considere o grafo não-dirigido cujos arestas são 0-1 0-2 2-1 3-5 4-5 . Cada linha da seguinte tabela descreve um corte nesse grafo (coluna do meio) e suas margens (primeira e última colunas). O terceiro corte da tabela é vazio (embora suas margens não sejam vazias).

Exercícios 2

Mostre que um grafo não-dirigido G é desconexo se e somente se tem um corte vazio.
Escreva uma função que receba um conjunto de vértices X (representado por seu vetor característico) de um grafo não-dirigido G e devolva o grau de X, ou seja, o número de arestas do leque de X.
Faça uma lista de todos os cortes do grafo não-dirigido definido pelo conjunto de arestas abaixo.
```
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
```
Seja X um conjunto não-trivial de vértices de um grafo não-dirigido G. Critique a seguinte afirmação: X e X são cortes de G.

Duas propriedades de substituição de arestas

A manipulação de árvores geradoras de grafos não-dirigidos usa duas operações básicas: uma acrescenta uma aresta a uma árvore geradora e assim cria um circuito; outra remove uma aresta da árvore geradora e assim define um corte. Essas operações dão origem a duas propriedades de substituição de arestas (= exchange properties).

Primeira propriedade. Seja T uma árvore geradora de um grafo não-dirigido G. Para qualquer aresta e de G, vamos denotar por T + e o grafo que se obtém quando e é inserida em T. Para qualquer aresta t de T, vamos denotar por T − t o grafo que se obtém quando t é removida de T.

Propriedade dos circuitos (ou Propriedade insere-remove): Seja T uma árvore geradora de um grafo não-dirigido G. Para qualquer aresta e de G que não esteja em T, o grafo T + e tem um único circuito. Para qualquer aresta t desse circuito, o grafo T + e − t é uma árvore geradora de G.

O único circuito em T + e é conhecido como circuito fundamental de e relativo a T. (Estamos abusando um pouco da ideia de igualdade e supondo que dois circuitos com o mesmo conjunto de arestas são iguais.)

Exemplo B. Seja T a árvore geradora definida pelas arestas escuras da figura. Seja e a aresta 1-3. O circuito fundamental de e é 1-3-2-0-7-1. Para qualquer aresta t desse circuito, T + e − t é uma árvore geradora.

Segunda propriedade. Seja T uma árvore geradora de um grafo não-dirigido G. Para toda aresta t de T, as duas componentes conexas de T − t definem um corte em G: trata-se do conjunto de todas as arestas de G que têm uma ponta em uma das componentes conexas de T − t e outra ponta na outra componente conexa. Diremos que esse é o corte determinado por T − t ou corte fundamental de t relativo a T.

Exemplo C. Seja T a árvore geradora definida pelas arestas escuras da figura. Seja t a aresta 0-2. O corte fundamental de t é o conjunto de arestas 1-3 1-2 7-2 0-2 0-6 4-6. Se e é uma qualquer dessas arestas então T − t + e é uma árvore geradora.

Exercícios 3

Seja T uma árvore geradora de um grafo não-dirigido G e e uma aresta de G que não está em T. Mostre que T + e tem um único circuito.
Seja T uma árvore geradora de um grafo não-dirigido G e t uma aresta de T. Mostre que T − t tem exatamente duas componentes conexas.
Toda discussão de MSTs envolve dois grafos, T e G, um morando dentro do outro. Às vezes não fica muito claro qual é o grafo a que cada parte da discussão se refere. Por exemplo, a expressão corte fundamental de uma aresta t se refere a um corte em T ou em G? Analogamente, o circuito fundamental de uma aresta e é um circuito em T ou em G?
Suponha que T é uma árvore geradora de um grafo G. O que é um corte fundamental de G? O que é um circuito fundamental de G?
Seja G o grafo não-dirigido da figura e T a árvore geradora de G indicada pelas arestas mais escuras. Qual o circuito fundamental da aresta 4-6? Qual o circuito fundamental da aresta 0-7? Qual o corte fundamental da aresta 0-7? Qual o corte fundamental da aresta 4-6?
Considere o grafo não-dirigido da figura. Seja T a árvore dgeradora de G induzida pelas aresta mais escuras. Pergunta 1: Se e é a aresta 4-6, quais são as arestas t de T tais que T + e − t é uma árvore geradora do grafo? Pergunta 2: Se t é a aresta 7-0, quais são as arestas e do grafo tais que T − t + e é uma árvore geradora do grafo?
Circuito fundamental versus corte fundamental. Seja T uma árvore geradora de um grafo não-dirigido G. Seja t uma aresta de T e e uma aresta fora de T. Prove que t pertence ao circuito fundamental de e se e somente se e está no corte fundamental de t.