Arborescências maximais de grafos

Esta página discute os subgrafos de um grafo que têm a estrutura de uma arborescência.

Arborescências de grafos

Um grafo H é subgrafo de um grafo D se todo vértice de H é vértice de D e todo arco de H é arco de D.   Uma arborescência de um grafo D é qualquer arborescência que seja subgrafo de D[Quem sabe teria sido melhor dizer subarborescência de um grafo.]

Uma r-arborescência T de um grafo D é maximal  (ou geradora)  todo vértice ao alcance de r em D está em T, ou seja, se não existe arco de D que tenha ponta inicial em T e ponta final fora de T[O adjetivo geradora é uma tradução inadequada de spanning. Meu uso do adjetivo geradora foge à tradição, uma vez que a expressão arborescência geradora é tradicionalmente usada apenas nos casos em que todos os vértices do grafo estão ao alcance de r.]  [Quem sabe deveríamos adotar o termo r-esqueleto no lugar de r-arborescência maximal.]

Problema da arborescência maximal:  Dado um vértice r de um grafo, encontrar uma r-arborescência maximal do grafo.

O algoritmo que resolve o problema é essencialmente o mesmo que calcula distâncias. Ele devolve o vetor de predecessores que representa a arborescência procurada.  Vamos supor que os vértices do grafo são 1,  …  , n e que o grafo é dado por suas listas de adjacência Adj[1 .. n].

Arborescência-Maximal (n, Adj, r)
11 . para u crescendo de 1 até n faça
12 .ooo pai[u] ← nil
13 . pai[r] ← r
14 . LCria-Lista(r)
15 . enquanto L não estiver vazia faça
16 .ooo uRetira-da-Lista(L)
17 .ooo para cada v em Adj[u] faça
18 .oooooo se pai[v] = nil
19 .ooooooooo então pai[v] ← u
10 .ooooooooo então  Insere-na-Lista(v, L)
11 . devolva pai[1 .. n]

Antes da primeira iteração, os pais dos vértices estão indefinidos. Esse estado indefinido é representado por nil[Como os vértices do grafo são 1,  …  , n, poderíamos usar 0 no lugar de nil.]   Em virtude do teste na linha 8, é importante que pai[r] seja diferente de nil. Esta é a razão para a linha 3.

Durante o processo iterativo, o algoritmo usa uma fila de vértices análoga à usada pelo algoritmo Distancias. Se as rotinas Cria-Lista, Retira-da-Lista e Insere-na-Lista consumirem tempo constante (isto é, uma quantidade de tempo independente do tamanho do grafo) então nosso algoritmo consumirá tempo Ο(n+m).

Exercícios 1

  1. Que acontece se eliminarmos a linha 3 do algoritmo Arborescência-Maximal?

Arcos de avanços, de retorno, e cruzados

Seja T uma r-arborescência maximal de um grafo D.  Em relação a T, os arcos de D quw estão ao alcance de r podem ser assim classificados:  um arco uv que não pertencem a T é

  1. de avanço (= forward),  se u é ancestral de v em T;
  2. de retorno (= back),  se v é ancestral de u em T;
  3. cruzado (= cross),  se u não é ancestral de v e v não é ancestral de u em T.

Cada arco ao alcance de r pertence a T ou é de um e apenas um desses três tipos.  Essa classificação é útil para discutir as propriedades de diferentes tipos de arborescências maximais, como as que veremos adiante.

Arborescência de distâncias e busca em largura

Dado um vértice r de um grafo D, uma r-arborescência das distâncias de D é qualquer r-arborescência maximal T de D que tenha a seguinte propriedade:  para todo vértice v ao alcance de r,  a distância de  r  a  v  em  T  é igual à distância de r a v em D.

Problema da arborescência das distâncias:  Dado um vértice r de um grafo D, encontrar uma r-arborescência de distâncias em D.

Para resolver o problema, basta usar uma simples adaptação do algoritmo Distâncias. O algoritmo devolve o vetor de predecessores que representa a arborescência procurada.

