Arborescências maximais de digrafos

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

Arborescências de digrafos

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

Uma r-arborescência T de um digrafo D é maximal  (ou geradora)  se o seu conjunto de vértice é igual ao território de r em D, 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 o território de r cobre todos os vértices do digrafo.]  [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 digrafo, encontrar uma r-arborescência maximal do digrafo.

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

  Arborescência-Maximal (n, Adj, r)
1o para  u crescendo de 1  até  n  faça
1oooo pai[u] ← nil
1o pai[r] ← r
1o LCria-Lista(r)
1o enquanto  L  não estiver vazia faça
1oooo uRetira-da-Lista(L)
1oooo para cada  v  em  Adj[u]  faça
1ooooooo se  pai[v] = nil
1oooooooooo então  pai[v] ← u
10  oooooooooo então  Insere-na-Lista(v, L)
11  o 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 digrafo 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 lista de vértices análoga à usada pelo algoritmo Território.  Se as rotinas Cria-Lista, Retira-da-Lista e Insere-na-Lista consumirem tempo constante (isto é, uma quantidade de tempo independente do tamanho do digrafo) 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 diretos, de retorno, e cruzados

Seja T uma r-arborescência maximal de um digrafo D.  Em relação a T, os arcos de D no território de r podem ser assim classificados:  um arco uv que não pertencem a T é

  1. direto (= 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 no território 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 digrafo 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 no território 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 digrafo 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)
1o para  u crescendo de 1  até  n  faça
1oooo pai[u] ← nil
1o pai[r] ← r
1o FCria-Fila(r)
1o enquanto  F  não estiver vazia faça
1oooo uSai-da-Fila(F)
1oooo para cada  v  em  Adj[u]  faça
1ooooooo se  pai[v] = nil
1oooooooooo então  pai[v] ← u
10  oooooooooo então  Entra-na-Fila(v, F)
11  o 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 direto 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 digrafo D e uma função f que atribui um número não negativo a cada arco do digrafo, 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 no território 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 digrafo dado. Inspire-se no algoritmo Dijkstra.

  2. Seja T uma r-arborescência de distâncias de um digrafo D.  Mostre que d(v) = d(u)+1 para todo arco direto 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 digrafo tem um peso numérico f(uv). O peso de uma arborescência do digrafo é 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 digrafo.

Problema da arborescência maximal de peso mínimo:  Dado um vértice r de um digrafo 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)
o para  u crescendo de 1  até  n  faça
oooo cor[u] ← branco
oooo pai[u] ← nil
o B-em-Prof (r, cor)
o devolva   pai[1..n]
  B-em-Prof (u, cor)
1o cor[u] ← cinza
1o para cada  v  em  Adj[u]  faça
1oooo se  cor[v] = branco
1ooooooo então  pai[v] ← u
1ooooooo então  B-em-Prof (v, cor)
1o 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 digrafo 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 digrafo, encontrar uma r-arborescência maximal do digrafo 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 digrafo D.  Mostre que todo arco reverso pertence a um ciclo. Mostre que todo ciclo tem um arco reverso. Mostre que arcos diretos e arcos cruzados não pertencem a ciclos.

Valid HTML 4.01 Strict Valid CSS!