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?

1 0 0 0 0 1
0 0 1 0 0 1
0 1 1 1 0 1
1 0 0 0 1 0
0 0 0 1 0 1
1 0 0 1 0 0

Um digrafo é qualquer matriz booleana com linhas e colunas indexadas por 1,2,…,n(Um digrafo é, portanto, uma estrutura mais rica que os vetores de que tratamos em outras páginas.)  No exemplo ao lado, temos um digrafo com linhas indexadas por 1,2,…,6 da esquerda para a direita e colunas indexadas por 1,2,…,6 de cima para baixo.

Embora esta definição de digrafo seja correta e conveniente, o respeito à tradição exige que a definição seja reformulada de maneira um pouco mais abstrata.  É o que faremos a seguir.

Vértices e arcos

Copiado de http://webmathematics.net/

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,

M[u,v] = 1   se existe arco de u para v  e
M[u,v] = 0   em caso contrário.

(Como já dissemos, esta matriz se confunde com o digrafo.)

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
1           1
2     1     1
3   1   1   1
4 1       1  
5       1   1
6 1     1    
 
u   Adj[u]
1 (6)
2 (3, 6)
3 (2, 4, 6)
4 (1, 5)
5 (4, 6)
6 (1, 4)

Consumo de tempo de algoritmos para digrafos

Suponha que toda instância de um certo problema consiste em um digrafo e nada mais.  Digamos n é o número de vértices e m o número de arcos do digrafo. Qual o tamanho de uma instância?

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(nm) 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 cn0 (que não dependem de n nem de m) tais que

T(nm)  ≤  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)
    o para u ← 1 até n faça
    oooo gs[u] ← 0
    o para u ← 1 até n faça
    oooo para cada v em Adj[u] faça
    ooooooo gs[u] ← gs[u]+1
    o 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

(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.  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 rs.

Copiado de http://webmathematics.net/

Exemplo: No digrafo da figura, (2,6,1,6,4,5,6) é um passeio e (2,3,6,4,1) é um caminho.

Exercícios

  1. Dados vértices r e s de um digrafo, decidir se existe um passeio de rs. 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 + fu 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.

Valid HTML 4.01 Strict Valid CSS!