Arborescência-de-Distâncias (n, Adj, r)
11 . para u crescendo de 1 até n faça
12 .ooo pai[u] ← nil
13 . pai[r] ← r
14 . FCria-Fila(r)
15 . enquanto F não estiver vazia faça
16 .ooo uSai-da-Fila(F)
17 .ooo para cada v em Adj[u] faça
18 .oooooo se pai[v] = nil
19 .ooooooooo então pai[v] ← u
10 .ooooooooo então  Entra-na-Fila(v, F)
11 . devolva pai[1 .. n]

Tal como no algoritmo Distâncias, a fila de vértices F usa a política FIFO.

Uma arborescência de distâncias pode também ser chamada de arborescência de busca em largura.

Em relação a qualquer r-arborescência de distâncias, todo arco de avanço ou cruzado uv é tal que   d(v) ≤ d(u)+1,   sendo d(x) a distância de rx.

Exercícios 2

  1. Dado um vértice r de um grafo D e uma função f que atribui um número não-negativo a cada arco do grafo, uma r-arborescência de f-distâncias é qualquer r-arborescência maximal T de D que tenha a seguinte propriedade:  para todo vértice v ao alcance de r,

    a f-distância de r a v em T é igual à f-distância de r a v em D.

    Escreva um algoritmo que encontre uma r-arborescência de f-distâncias em um grafo dado. Inspire-se no algoritmo Dijkstra.

  2. Seja T uma r-arborescência de distâncias de um grafo D.  Mostre que d(v) = d(u)+1 para todo arco de avanço uv.  Mostre que d(v) ≤ d(u)+1 para todo arco cruzado uv.  O que se pode afirmar sobre arcos reversos?

Arborescências de peso mínimo

Suponha que cada arco uv de um grafo tem um peso numérico f(uv). O peso de uma arborescência do grafo é a soma dos pesos de seus arcos. O peso de uma arborescência T será denotado por f(T).  Diremos que uma r-arborescência maximal T tem peso mínimo se

f(T)  ≤  f(T′)

para toda r-arborescência maximal T′ do grafo.

Problema da arborescência maximal de peso mínimo:  Dado um vértice r de um grafo cujos arcos têm pesos numéricos, encontrar uma r-arborescência maximal de peso mínimo.

O problema também é conhecido como optimum branchings problem.  A solução do problema é muito interessante mas não muito fácil.  Veja a seção 4.9 de KT.

Exercícios 3

  1. Mostre que uma r-arborescência de f-distâncias não tem peso mínimo.
  2. Difícil mas interessante:   Escreva um algoritmo para resolver o problema da r-arborescência maximal de peso mínimo.

Arborescência de busca em profundidade

Busca-em-Profundidade (n, Adj, r)
. para u crescendo de 1 até n faça
.ooo cor[u] ← branco
.ooo pai[u] ← nil
. B-em-Prof (r, cor)
. devolva pai[1 .. n]
B-em-Prof (u, cor)
11 . cor[u] ← cinza
12 . para cada v em Adj[u] faça
13 .ooo se cor[v] = branco
14 .oooooo então pai[v] ← u
14 .oooooo então B-em-Prof (v, cor)
15 . cor[u] ← preto

Em relação a qualquer r-arborescência de busca em profundidade, todo arco reverso pertence a um ciclo. Reciprocamente, todo ciclo do grafo tem um arco reverso. Por outro lado, arcos cruzados não pertencem a ciclos.   Pode-se dizer que o algoritmo de busca em profundidade resolve o seguinte

Problema da arborescência de busca em profundidade:  Dado um vértice r de um grafo, encontrar uma r-arborescência maximal do grafo que tenha as seguintes propriedades:  (1) todo ciclo tem pelo menos um arco reverso e (2) nenhum ciclo contém arco cruzado.

Exercícios 4

  1. [Importante]  Seja T uma r-arborescência de busca em profundidade de um grafo D.  Mostre que todo arco reverso pertence a um ciclo. Mostre que todo ciclo tem um arco reverso. Mostre que arcos de avanços e arcos cruzados não pertencem a ciclos.