Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página trata apenas de grafos (ou seja, digrafos simétricos). Os conceitos aqui discutidos não fazem sentido em digrafos arbitrários.
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. É comum suprimir o "sub" e dizer que T é árvore de G.
Uma árvore geradora (= spanning tree) de um grafo G é qualquer á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.)
É 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.)
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
1-4 0-5 5-2 2-9 0-6 4-9 2-6 6-4
A maniplação de árvores geradoras de grafos usa duas operações: uma acrescenta uma aresta a uma árvore geradora e assim cria um ciclo; outra remove uma aresta da árvore geradora e assim define um corte. A figura abaixo [copiada de 'Algorithms', 4th.ed., de Sedgewick e Wayne] ilustra as duas operações.
Seja G um grafo e H um subgrafo gerador (uma árvore geradora, por exemplo) de G. Para qualquer aresta e de G, vamos denotar por H + e o grafo que se obtém quando e é inserida em H (veja a função GRAPHinsertE.) Para qualquer aresta h de H, vamos denotar por H − h o grafo que se obtém quando h é removida de H (veja a função GRAPHremoveE).
Propriedade dos Ciclos (ou Propriedade da Substituição Insere-Remove): 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.
A propósito, o único ciclo de T + e é conhecido como ciclo fundamental de e. (Ao dizer que T + e tem um único ciclo não trivial estamos supondo que dois ciclos são iguais se têm o mesmo conjunto de vértices e (1) têm o mesmo conjunto de arcos ou (2) todo arco de um é antiparalelo a um arco do outro.)
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
Para enunciar a segunda propriedade de substituição de arestas, precisamos do seguinte conceito. 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 ou corte fundamental de e.
Propriedade dos Cortes (ou Propriedade da Substituição Remove-Insere): 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
4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4
A seguinte lista de arestas define uma árvore geradora T do grafo.
4-5 5-7 0-7 2-3 1-7 0-2 6-2
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?
