| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
Muitas problemas computacionais básicos são formulados sobre vetores. Muitos outros são formulados sobre matrizes; mais especificamente, matrizes quadradas booleanas. Essas matrizes são conhecidas como digrafos ou grafos dirigidos.
Esta página define os conceitos de digrafo, caminho, floresta radicada, e árvore radicada. Os conceitos são usados, em outras páginas, para discutir os problemas da permutação topológica, das componentes fortes, do caminho mínimo, da árvore geradora mínima, da cobertura por vértices, etc.
Sumário:
Um digrafo (= digraph) é um objeto formado por dois conjuntos: um conjunto de vértices e um conjunto de arcos. Cada arco é um par ordenado de vértices; o primeiro vértice do par é a ponta inicial do arco e o segundo é a ponta final do arco. Os arcos de um digrafo são pares ordenados: um arco (u, v) é diferente de um arco (v, u).
(A palavra digrafo
não consta dos dicionários,
mas é cômoda e corresponde bem ao termo digraph em inglês,
que já está bem estabelecido.
Alguns autores descuidados
escrevem dígrafo
,
com acento;
isso não faz sentido algum e deve ser evitado
e combatido.)
Você pode imaginar que um digrafo é uma espécie de mapa rodoviário: os vértices são cidades e os arcos são estradas de mão única.
Um arco com ponta inicial u e ponta final v é denotado por (u, v) ou por uv. Dizemos que um arco uv vai de u a v. Dizemos que um arco xy sai de um vértice u se x = u . Analogamente, um arco xy entra em um vértice u se y = u.
Dizemos que um vértice v é adjacente a um vértice u se o par (u, v) é um arco, ou seja, se existe um arco que sai de u e entra em v. Nessas mesmas circunstâncias, dizemos também que v é um vizinho (= neighbor) de u. A relação de adjacência não é simétrica: v pode ser adjacente a u sem que u seja adjacente a v.
Dados vértices u e v de um digrafo,
existe no máximo um arco uv
e no máximo um arco vu.
Em outras palavras,
nossos digrafos não têm arcos paralelos
.
Nossos digrafos também não têm laços
(= loops),
uma vez que as duas pontas de cada arco são distintas.
O grau de saída (= outdegree) de um vértice é o número de arcos que saem do vértice. O grau de entrada (= indegree) é o número de arcos que entram no vértice.
Um digrafo com conjunto V de vértices e conjunto A de arcos pode ser denotado simplesmente por (V, A) . Às vezes é conveniente dar um nome ao digrafo com um todo. Se o nome de um digrafo é G então seus conjuntos de vértices e arcos serão denotados por V(G) e A(G) respectivamente.
Se n é o número de vértices e m é o número de arcos de um digrafo então 0 ≤ m ≤ ½ (n² − n) . Esse intervalo de possíveis valores de m é bastante extenso. Se m estiver mais próximo do extremo inferior do intervalo, dizemos que o digrafo é esparso (= sparse). Se m estiver mais próximo do extremo superior, dizemos que o digrafo é denso (= dense).
Um digrafo H é subdigrafo de um digrafo G se V(H) ⊆ V(G) e A(H) ⊆ A(G). Se V(H) = V(G), dizemos que H é um subdigrafo gerador (= spanning) de G.
Dado um subconjunto X de V(G), o subdigrafo induzido por X é o digrafo (X, B) em que B é o conjunto de todos os arcos de G que têm ambas as pontas em X. Um subdigrafo induzido de G é um subdigrafo induzido por algum subconjunto de V(G).
Uma boa estrutura de dados para representar um digrafo é a matriz de adjacência. Trata-se de uma matriz booleana quadrada, digamos M, cujas linhas e colunas são indexadas pelos vértices. Para cada par (u, v) de vértices,
M[u, v] = 1
se uv é um arco e
M[u, v] = 0
em caso contrário.
Outra estrutura de dados usada para representar os arcos de um digrafo é um conjunto de listas de adjacência: para cada vértice u, temos uma lista
Adj[u]
de todos os vértices v adjacentes a u. É claro que o número de elementos da lista Adj[u] é igual ao grau de saída de u.
Exemplo A:
Matriz de adjacência e listas de adjacência
do digrafo definido pela figura acima.
Você deve imaginar um 0
em cada casa vazia da matriz.
|
|
Suponha que toda instância de um certo problema consiste em um digrafo e nada mais. Qual o tamanho de uma instância? Em outras palavras, qual o tamanho de um digrafo em termos do número n de vértices e do número m arcos?
Se o digrafo for representado por sua matriz de adjacência, é razoável dizer que o tamanho de cada instância é n² (qualquer que seja o valor de m). Se o digrafo for representado por suas listas de adjacência, é mais razoável dizer que o tamanho de cada instância é n + m. É melhor ainda dizer que o tamanho é o par (n, m).
Suponha agora que os digrafos são representados por suas listas de adjacência e que um certo algoritmo para o problema consome T*(n, m) unidades de tempo no pior caso. Que sentido faz dizer que T* está em Ο(n + m lg n), por exemplo? Como m é limitado por n², é preciso interpretar a notação assintótica com um pouco de cuidado. Dizer que T* está em Ο(n + m lg n) significa que existem números c e n0 (que não dependem de n nem de m) tais que
T*(n, m) ≤ c · (n + m lg n)
para todo digrafo com n ≥ n0 vértices e com qualquer número m de arcos. (A propósito, podemos tomar n0 = 1, uma vez que n + m lg n > 0 para todo n ≥ 1.)
| Grau-de-Saída (G) |
| . para cada u em V(G) |
| .ooo gs[u] := 0 |
| . para cada u em V(G) |
| .ooo para cada v em Adj[u] |
| .oooooo gs[u] := gs[u]+1 |
| . devolva gs |
Mostre que esse algoritmo consome Ο(n + n m) unidades de tempo, onde m é o número de arcos. Melhore essa estimativa, mostrando que o algoritmo consome apenas Ο(n + m) unidades de tempo.
Um passeio (= walk) em um digrafo é uma sequência de vértices em que cada vértice é adjacente ao anterior. Mais exatamente, um passeio é uma sequência
(v0, v1, … , vk-1, vk)
de vértices tal que, para todo i, o par vi-1vi é um arco. O vértice v0 é a origem do passeio e vk é o término do passeio. Dizemos também que o passeio vai de v0 a vk.
Cada arco da forma vi-1vi
é um arco do passeio.
Note que um passeio é um objeto orientado
(ou dirigido
):
cada arco do passeio aponta para a direita
.
Um caminho (= path) é um passeio sem arcos repetidos. O comprimento de um caminho é o número de arcos do caminho. Um caminho é simples se não tem vértices repetidos.
Dizemos que um vértice x está ao alcance de (= reachable from) um vértice r se existe um caminho de r a x. Diz-se também que x é acessível a partir de r,
Exemplo B:
No digrafo da figura,
(2, 6, 4, 5, 6, 4, 1) é um passeio,
(2, 6, 1, 6, 4, 1) é um caminho e
(2, 6, 4, 1) é um caminho simples.
O caminho (6, 4, 1, 6) não é simples.
O caminho trivial
(6) é simples.
importânciade um vértice num digrafo é o grau de entrada do vértice. Uma medida mais refinada é o pagerank do vértice, definido a seguir. Em primeiro lugar, é preciso escolher um número racional λ no intervalo [0,1]. Agora, seja pr uma função que leva o conjunto dos vértices nos racionais não-negativos de modo a satisfazer a seguinte equação para cada vértice v:
pr(v) = (1−λ)/n + λ ∑u pr(u)/gs(u) ,
onde a soma se estende a todos os vértices u tais que uv é um arco, gs(u) é o grau de saída de u e n é o número de vértices. Dizemos que pr(v) é o pagerank do vértice v. É verdade que existe uma só função pr que satisfaz essas equações (para cada λ)? Escreva um algoritmo que calcule pr iterativamente.
Uma floresta radicada (= rooted forest) é qualquer digrafo dotado das seguintes propriedades:
Florestas radicadas também são conhecidas como florestas-com-raizes e como florestas enraizadas. Uma raiz (= root) de uma floresta radicada é qualquer vértice de grau de entrada 0. É fácil verificar que para todo vértice v de uma floresta radicada existe um único caminho que vai de uma raiz até v.
Em uma floresta radicada, um vértice v é pai (= parent) de um vértice w se vw é um arco (o único arco que tem ponta final w). Um vértice w é filho (= child) de v se v é pai de w. Um vértice x é ancestral (= ancestor) de um vértice y se o único caminho que vai de uma raiz até y passa por x. Um vértice y é um descendente (= descendant) de x se x é ancestral de y.
Uma árvore radicada (= rooted tree) é uma floresta radicada que tem uma só raiz.
Exemplo C: A figura mostra uma floresta radicada com vértices 0, 1, … , 11. Os vértices 0 e 2 são as raízes da floresta. O vértice 4 é ancestral do vértice 0. O vértice 3 é descendente do vértices 0, 5 e 4. O vértice 0 não é ancestral nem descendente do vértice 1. O vértice 4 não é ancestral nem descendente do vértice 6.