Introdução aos Grafos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
GRAFOS
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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)
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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),
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
EXEMPLOS DE GRAFOS
A
C
B
1:
A
2:
C
B
A
3:
A
B
4:
A
5:
C
B
A
6:
C
B
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos
Quantos arcos teria um grafo com N vértices?
Ex.: 
C
B
A
D
B
A
B
A
C
1:
2:
3:
R.: 1 arco
R.: 3 arcos
R.: 6 arcos
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.:
C
B
A
1:
C
B
A
2:
D
E
2
1
3:
3
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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) = 1
Grau(B) = 2 Grau(D) = 1
Grau(A) = 3 Grau(D) = 3
Grau(B) = 4 Grau(E) = 1
Grau(C) = 4 Grau(F) = 1
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos – Caminho e Comprimento
C
B
A
D
Caminho: (C B D)
Comprimento: 2
D é alcançável a partir de C
A não é alcançável a partir 
	de nenhum vértice
O caminho mostrado é simples
C
B
A
D
F
E
Caminho: (A D C B)
Comprimento: 3
B é alcançável a partir de A, 
	mas E não.
O caminho mostrado é simples
Já o caminho (A B A B) não é
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos – Ciclos
Ciclo: (B C D)
Os caminhos (B C D),
(C D B) e (D B C) formam 
o mesmo ciclo
Ciclo: (A D C B A)
Self-loop: (C C)
Os caminhos (A D B A), 
(D B A D) e (B A D B) 
formam o mesmo ciclo
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos - Árvores
Um grafo acíclico conectado uma árvore pode se tornar uma árvore genérica 
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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
Representação Planar do Grafo:
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.
O grafo não é conectado, pois 
não é possível alcançar A a partir 
dos vértices B, C ou D
O grafo {C D B} é um
componente conectado do grafo
Inserindo-se o arco (A B), o
Grafo passa a ser conectado
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.
{A B C D são os componentes fortemente conectados
{E F}não são, pois F não é alcançável a partir de E
O que fazer para deixar o grafo fortemente conectado?
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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’}
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.:
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos – 
Pontos de Articulação
São vértices que, se forem removidos do grafo, produzem pelo menos dois componentes conectados. Ex.:
5
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos – 
Grafos Bi-Conectados
São grafos que não possuem nenhum ponto de articulação. Exs.:
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Conceitos Básicos – 
Grafos Ponderados
Grafo Ponderado: grafos com pesos associados a seus arcos
Ex.:
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Grafos - Representações
Existem muitas formas de se representar grafos, porém vamos ver 3 tipos:
Matriz de Adjacências
Lista de Adjacências
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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:
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)
A[, j] = 0, caso contrário
Em casos de grafos ponderados (com pesos associados às arestas), o valor a ser inserido refere-se ao peso da aresta;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Matriz de Adjacências - Exemplo
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Matriz de Adjacências - Exemplo
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Matriz de Adjacências – Características
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 entrada
Desvantagens:
Requer muito espaço de armazenamento
Deve ser mais utilizada para grafos densos
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Lista de Adjacências - Exemplo
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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!!! 
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Implementações
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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.
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Matriz de Adjacência – 
Iniciar Grafo
Procedure Iniciar_Grafo (Var G: Grafo)
Var i, j: integer;
Begin
	For i :=1 to max do
		Begin {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 do
			G.Mat[i, j] := false
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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 <> “” then
			Grafo_Vazio := False;
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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 := false
	else begin
		flag := true;
		G.Vertice[i].item := x;
		G.Vertice[i].visitado := false;
	end;
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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 := false
	else begin {Inserir a aresta}
		flag := true;
		G.Aresta[linha, coluna] := true;
	end;
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
Lista de Adjacência – 
Iniciar Grafo
Procedure Iniciar_Grafo (Var G: Grafo)
Var i: integer;
Begin
	For i :=1 to max do
		Begin
			G[i].Item := “”;
			G[i].Visitado := false;
			G[i].Prox := nil;
		End;
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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 <> “” then
			Grafo_Vazio := False;
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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 := false
	else begin
		flag := true;
		G[i].item := x;
		G[i].visitado := false;
		G[i].prox := nil;
	end;
End;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
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;
*Celso A. Saibel Santos
Ano 2002 
*Estrutura de Dados – Árvores Binária de Busca
*
FIM