Lesson23

Os grafos surgem em inúmeros problemas e aplicações, tendo dado origem à disciplina de teoria de grafos, que se dedica apenas ao estudo de problemas e propriedades de grafos. Porém, ainda que a teoria de grafos tenha uma longa história, com o problema das sete pontes de Königsberg levantado por Leonhard Euler na sua fundação, os grafos têm vindo a ganhar ainda mais notoriedade nos últimos anos com o estudo de redes complexas. São exemplo de redes complexas as redes sociais, as redes biológicas, as redes de transportes, as redes de distribuição, entre muitos outros exemplos, e são inúmeros os problemas inerentes a estas redes enquanto sistemas complexos (mais detalhes no material de apoio de ARC). Os algoritmos e as estruturas de dados têm nesta área particular relevância, não só porque os problemas com grafos são em geral computacionalmente difíceis, mas porque estes sistemas são em geral de muito grande dimensão, como é o caso de várias redes sociais bem conhecidas.

Definições

Um grafo $G$ é caracterizado por um conjunto de vértices $V$ e por um conjunto de arcos $E\subseteq V\times V$, i.e., $G=(V,E)$. Os arcos representam ligações entre pares de vértices, em que cada arco liga dois vértices e cada vértice pode estar ligado a vários outros vértices.

Dado $G=(V,E)$, $|V|$ e $|E|$ denotam respectivamente o número de vértices e o número de arcos de $G$. Quando $|E|<< |V|^2$, ou seja quando o número de arcos é muito menor que o número possível de arcos, $G$ diz-se esparso.

-- Gephi.org

O grau de um vértice (degree) é o número de ligações/vizinhos do mesmo. O grau médio de um grafo é a média dos graus de todos os vértices.

Os arcos podem ser orientados, caso em que o grafo se diz orientado. Os arcos podem também ter pesos associados, caso em que o grafo se diz pesado.

Um grafo diz-se orientado e acíclico se, para qualquer vértice $v$, não existem caminhos com início e fim em $v$.

Um grafo diz-se conexo se, para quaisquer vértices $u$ e $v$, existe pelo menos um caminho entre $u$ e $v$. Um grafo diz-se bi-connected se ao removermos um qualquer vértice $v$ o grafo continua conexo.

Exemplos de problemas em grafos:

1. Qual é a distribuição de grau de um grafo?
2. Qual é a distância média?
3. Qual é o caminho mais curto entre dois vértices?
4. Existe um caminho que passa uma e uma só vez em cada arco?
5. Existe um caminho que passa uma e uma só vez em cada vértice?
6. Que vértices/arcos devemos atacar para desligar um grafo?
7. Qual é a probabilidade de um vértice de ficar "infectado" dada uma rede de contactos num fenómeno epidémico?
8. Quais são as comunidades numa rede social?

Estes são apenas alguns exemplos. O estudo de redes complexas envolve outros tópicos como a influência entre contactos, a dinâmica entre pares, e teoria de jogos. De facto os grafos oferecem uma forma conveniente de representar relações e dependências entre processos, organismos, organizações, populações e ainda de todos os componentes destes. Desde grafos de circuitos, redes de transporte, diagramas de procedimentos e módulos num programa informático, etc., no momento em que temos o grafo que representa um determinado conceito, é "fácil" (pelos menos conceptualmente) encontrar caminhos mais curtos, fazer planeamento, etc. Podemos também ter o mesmo sistema representado por redes distintas, cada uma a uma escala diferente.

Nesta e nas próximas aulas vamos ver como representar grafos e alguns dos algoritmos básicos que permitem responder a muitos problemas com grafos.

Representação

Podemos representar um grafo com uma matriz de adjacências ou com listas de adjacências.

Consideremos o seguinte grafo não orientado:

Representação com uma matriz de adjacências que, no caso dos grafos não orientados, é sempre simétrica:

+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+

Representação com listas de adjacências:

+---+  +---+---+
|  -+->| 2 |  -+->
|   |  +---+---+
+---+  +---+---+  +---+---+
|  -+->| 2 |  -+->| 3 |  -+->
|   |  +---+---+  +---+---+
+---+  +---+---+  +---+---+  +---+---+  +---+---+
|  -+->| 0 |  -+->| 1 |  -+->| 3 |  -+->| 5 |  -+->
|   |  +---+---+  +---+---+  +---+---+  +---+---+
+---+  +---+---+  +---+---+  +---+---+
|  -+->| 1 |  -+->| 2 |  -+->| 4 |  -+->
|   |  +---+---+  +---+---+  +---+---+
+---+  +---+---+  +---+---+  +---+---+
|  -+->| 3 |  -+->| 5 |  -+->| 6 |  -+->
|   |  +---+---+  +---+---+  +---+---+
+---+  +---+---+  +---+---+
|  -+->| 2 |  -+->| 4 |  -+->
|   |  +---+---+  +---+---+
+---+  +---+---+
|  -+->| 4 |  -+->
|   |  +---+---+
+---+

Consideremos o seguinte grafo orientado:

Representação com uma matriz de adjacências:

+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 0 | 0 | 1 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+

Representação com listas de adjacências:

+---+
|  -+->
|   |
+---+  +---+---+
|  -+->| 3 |  -+->
|   |  +---+---+
+---+  +---+---+  +---+---+  +---+---+
|  -+->| 0 |  -+->| 1 |  -+->| 5 |  -+->
|   |  +---+---+  +---+---+  +---+---+
+---+  +---+---+
|  -+->| 2 |  -+->
|   |  +---+---+
+---+  +---+---+  +---+---+  +---+---+
|  -+->| 3 |  -+->| 5 |  -+->| 6 |  -+->
|   |  +---+---+  +---+---+  +---+---+
+---+
|  -+->
|   |
+---+
|  -+->
|   |
+---+

