Upload
lavinia-cortes-schmidt
View
223
Download
0
Embed Size (px)
Citation preview
GRAFOS
Motivação
• Muitas aplicações em computação necessitam considerar conjunto de conexões entre pares de objetos:– Existe um caminho para ir de um objeto a outro seguindo
as conexões?– Qual é a menor distância entre um objeto e outro?– Quantos outros objetos podem ser alcançados a partir de
um determinado objeto?• Grafos são utilizados para modelar tais problemas• São possivelmente as estruturas matemáticas mais
utilizadas na ciência
Algumas Aplicações
• Alguns exemplos de problemas práticos que podem ser resolvidos através de uma modelagem em grafos:– Ajudar máquinas de busca a localizar informação
relevante na Web.– Descobrir qual é o roteiro mais curto para visitar as
principais cidades de uma região turística.– Dentre diversas outras
Conceito Básicos – Definição
• Grafos consistem de dois conjuntos V e E e uma função G, tal que– V(G) é um conjunto finito e não vazio de vértices. Os
vértices são objetos simples que podem ter uma chave e outros atributos;
– A(G) é um conjunto disjunto de arcos ou arestas G é um conjunto de funções que associam pares de
vértices de V(G) – Definição Matemática: G = (V(G), E(G), G)
Exemplo:
• G=(V(G), E(G), G), onde– V(G) ={1, 2, 3, 4, 5}– E(G)={e1, e2, e3, e4, e5, e6, e7 , e8} G :
G(e1)= (1, 2), G(e2)= (1, 4), G(e3)= (2, 3), G(e4)= (2, 5), G(e5)= (3, 4), G(e6)= (1, 1),
5
1
2
3
4
EXEMPLOS DE GRAFOS
A
CB
1:
A2:
CB
A3:
A
B
4:
A5:
CB
A6:
C
B
Conceitos Básicos
• Quantos arcos teria um grafo com N vértices?• Ex.:
CB
A D
B
A
B
A C1: 2: 3:
R.: 1 arco R.: 3 arcos R.: 6 arcos
O número de arcos é dado pela fórmula
N-1 : Todos os vértices, excluindo ele mesmo/2 : Duas arestas iguais, de ida e volta
N (N-1)2
Conceitos Básicos – Tipos de Grafos• Grafo Não Direcional:
– São grafos onde as arestas E(G) não são ordenadas (direcionadas), ou seja, a ARESTA (V1, V2) é a mesma ARESTA (V2, V1)
• Grafo Direcional (Dígrafo):– São grafos onde as arestas E(G) são ordenadas
(direcionadas), ou seja, a ARESTA (V1, V2) é diferente da ARESTA (V2, V1)
• Exs.:
CB
A1:
CBA2:
D E 2
13:
3
Conceitos Básicos – Grau de um Vértice• Grau de um Vértice
– Número de arcos que incidem sobre um vértice• Em grafos não direcionados, é o número de
arcos que incidem sobre o vértice• Em grafos direcionados, é o número de arestas
que saem dele mais o número de arestas que incidem nele
• Um vértice é dito isolado quando seu grau é zero.• Ex.:
Grau(A) = 0 Grau(C) = 1Grau(B) = 2 Grau(D) = 1
CB
A D
CB
A D
F
E
Grau(A) = 3 Grau(D) = 3Grau(B) = 4 Grau(E) = 1Grau(C) = 4 Grau(F) = 1
Conceitos Básicos – Caminho e Comprimento
• Um caminho de um vértice x a um vértice y em um grafo G = (V;E) é uma seqüência de vértices (v0, v1, v2, ..., vn) tal que x = v0 e y = vn, e (vi-1; vi) ( E, para i = 1, 2, ..., n.
• O comprimento de um caminho é o número de arestas percorridos no caminho.
• Se existir um caminho c de x a y então y é alcançável a partir de x via c.
• Um caminho é simples se todos os vértices do caminho são distintos.
Conceitos Básicos – Caminho e Comprimento
CB
A D
1. Caminho: (C B D)2. Comprimento: 23. D é alcançável a partir de C4. A não é alcançável a partir
de nenhum vértice5. O caminho mostrado é simples
CB
A D
F
E
1. Caminho: (A D C B)2. Comprimento: 33. B é alcançável a partir de A,
mas E não.5. O caminho mostrado é simples6. Já o caminho (A B A B) não é
Conceitos Básicos – Ciclos
• Em um grafo não direcionado:– Um caminho (v0, v1, ..., vn) forma um ciclo se v0 = vn e o
caminho contém pelo menos três arestas.• Em um grafo direcionado:
– Um caminho (v0, v1, ..., vn) forma um ciclo se v0 = vn e o caminho contém pelo menos uma aresta.
• O ciclo é simples também se os vértices v1, v2, ..., vn são distintos.
• Grafos sem ciclos são chamados acíclicos, e cíclicos, caso contrário
• O self-loop é um ciclo de tamanho 1.• Dois caminhos (v0, v1, ..., vn) e (v0’, v1’, ..., vn’) formam
o mesmo ciclo se existir um inteiro j tal que vi’= v(i+j) mod n para i = 0, 1, ..., n - 1
Conceitos Básicos – Ciclos
1. Ciclo: (B C D)2. Os caminhos (B C D),(C D B) e (D B C) formam o mesmo ciclo
CB
A D
F
E
1. Ciclo: (A D C B A)2. Self-loop: (C C)3. Os caminhos (A D B A), (D B A D) e (B A D B) formam o mesmo ciclo
CB
A D
Conceitos Básicos - Árvores
• Um grafo acíclico conectado uma árvore pode se tornar uma árvore genérica
73
6 1 5
2
84 973
6
1
5
2 8
4
9
1010
Conceitos Básicos – Grafos Planares
• São grafos em que as arestas não se interceptam entre si, ou seja, as arestas interceptam apenas os seus vértices
73
6
1
5
2 8
4
9
73
6 1 5
2
84 9
Grafo Não Planar: Representação Planar do Grafo:
Conceitos Básicos – Componentes Conectados
• Um grafo não direcionado é conectado se cada par de vértices está conectado por um caminho.
• Os componentes conectados são as porções conectadas de um grafo.
• Um grafo não direcionado é conectado se ele tem exatamente um componente conectado.
CB
A D 1. O grafo não é conectado, pois não é possível alcançar A a partir dos vértices B, C ou D2. O grafo {C D B} é umcomponente conectado do grafo• Inserindo-se o arco (A B), oGrafo passa a ser conectado
Conceitos Básicos – Componentes Fortemente Conectados• Um grafo direcionado é dito fortemente conectado
se cada dois vértices quaisquer são alcançáveis a partir de um outro.
• Os componentes fortemente conectados de um grafo direcionado são conjuntos de vértices sob a relação “são mutuamente alcançáveis”.
• Um grafo direcionado fortemente conectado tem exatamente um componente fortemente conectado.
1. {A B C D são os componentes fortemente conectados
2. {E F}não são, pois F não é alcançável a partir de ECB
A D
F
E
O que fazer para deixar o grafo fortemente conectado?
Conceitos Básicos – SubGrafos
• Um grafo G’ = (V’;A’) é um subgrafo de G = (V;A) se V’ V e A’ A
• Dado um conjunto V’ V , o subgrafo induzido por V’ é o grafo G’ = (V’;A’), onde A’ = {(u; v) A | u; v V’}
CB
A D
F
E
B
A
F
E
C
D
B
A D1: 2: 3: 4:
Conceitos Básicos – Grafos Isomorfos
• G = (V;A) e G’ = (V’;A’) são isomorfos se:– V(G)=V(G’);– E(G)=E(G’); G = G’
• Ex.:
76
4 5
2
1
3
0
76
4 5
2
1
3
0
Conceitos Básicos – Pontos de Articulação
• São vértices que, se forem removidos do grafo, produzem pelo menos dois componentes conectados. Ex.:
1
2 4
3 5
6
7
8
9
1
2 4
3
6
7
8
9
5
Conceitos Básicos – Grafos Bi-Conectados
• São grafos que não possuem nenhum ponto de articulação. Exs.:
1
2 4
31
2
4
36
Conceitos Básicos – Grafos Ponderados
• Grafo Ponderado: grafos com pesos associados a seus arcos
• Ex.:
C
B
A
D
E
2
3
4
2
3
5
1
Outras Definições
• Grafos Finitos: um grafo é finito se V(G) e E(G) são finitos
• Grafos com apenas um vértice são ditos triviais.
• Um grafo é simples se não possuir loops e arestas múltiplas.
• Um grafo é completo se todos os vértices são adjacentes entre si.
Grafos - Representações
• Existem muitas formas de se representar grafos, porém vamos ver 3 tipos:– Matriz de Adjacências– Lista de Adjacências
Matriz de Adjacências
• Seja G = (V, A) um grafo com N vértices, a matriz de adjacência “A” de “G” é um arranjo bidimensional NXN, com as seguintes propriedades:1. A[i, j] = 1, se existe um arco do vértice i ao vértice j (ou
incide em j, no caso de grafos direcionados)2. A[, j] = 0, caso contrário3. Em casos de grafos ponderados (com pesos associados
às arestas), o valor a ser inserido refere-se ao peso da aresta;
Matriz de Adjacências - Exemplo
C
B
A
D
A B C DA 0 1 1 0B 1 0 1 0C 1 1 0 1D 0 0 1 0
C
B
A
D
A B C DA 0 0 1 0B 1 0 0 0C 0 1 0 1D 0 0 0 0
Matriz de Adjacências - ExemploA B C D
A 0 2 4 0B 2 0 3 0C 4 3 0 5D 0 0 5 0
A B C DA 0 0 4 0B 2 0 0 0C 0 3 0 5D 0 0 0 0
C
B
A
D
2
3
4
5
C
B
A
D
2
3
4
5
Matriz de Adjacências – Características
1. Vantagens:• Fácil visualização para vértices adjacentes
– Muito útil para algoritmos em que necessitamos saber com rapidez se existe uma aresta ligando dois vértices
• Fácil cálculo do grau do nó. – A soma dos números de uma linha retorna o grau do vértice,
em grafos não direcionados– Em grafos direcionados
• A soma dos números de uma linha retorna o grau de saída• A soma dos números de uma coluna retorna o grau de
entrada2. Desvantagens:• Requer muito espaço de armazenamento
– Deve ser mais utilizada para grafos densos
Lista de Adjacências
• Na Lista de Adjacências, as linhas da matriz são representadas por listas ligadas – Cada vértice corresponde a uma linha– Vértices que contém ligações diretas têm um nó
associado na linha
• Um vetor Vi é usado como cabeçalho para estas listas, onde i é um determinado vértice
Lista de Adjacências - Exemplo
C
B
A
D
C
B
A
D
A
B
C
D
B C
A C
A B
C
D
A
B
C
D
C
A
B D
Listas de Adjacências - Características
• Mais utilizada para grafos esparsos, pois também exige muito espaço para armazenamento
• Verificação de grau:– Não Direcionais: quantidade de nós em uma linha– Direcionais:
• A quantidade de nós de uma linha representa o grau de saída.
• Como saber o grau de entrada de cada nó?Deve-se pesquisar em todos os vértices do grafo, excluindo ele, se existe alguma referência para o nó em questão!!!
Implementações
Operações Básicas
• Iniciar_Grafo (Var G: Grafo): Inicializa um novo grafo• GrafoVazio (G: Grafo): Verifica se o grafo está vazio• InserirVertice (Var G: Grafo; x:TipoItem, Var flag:
boolean): insere o novo vértice (ou nó) x dentro do grafo G
• Inserir_Aresta (G: Grafo; x_orig, x_dest: TipoItem; Var flag: boolean): insere uma aresta (ou arco) que sai do nó x_orig ao nó x_dest
• Dentre outros, por exemplo, a busca, que será vista na próxima aula.
Matriz de Adjacência
CONST max=20; {Quantidade de vértices no grafo}TYPE TipoItem = Record
Chave: long; {Mais Outras Declarações Desejadas}END;TYPE TipoVertice = RECORD
Item: TipoItem; {Dado associado ao vértice}Visitado: Boolean; {Indica se o vértice já foi visitado}
END;TYPE Grafo = RECORD
Vertice: ARRAY[1..max] OF TipoVertice;Arestas: ARRAY[1..max, 1..max] OF
Boolean;VAR
G: Grafo;
Matriz de Adjacência – Iniciar Grafo
Procedure Iniciar_Grafo (Var G: Grafo)Var i, j: integer;Begin
For i :=1 to max doBegin {Denominar os vértices do grafo}
G.Vertice[i].Item := “”;G.Vertice[i].Visitado := false;
End;For i :=1 to max do {Arestas para cada vértice do grafo}
For i :=1 to max doG.Mat[i, j] := false
End;
Matriz de Adjacência – Verificar Grafo Vazio
Function Grafo_Vazio (G: Grafo): Boolean;Var i: integer;Begin
Grafo_Vazio := true;i := 1;While i <=max and Grafo_Vazio do
if G.Vertice[i].Item <> “” thenGrafo_Vazio := False;
End;
Matriz de Adjacência – Inserir Vértice
Procedure Inserir_Vertice (Var G: Grafo; x: TipoItem, Var flag: boolean);
Var i: integer;Begin
i := 1;while (i<=max) and G[i].Item <> ‘’ do
i := i+1;if i > n then
flag := falseelse begin
flag := true;G.Vertice[i].item := x;G.Vertice[i].visitado := false;
end;End;
Matriz de Adjacência – Inserir Aresta
Procedure Inserir_Aresta (Var G: Grafo; x_orig, x_dest: TipoItem, var flag: boolean);
Var linha, coluna: integer; paux: ponteiro; achou := false;Begin {Ao entrar nesse algoritmo, deve-se garantir que existe o ponteiro de origem}
linha := 1; achou := false;while (linha<=max and not achou) do {Achar a posição do item de destino}
if G.Vertice[linha].item = x_dest then achou := true;
coluna := 1; achou := false;while (j<=max and not achou) do {Achar a posição do item de origem}
if G.Vertice[coluna].item = x_orig then achou := true;
if linha>max or coluna >max then {Não achou a posição de origem ou destino}
flag := falseelse begin {Inserir a aresta}
flag := true;G.Aresta[linha, coluna] := true;
end;End;
Lista de Adjacência
CONST max=20; {Quantidade de vértices no grafo}TYPE ponteiro=^No;TYPE TipoItem = Record
Chave: long; {Outras Declarações Desejadas}
END;TYPE Vertices = RECORD
Item: TipoItem; {Dado associado ao vértice}Visitado: Boolean; {Indica se o vértice já foi visitado}Prox: Ponteiro; {Aponta para o próximo vértice, caso haja}
END;TYPE Grafo = ARRAY[1..max] OF Vertices;Var
G: Grafo;
Lista de Adjacência – Iniciar Grafo
Procedure Iniciar_Grafo (Var G: Grafo)Var i: integer;Begin
For i :=1 to max doBegin
G[i].Item := “”;G[i].Visitado := false;G[i].Prox := nil;
End;End;
Lista de Adjacência – Verificar Grafo Vazio
Function Grafo_Vazio (G: Grafo): Boolean;Var i: integer;Begin
Grafo_Vazio := true;i := 1;While i <=max and Grafo_Vazio do
if G[i].Item <> “” thenGrafo_Vazio := False;
End;
Lista de Adjacência – Inserir Vértice
Procedure Inserir_Vertice (Var G: Grafo; x: TipoItem, Var flag: boolean);
Var i: integer;Begin
i := 1;while (i<=max) and G[i].Item <> ‘’ do
i := i+1;if i > n then
flag := falseelse begin
flag := true;G[i].item := x;G[i].visitado := false;G[i].prox := nil;
end;End;
Lista de Adjacência – Inserir Aresta
Procedure Inserir_Aresta (Var G: Grafo; x_orig, x_dest: TipoItem, var flag: boolean);
Var i: integer; paux: ponteiro; achou := false;Begin {Ao entrar nesse algoritmo, deve-se garantir que existe o ponteiro de origem}
i := 1; achou := false;while (i<=max and not achou) do {Achar a posição do item de destino}
if G[i].item = xdest then achou := true;
if i>max then {Não achou a posição de destino}flag := false
else begin {Inserir a aresta}flag := true;new (paux);paux^.Item := x_orig;paux^.visitado := G[i].visitado;paux^prox := G[i].prox;G[i].prox := paux;
end;End;
FIM