O que é um grafo?

AED
Algoritmos e Estruturas de Dados
LEEC - 2005/2006
Teoria de Grafos e
Algoritmos em Grafos
Grafos - O que é um grafo?
• Objecto abstracto
• Dois tipos de entidades
– Nós ou Vértices
– Ramos ou Arestas
• Vértices representam
– cidades, pessoas, máquinas,
números, etc
• Arestas representam
– existência de ligações entre
nós, valor da ligação entre
nós, distância entre nós, etc
AED (IST/DEEC)
2
Grafos - Motivação
• Emparelhamento
• Mapas
– caminhos mais curtos; caminhos mais baratos.
• Circuitos Eléctricos
– existência de curto-circuitos; existência de cruzamento entre ligações.
• Sequenciamento
– tarefas a executar por um
conjunto de recursos sujeitas a restrições de carácter
tecnológico.
– processamento de imagem
estéreo; atribuição de pessoas a lugares.
• Redes de dados
– computadores ligados entre
si, enviando e recebendo
mensagens; existência de ligação entre quaisquer nós;
redundância.
• Estrutura de Programas
– grafos gerados por compiladores representando a estrutura de chamadas;
AED (IST/DEEC)
3
Grafos – Definições (1)
• Def: Um grafo é um conjunto de vértices e um conjunto
de arestas que ligam pares de vértices distintos (com
nunca mais que uma aresta a ligar qualquer par de
vértices).
• Def: Dois vértices ligados por uma aresta dizem-se
adjacentes.
• Def: Uma aresta que ligue dois vértices diz-se incidente
de cada um dos vértices.
AED (IST/DEEC)
4
Grafos – Definições (2)
• Def: O número de arestas incidentes num vértice diz-se o
grau desse vértice.
• Def: O subconjunto de arestas e vértices a elas associados
diz-se um sub-grafo do grafo original.
• Def: Uma sequência de vértices na qual os vértices
sucessivos estão ligados por arestas do grafo diz-se um
caminho.
AED (IST/DEEC)
5
Grafos – Definições (3)
• Def: Num caminho simples os vértices e arestas são
distintos.
• Def: Um caminho em que todos os vértices e arestas são
distintos, excepto para o primeiro e último que são iguais,
diz-se um ciclo.
• Def: Dois caminhos simples dizem-se disjuntos se não
possuírem vértices comuns, excepto possivelmente para os
vértices extremos.
AED (IST/DEEC)
6
Grafos – Definições (4)
• Def: Um grafo diz-se ligado se existir um caminho de cada
vértice para todos os outros vértices do grafo.
• Def: Um grafo que não seja ligado é constituído por
componentes ligadas, que se dizem sub-grafos ligados
máximos.
• Def: Um grafo ligado acíclico, i.e. sem ciclos, diz-se uma
árvore.
AED (IST/DEEC)
7
Grafos – Definições (5)
• Def: Um conjunto de árvores diz-se uma floresta.
• Def: A árvore de suporte de um grafo ligado é um
sub-grafo que contém todos os vértices e é uma árvore.
• A floresta de suporte de um grafo é um sub-grafo que
contém todos os seus vértices e é uma floresta.
AED (IST/DEEC)
8
Grafos – Propriedades em árvores
• Um grafo G de V vértices é uma árvore se e só se satisfizer
qualquer das seguintes condições:
– G tem V-1 arestas e nenhum ciclo.
– G tem V-1 arestas e é ligado.
– Existe apenas um caminho simples a unir quaisquer dois vértices.
– G é ligado mas retirando uma só aresta faz com que deixe de o ser.
AED (IST/DEEC)
9
Grafos – Exemplos (1)
G
1
2
4
6
3
5
8
7
• Os vértices 6 e 7 são adjacentes.
• Os vértices 4 e 6 não são adjacentes.
• O vértice 7 tem grau quatro.
AED (IST/DEEC)
10
Grafos – Exemplos (2)
G’
1
2
4
3
5
6
•
•
•
•
8
7
G’ é um sub-grafo de G, gerado a partir das arestas a cheio.
O vértice 5 não pertence a G’.
G é um grafo ligado; G’ não é.
O sub-grafo G’ é constituído por um grafo completo com três
vértices e por uma árvore com quatro vértices
AED (IST/DEEC)
11
Grafos – Exemplos (3)
G
1
2
4
6
3
5
8
7
• Caminho: 1-2-4-5-7-8
AED (IST/DEEC)
12
Grafos – Exemplos (4)
G
1
2
4
3
5
6
8
7
• Ciclo: 3-4-5-6-7-8-3
AED (IST/DEEC)
13
Grafos – Exemplos (5)
G’’
1
2
4
6
3
5
8
7
• G’’: árvore de suporte de G.
AED (IST/DEEC)
14
Grafos – Síntese da Aula 1
• Introdução
– Definição de grafo
– Motivação aplicacional
• Definições e notação
• Propriedades elementares em grafos
• Exemplos
AED (IST/DEEC)
15
Grafos - Definições e Propriedades (1)
• Def: Um grafo diz-se completo quando existe uma aresta
ligando qualquer par de vértices.
• Prop: Um grafo com V vértices possui, no máximo,
V(V-1)/2 arestas.
• Def: Um grafo G’ diz-se complemento do grafo G quando
se obtém a partir de um grafo completo com o mesmo
número de vértices de G, retirando-lhe todas as arestas de G.
AED (IST/DEEC)
16
Grafos - Definições e Propriedades (2)
• Def: Um grafo que possua um número de arestas próximo
do número máximo diz-se denso.
• Def: Um grafo cujo complemento seja denso diz-se
esparso.
• Def: Densidade de um grafo: 2E/V, em que E é o número
de arestas e V o de vértices.
• Def: A um sub-grafo completo dá-se o nome de clique.
AED (IST/DEEC)
17
Grafos - Definições e Propriedades (3)
• Def: Um grafo que possua a propriedade de ser possível
dividir os vértices em dois conjuntos tais que todas as
arestas apenas ligam vértices de um conjunto a vértices do
outro conjunto diz-se bipartido.
• Def: Quando existe um sentido atribuído às arestas, os
grafos dizem-se direccionados, dirigidos ou digrafos.
• Def: O primeiro vértice de uma aresta direccionada diz-se
fonte e o segundo diz-se destino.
AED (IST/DEEC)
18
Grafos - Definições e Propriedades (4)
• Prop: Apenas os vértices destino são adjacentes dos vértices fonte.
• Def: Um ciclo direccionado num digrafo é um ciclo em
que todos os pares de vértices adjacentes surgem pela
ordem especificada pelas arestas.
• Def: Um digrafo sem ciclos direccionados diz-se grafo
direccionado acíclico, ou DAG (Directed Acyclic Graph).
AED (IST/DEEC)
19
Grafos - Definições e Propriedades (5)
• Def: Quando se atribuem pesos às arestas, representando
custo, distância, etc., diz-se que o grafo é ponderado.
– Também é possível atribuir pesos aos próprios vértices, ou a pares
vértice/aresta.
• Def: Grafos ponderados direccionados, dizem-se redes.
AED (IST/DEEC)
20
Grafos - Interface ADT para Grafos (1)
• Os algoritmos para processamento de grafos serão
desenvolvidos no contexto de uma ADT que define as tarefas
de interesse.
• A nossa primeira interface elementar é tal que:
– O número de vértices e arestas são especificados por inteiros;
– Uma aresta é definida por um par de inteiros, designando os
vértices que une;
– O número de vértices é limitado superiormente.
• Esta interface irá sendo alargada à medida das necessidades.
AED (IST/DEEC)
21
Grafos - Interface ADT para Grafos (2)
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);
AED (IST/DEEC)
Graphinit cria grafo com
o número final de vértices,
sem arestas.
GraphinsertE insere uma
aresta, caso não exista.
GraphremoveE retira uma
aresta, caso exista.
Graphedges conta o número de arestas.
Graphcopy cria uma segunda cópia do grafo.
Graphdestroy faz o inverso de Graphinit.
22
Grafos - Matriz de Adjacências (1)
• Matriz de Adjacências
– Matriz (V×V) de valores booleanos;
– A entrada correspondente à linha v e coluna w é 1
se existir uma aresta ligando estes dois vértices;
– A mesma entrada vale 0 caso contrário;
– A matriz é simétrica, excepto para digrafos, em
que poderá não sê-lo.
AED (IST/DEEC)
23
Grafos - Matriz de Adjacências (2)
• Matriz
• Grafo
G
1
2
4
6
3
5
8
7
1
2
3
4
5
6
7
8
1
1
1
0
1
0
0
0
0
2
1
1
0
1
0
0
0
0
3
0
0
1
1
0
0
1
1
4
1
1
1
1
1
0
0
0
5
0
0
0
1
1
1
1
0
6
0
0
0
0
1
1
1
0
7
0
0
1
0
1
1
1
1
8
0
0
1
0
0
0
1
1
Matriz V ×V simétrica
AED (IST/DEEC)
24
Grafos - Implementação de ADT (1)
#include <stdlib.h>
#include “GRAPH.h”
struct graph {int V; int 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;
}
AED (IST/DEEC)
25
Grafos - Implementação de ADT (2)
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;
}
AED (IST/DEEC)
26
Grafos – Síntese da Aula 2
• Definições e propriedades
– Grafos completos, complemento de um grafo, densidade, cliques,
grafos bipartidos, grafos direccionados, ciclos em grafos
direccionados, grafos ponderados, redes.
• Estrutura abstracta de dados para grafos
– Interface elementar
• Matrizes de adjacência
– Representação de um grafo
– Implementação da estrutura abstracta de dados
AED (IST/DEEC)
27
Grafos - Listas de Adjacências (1)
• Listas de Adjacências
– Cada vértice possui uma lista ligada;
– Os elementos constituintes da lista de um vértice são
os seus vértices adjacentes;
– Em grafos simples, se os vértices v e w são
adjacentes, então w pertence à lista de v e v pertence à
lista de w.
AED (IST/DEEC)
28
Grafos - Listas de Adjacências (2)
• Grafo
• Listas de Adjacências
G
1
2
4
6
3
5
8
7
1
2
3
4
5
6
7
8
4
1
4
3
4
5
5
3
2
4
8
1
6
7
3
7
7
2
7
5
6
8
Tabela com V listas de
arestas
AED (IST/DEEC)
29
Grafos - Implementação de ADT (1)
#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;
}
AED (IST/DEEC)
30
Grafos - Implementação de ADT (2)
Graph GRAPHinit(int V)}
int v; Graph 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++;}
AED (IST/DEEC)
31
Grafos - Implementação de ADT (3)
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;
}
AED (IST/DEEC)
32
Grafos - Vantagens das M. de Adj.
• Representação de eleição quando
– há espaço disponível;
– os grafos são densos;
– os algoritmos requerem mais que V2 operações.
• Adição e remoção de arestas é feita de forma eficiente;
• É fácil evitar a existência de arestas paralelas;
• É fácil determinar se dois vértices estão ou não ligados.
AED (IST/DEEC)
33
Grafos - Inconvenientes das M. de Adj.
• Grafos esparsos de grande dimensão requerem espaço de
memória proporcional a V2;
• Neste casos, a simples inicialização do grafo
(proporcional a V2) pode ser do-minante na execução
global do algoritmo;
• Pode nem sequer
armazenar a matriz.
AED (IST/DEEC)
existir
memória suficiente para
34
Grafos - Vantagens das L. de Adj.
• Inicialização é proporcional a V.
• Utiliza sempre espaço proporcional a V+E
– adequado para grafos esparsos.
– algoritmos que assentem na análise de arestas em grafos esparsos.
• Adição de arestas é feita de forma eficiente.
AED (IST/DEEC)
35
Grafos - Inconvenientes das L. de Adj.
• Arestas paralelas e adjacência entre vértices
– requer que se pesquise as listas de adjacências, o que pode levar
um tempo proporcional a V.
• Remoção de arestas
– pode levar um tempo proporcional a V (este problema pode ser
contornado).
• Não aconselhável para
– grafos de grande dimensão que não podem ter arestas paralelas;
– grande utilização de remoção de arestas.
AED (IST/DEEC)
36
Grafos - Variantes e Extensões (1)
• Outros tipos de grafos
– Digrafos
• ambas facilmente extensíveis;
• arestas representadas só uma vez;
– Grafos ponderados e redes
• M. de Adj. preenchida com pesos;
• L. De Adj. com campos extra para representação dos
pesos.
AED (IST/DEEC)
37
Grafos - Variantes e Extensões (2)
• Alteração da estrutura de dados
– Tipo “EDGE” contendo informação adicional, para
além dos vértices que liga.
– Vectores indexados pelos vértices
• Manutenção da informação do grau do vértice.
– Vector de arestas
• Forma alternativa de representação de grafos.
AED (IST/DEEC)
38
Grafos - Representações alternativas
• Três mecanismos básicos de representação de grafos
– Vector de arestas;
– Matriz de adjacências;
– Listas de adjacências.
• Produzem diferentes desempenhos ao nível das operações de manipulação.
• Escolha deverá depender do problema a resolver.
AED (IST/DEEC)
39
Grafos – Desempenho Relativo
Espaço
V. de Arestas M. de Adj. L. de Adj.
V2
V+E
E
Inicialização
1
V2
V
Cópia
E
V2
E
Destruição
1
V
E
Inserir aresta
1
1
1
Encontrar aresta
E
1
V
Remover aresta
E
1
V
Vértice isolado?
E
V
1
Caminho de u a v?
Elg*V
V2
E
AED (IST/DEEC)
40
Grafos - Encontrar e remover arestas (1)
• Eficientes em representações por matriz de adjacências.
• Como torná-las eficientes para as outras representações?
• Atribuir um símbolo inteiro a cada aresta
– Aresta v-w fica com o símbolo v*V+w.
• Por exemplo, fazer uso de tabelas de dispersão (“hashtables”)
• Quando uma aresta é inserida, é fácil testar se o símbolo
já foi usado.
AED (IST/DEEC)
41
Grafos - Encontrar e remover arestas (2)
• Remoção em digrafos
– ponteiro na tabela de dispersão para a sua representação
na lista de adjacências;
– requer listas duplamente ligadas.
• Remoção em grafos simples
– colocação de ambos os ponteiros na tabela de dispersão;
– ou ponteiro entre os vértices.
AED (IST/DEEC)
42
Grafos – Síntese da Aula 3
• Listas de adjacência
– Representação de um grafo
– Implementação da estrutura abstracta de dados
• Comparação das representações alternativas
– Vantagens e inconvenientes das matrizes de adjacência
– Vantagens e inconvenientes das listas de adjacência
• Variantes e extensões
– Grafos direccionados, ponderados e redes
– Outras representações
• Comparação das representações alternativas
– Memória e tempo de execução
AED (IST/DEEC)
43