No caso dos grafos não orientados, o tamanho das listas de adjacência é $2 |E|$. No caso dos grafos orientados, o tamanho das listas de adjacência é $|E|$. O tamanho total em qualquer dos casos é portanto $O(V+E)$. A matriz de adjacências requer $O(V^2)$ espaço para qualquer grafo.

A representação com matrizes de adjacência é em geral mais adequada quando existe espaço disponível, os grafos são densos, e os algoritmos requerem mais de $O(V^2)$ operações. Neste caso a adição e remoção de arcos é feita de forma eficiente, é fácil evitar existência de arcos paralelos (repetidos), e é também fácil determinar se dois vértices estão ou não ligados. Existem no entanto alguns inconvenientes com esta representação tais como ser sempre necessário espaço em memória proporcional a $O(V^2)$, mesmo no caso dos grafos esparsos de grande dimensão em que o número de arcos é muito menor do que $V^2$. Neste caso, a simples inicialização do grafo (proporcional a $V^2$) pode dominar o tempo de execução global do algoritmo e, para o caso de grafos muito esparsos, mas com um número muito elevado de vértices, pode nem sequer existir memória suficiente para armazenar a matriz.

No caso das listas de adjacências a inicialização é proporcional a $V$ e utilizamos sempre espaço proporcional a $V+E$, sendo portanto uma representação adequada para grafos esparsos e para uso com algoritmos que assentem na análise de arcos em grafos esparsos. A adição de arcos é também feita de forma eficiente. No entanto, a detecção de arcos paralelos e adjacência entre vértices requer que se pesquise as listas de adjacências, o que pode levar um tempo proporcional a $V$, e a remoção de arcos pode também levar um tempo proporcional a $V$ (embora este problema pode ser contornado). As listas de adjacências não são portanto aconselháveis para grafos de grande dimensão que não podem ter arcos paralelos e quando a remoção de arcos ocorre com frequência.

Dependendo do problema, pode ser necessário utilizar representações mais eficientes, como representações eficientes para matrizes esparsas ou até estruturas de dados sucintas como as utilizadas na framework Webgraph, que permitem representar redes sociais de grande dimensão mesmo em computadores relativamente modestos.

ADT e implementação

Ficheiro graph.h:

typedef struct {
  int v;
  int w;
} Edge;

Edge EDGE(int, int);
typedef struct graph *Graph;
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge a[], Graph G);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

Ficheiro graph_mat.c (com matrizes):

#include <stdlib.h>
#include “graph.h”

struct graph {
   int V, E;
   int **adj;
};

Graph GRAPHinit(int V){
  Graph G = malloc(sizeof(struct graph));
  G->V = V;
  G->E = 0;
  G->adj = MATRIXint(V, V, 0);
  return G;
}

void GRAPHinsertE(Graph G, Edge e) {
  int v = e.v, w = e.w;
  if (G->adj[v][w] == 0)
    G->E++;
  G->adj[v][w] = 1;
  G->adj[w][v] = 1;
}

void GRAPHremoveE(Graph G, Edge e) {
  int v = e.v, w = e.w;
  if (G->adj[v][w] == 1)
    G->E--;
  G->adj[v][w] = 0;
  G->adj[w][v] = 0;
}

int GRAPHedges(Edge a[], Graph G){
  int v, w, E = 0;
  for (v = 0; v < G->V; v++)
    for (w = v+1; w < G->V; w++)
      if (G->adj[v][w] == 1)
        a[E++] = EDGE(v, w);
  return E;
}

Ficheiro graph_list.c (com listas):

#include <stdlib.h>
#include “graph.h”

typedef struct node *link;

struct node {
   int v;
   link next;
};

struct graph {
   int V;
   int E;
   link *adj;
};

link NEW(int v, link next) {
  link x = malloc(sizeof(struct node));
  x->v = v;
  x ->next = next;
  return x;
}

Graph GRAPHinit(int V) {
  int v;

  G = malloc(sizeof(struct graph));
  G->V = V;
  G->E = 0;
  G->adj = malloc(V * sizeof(link));
  for (v = 0; v < V; v++)
    G->adj[v] = NULL;

  return G;
}

void GRAPHinsertE(Graph G, Edge e) {
  int v = e.v, w = e.w;
  G->adj[v] = NEW(w, G->adj[v]);
  G->adj[w] = NEW(v, G->adj[w]);
  G->E++;
}

void GRAPHremoveE(Graph G, Edge e){
  /* Fica como exercício */
}

int GRAPHedges(Edge a[], Graph G) {
  int v, E = 0;
  link t;
  for (v = 0; v < G->V; v++)
    for (t = G->adj[v]; t != NULL; t = t->next)
      if (v < t->v )
        a[E++] = EDGE(v, t->v);
  return E;
}

Representação versus complexidade algorítmica

Podemos considerar três mecanismos básicos de representação de grafos: vector de arcos (pouco comum); matriz de adjacências; e listas de adjacências. É preciso ter em conta que estas estruturas de dados conduzem a diferentes desempenhos ao nível das operações de manipulação e a escolha da estrutura de dados a utilizar na representação deverá depender sempre do problema a resolver.

Complexidade típica para as operações de manipulação mais comuns: