Digrafos
Digrafos
Digrafos
Digrafos
Esta página define os conceitos de digrafo, passeio e caminho. Ela serve de preparação para as páginas que estudarão os problemas do
caminho mínimo, da arborescência maximal (= árvore geradora), da enumeração topológica, dos componentes fortes, etc.
[A palavra digrafo não consta dos dicionários, mas é cômoda e corresponde bem ao termo digraph em inglês, que já está bastante
arraigado. Alguns autores descuidados escrevem "dígrafo", com acento; isso não faz sentido algum e deve ser evitado e combatido.]
Veja os verbetes Directed graph, Graph theory e Glossary of graph theory na Wikipedia.
O que é um digrafo?
Um digrafo é qualquer matriz booleana com linhas e colunas indexadas por 1,2,…,n. (Um digrafo é, portanto, 1 0 0 0 0 1
uma estrutura mais rica que os vetores de que tratamos em outras páginas.) No exemplo ao lado, temos um 0 0 1 0 0 1
digrafo com linhas indexadas por 1,2,…,6 da esquerda para a direita e colunas indexadas por 1,2,…,6 de cima 0 1 1 1 0 1
para baixo. 1 0 0 0 1 0
0 0 0 1 0 1
Embora esta definição de digrafo seja correta e conveniente, o respeito à tradição exige que a definição seja
1 0 0 1 0 0
reformulada de maneira um pouco mais abstrata. É o que faremos a seguir.
Vértices e arcos
Um digrafo é 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. 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.
Alguns livros, como o CLRS, usam a palavra grafo no lugar do meu digrafo. Eu prefiro reservar a
palavra grafo para objetos em que os arcos não são orientados (os arcos são chamados arestas nesse
caso). Outros livros usam expressões como "grafo orientado" e "grafo dirigido" no lugar do meu
"digrafo".
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. O grau de saída de um vértice é o número de arcos que saem do
vértice. O grau de entrada é o número de arcos que entram no vértice.
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 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 (afinal, o cruzamento da linha u com a coluna v só pode conter 0 ou 1) e
no máximo um arco vu. Em outras palavras, nossos digrafos não têm arcos "paralelos". Por outro lado, podemos ter arcos da forma uu,
em que a ponta final coincide com a inicial (que correspondem ao cruzamento da linha u com a coluna u). Um arco desse tipo é conhecido
como laço.
Um digrafo com conjunto de vértices V (usualmente {1,2,…,n}) e conjunto de arcos A pode ser denotado simplesmente por
(V, A) .
Às vezes é conveniente dar um nome ao digrafo com um todo. Se o nome do digrafo é D, por exemplo, então os seus conjuntos de vértices
e arcos serão denotados por V(D) e A(D) respectivamente.
Exercícios
1. Mostre que a soma dos graus de entrada de todos os vértices é igual ao número de arcos do digrafo.
2. Mostre que a soma dos graus de saída de todos os vértices é igual ao número de arcos do digrafo.
Representação e estruturas de dados
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,
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: Matriz de adjacência e listas de adjacência do digrafo da figura acima. Você deve imaginar um "0" em cada
casa vazia da matriz.
1 2 3 4 5 6 u Adj[u]
1 1 1 (6)
2 1 1 2 (3, 6)
3 1 1 1 3 (2, 4, 6)
4 1 1 4 (1, 5)
5 1 1 5 (4, 6)
6 1 1 6 (1, 4)
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.)
Exercícios
1. Mostre que um digrafo com n vértices tem no máximo n² arcos. Qual o número mínimo de arcos de um digrafo?
2. Quanto espaço ocupa a representação de um digrafo por meio de uma matriz de adjacência? Quanto espaço ocupa a representação
de um digrafo por meio de listas de adjacência?
3. [IMPORTANTE] Considere o seguinte algoritmo que calcula o grau de saída, gs[u], de cada vértice u de um digrafo representado por
suas listas de adjacência. O algoritmo supõe que os vértices do digrafo são 1, 2, … , n.
GRAU-DE-SAÍDA (n, Adj)
para u ← 1 até n faça
gs[u] ← 0
para u ← 1 até n faça
para cada v em Adj[u] faça
gs[u] ← gs[u]+1
devolva gs[1..n]
Mostre que esse algoritmo consome Ο(n+nm) unidades de tempo, onde m é o número de arcos. Melhore essa estimativa, mostrando
que o algoritmo consome Ο(n+m) unidades de tempo.
4. Escreva um algoritmo que receba um digrafo descrito por suas listas de adjacência e calcule o grau de entrada de cada vértice.
Passeios e caminhos
Um passeio em um digrafo é uma sequência de vértices em que cada vértice é adjacente ao anterior. Mais exatamente, um passeio é uma
sequência
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. Note que um
passeio é um objeto orientado (ou dirigido): cada arco do passeio aponta "para a direita".
Um passeio sem vértices repetidos será chamado caminho. É fácil verificar que existe um caminho de um vértice r a um vértice s se e
somente se existe um passeio de r a s.
Exercícios
1. Dados vértices r e s de um digrafo, decidir se existe um passeio de r a s. Mostre que o
algoritmo guloso óbvio não resolve esse problema.
2. Seja P um passeio com origem r e término s. Mostre que alguma subsequência de P é um
caminho com origem r e término s.
3. [PAGERANK DO GOOGLE] Uma medida grosseira da "importância" de 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 f no
intervalo [0,1]. Agora, seja p 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:
p(v) = (1−f)/n + f ∑u p(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 p(v) é o pagerank do vértice v. É verdade que existe uma só função p que satisfaz essas equações (para cada f)? Escreva um
algoritmo que calcule p iterativamente.
http://www.ime.usp.br/~pf/analise_de_algoritmos/
Last modified: Mon Apr 13 07:08:12 BRT 2015
Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística da USP