Grafos

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 das páginas anteriores trataram de problemas sobre vetores. Esta página e as seguintes tratam de problemas sobre matrizes com valores 0 e 1. Essas matrizes são conhecidas como grafos.

Esta página define os conceitos de grafo, caminho, floresta radicada, e árvore raicada. Ela serve de base para as páginas que estudarão os problemas da permutação topológica, dos componentes fortes, do caminho mínimo, da árvore geradora mínima, etc.

O que é um grafo?

../gif/google_centrality.jpg

Um grafo (= graph) é 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 grafo é uma espécie de mapa rodoviário: os vértices são cidades e os arcos são estradas de mão única.

Os arcos de um grafo são pares ordenados: um arco (u, v) é diferente de um arco (v, u). Para enfatizar esse fato, poderíamos usar a expressão digrafo ou grafo dirigido no lugar de grafo.

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 grafo, existe no máximo um arco uv e no máximo um arco vu. Em outras palavras, nossos grafos não têm arcos paralelos. Nossos grafos também não têm laços (= loops), uma vez que as duas pontas de cada arco são distintas.

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 grafo 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 grafo com um todo. Se o nome de um grafo é G então os seus conjuntos de vértices e arcos serão denotados por  V(G)  e  A(G)  respectivamente. Um grafo H é subgrafo de um grafo G se V(H) ⊆ V(G) e A(H) ⊆ A(G). Se V(H) = V(G), dizemos que H é um subgrafo gerador (= spanning) de G.

Dado um conjunto X de vértices de um grafo G, considere o conjunto B de todos os arcos de G que têm ambas as pontas em X. Dizemos que o subgrafo (X, B) é induzido por X.

Se n é o número de vértices e m é o número de arcos de um grafo 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 grafo é esparso (= sparse). Se m estiver mais próximo do extremo superior, dizemos que o grafo é denso (= dense).

Exercícios 1

  1. ★ Mostre que a soma dos graus de entrada de todos os vértices é igual ao número de arcos do grafo. Mostre que a soma dos graus de saída de todos os vértices é igual ao número de arcos do grafo.
  2. Seja n o número de vértices e m o número de arcos de um grafo. Mostre que m < n²/2.
  3. É correto dizer que um grafo é denso se m = Ο(n²)?

Representação e estruturas de dados

Uma boa estrutura de dados para representar um grafo é 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 grafo é 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 grafo definido pela 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)

Desempenho de algoritmos para grafos

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

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

T(n, m)  ≤  c · (n + m lg n)

para todo grafo 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 2

  1. Quanto espaço ocupa a representação de um grafo por meio de uma matriz de adjacência?  Quanto espaço ocupa a representação de um grafo por meio de listas de adjacência?
  2. ★ Considere o seguinte algoritmo que calcula o grau de saída, gs[u], de cada vértice u de um grafo G representado por seu vetor Adj de listas de adjacência.
    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 + nm) unidades de tempo, onde m é o número de arcos. Melhore essa estimativa, mostrando que o algoritmo consome apenas Ο(n + m) unidades de tempo.

  3. Escreva um algoritmo que receba um grafo descrito por suas listas de adjacência e calcule o grau de entrada de cada vértice.

Passeios e caminhos

Um passeio (= walk) em um grafo é 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 passeio sem arcos repetidos será chamado caminho (= path). É 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. Um caminho é simples se não tem vértices repetidos.

Dizemos que um vértice x está ao alcance (= reachable) de um vértice r se existe um caminho de rx. Diz-se também que x é acessível a partir de r,

../gif/google_centrality.jpg

Exemplo B: No grafo 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.

Exercícios 4

  1. ★ Seja P um passeio com origem r e término s. Mostre que alguma subsequência de P é um caminho simples com origem r e término s.
  2. ★ Mostre que existe um passeio de rs se e somente se existe um caminho simples de rs.
  3. Dados vértices r e s de um grafo, decidir se existe um passeio de rs. Mostre que o algoritmo guloso óbvio não resolve esse problema.
  4. Pagerank do Google.  Uma medida grosseira da importância de um vértice num grafo é 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 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−λ)/n + λ ∑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 λ)?  Escreva um algoritmo que calcule p iterativamente.

Florestas radicadas

Uma floresta radicada (= rooted forest) é um grafo 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.

figs/mine/forest-b.png

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.

Exercícios 5

  1. ★ Suponha que v é um vértice de uma floresta radicada. Mostre que existe um único caminho que vai de uma raiz até v. Mostre que esse caminho é simples.
  2. Mostre que toda floresta radicada com n vértices e k raízes tem exatamente n − k arcos.
  3. Mostre que toda floresta radicada admite uma permutação (v1, v2, … , vk) dos vértices tal que todo arco da floresta tem a forma vivj com i < j.