Representação Grafo

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

*
*
*
Representação de grafos
Introdução
Seja a figura abaixo a planta baixa de um museu de arte de uma determinada cidade X. 
O museu possui seis salas que se comunicam internamente e quatro portas que fazem a ligação externa. Suponha que, no momento em que os visitantes se encontram na sala B, ocorre um incêndio no telhado do museu. Qual instrução deve ser dada pelo segurança, para que os nela se encontrem atinjam a parte externa do museu o mais rápido possível.
A
C
B
E
D
F
Prof.: Lamounier Josino de Assis
*
*
*
MODELAGEM DO PROBLEMA POR DE UM GRAFO
Associando respectivamente às salas A, B, C, D, E, F do museu os vértices a, b, c, d, e, f ,e à sua parte externa,o vértice g.
Definindo suas arestas como os pares de vértices (v,w) que corresponde as duas salas que se comunicam, ou a uma sala e a parte externa do museu, caso elas se comunique.Obtém-se o grafo G(V,E) abaixo	
a
b
c
d
g
f
e
Prof.: Lamounier Josino de Assis
*
*
*
CAMINHO MÍNIMO ENTRE OS VÉRTICES
A questão do problema é indagar sobre o trajeto mais rápido que deve ser seguido por um visitante que se encontra na sala B para atingir a saída em g.
Caminho mínimo entre os vértices b e g.
C1< b,a,g >, C2< b,a,d,g >, C3< b,a,d,e,g >,C4< b,a,d,e,f,g >,
 C5< b,c,e,g >, C6< b,c,e,f,g >,C7< b,c,e,d,g >, C8< b,c,e,d,a,g >.
Deles qual é o caminho mínimo?
Lembrete: caminho mínimo é aquele de menor comprimento, ou seja, aquele que percorre o menor de arestas de b a g. Logo C1 deve ser escolhido. 
 
 
 
 
 
Prof.: Lamounier Josino de Assis
*
*
*
MALHA VIÁRIA DE UMA CIDADE
a malha viária de uma cidade pode ser representada por meio de um grafo, onde as esquinas são os vértices e os trechos de rua as arestas.
Obs.: Às arestas podem-se atribuir valores que correspondem ao custo de percorrer trechos de ruas a elas associados.
Uma Aplicação: Qual o melhor caminho para uma ambulância que se encontra no vértice Va e tenha que se dirigir a um hospital localizado próximo do vértice Vk?.
Prof.: Lamounier Josino de Assis
*
*
*
 Torna-se inviável, já que a resposta deve ser dada com precisão, diante do grande número de opções disponíveis
Prof.: Lamounier Josino de Assis
*
*
*
Obs.:
A utilização do computador para fornecer a resposta é inevitável
Deve-se estabelecer uma forma de representação de grafos que se encontre adequada à máquina e utilizar algoritmos mais eficientes na solução do problema.
Torna-se necessário indagar sobre o número máximo de arestas de grafos e digrafos, e possível relação que ele possa ter com o seu número de arestas.
Número Máximo de Arestas de Grafos e Digrafos.
Ex) Em um torneio de futebol, participarão seis times. Cada equipe deve jogar exatamente uma vez com cada uma das outras participantes. Quantos jogos haverá no torneio?
Prof.: Lamounier Josino de Assis
*
*
*
MODELAGEM DO PROBLEMA
G(V,E) o grafo tal que:
V={ cada time de futebol que participará do torneio}
E={ (v,w) representa o jogo entre os times v e w}
Obs.: número de arestas = número de jogos
Questão: Quantas arestas possui G?
Resolução: 
Cn,p= n!/(n-p)! P!, pois
Não importa a ordem dos
Jogos.
C6,2= 6!/(6-2)!2! = 15 jogos
Conclusão
Se G é um grafo simples, com n vértices e m arestas , então o nº de arestas é 
 m ≤ Cn,2 => m ≤ n!/(n-2)!2! = n(n-1)(n-2)/(n-2)! 2 => m ≤n(n-1)/2
v
r
t
u
s
w
r
Prof.: Lamounier Josino de Assis
*
*
*
Obs.: Caso os laços sejam permitidos, basta adicionar a n(n-1)/2 o número de laços que podem ser formados com os n vértices do grafo, ou seja, n arestas do tipo (v,v).
Assim, temos: n(n-1)/2 + n =
 (n² - n + 2n)/2 =
 (n² + n )/2=
n(n+1)/2 Combinação com repetição que podem ser formados com n elementos agrupados 2 a 2.
Consideremos o problema anterior com jogos de ida e volta.
Modelagem: Digrafo
V={ cada time do torneio é representado por um vértice}
E={ a aresta (v,w) representa o jogo entre v e w na casa de w, logo (v,w) ≠ (w,v)
A questão Quantos jogos possui o torneio, passa a ser quantas arestas possui o digrafo?
Prof.: Lamounier Josino de Assis
*
*
*
Resolução:
A6,2 = 6!/(6-2)! = 30 => An,p = n!/(n-p)!, uma vez que a ordem dos elementos são importantes, isto é, (v,w) ≠ (w,v).
Obs.: 
a) Para digrafo D(V,E) simples de n vértices e m arestas temos:
An,2 = n!/(n-2)! = n(n-1)! => m ≤ n(n-1) arestas.
b) Laços Permitidos => An,2 = n arestas =>n(n-1) + n = n² -n + n
 Logo m ≤ n².( Arranjo com repetição formados com n objetos agrupados 2 a 2.
Conclusão: O número de arestas de grafos e digrafos simples estão associados ao grau do vértice, ou seja, cada aresta do grafo contribui com duas unidades para a determinação dos graus dos vértices, uma unidade para cada vértice que a define. 
Logo, 
 A soma dos graus dos vértices é 
 igual ao dobro do nº de arestas do 															grafo
 
*
*
*
Exemplo - Grafo
Seja o grafo dado abaixo.
1
2
3
5
4
Prof.: Lamounier Josino de Assis
*
*
*
Exemplo - Digrafo
Para digrafos existem dois tipos de graus associados
Grau+ (v): (v,x) => aqueles que têm v como origem 
Grau- (v): (x,v) => aqueles que têm v como destino
1
2
3
4
Prof.: Lamounier Josino de Assis
*
*
*
REPRESENTAÇÃO DE GRAFOS E DIGRAFOS
Embora a representação geométrica tenha grande apelo visual, existem situações nas quais seu uso torna-se ineficiente.
Um grafo pode ter inúmeras representações, já que os pontos, substitutos dos vértices, podem ocupar posições arbitrárias no plano, fazendo com que as linhas, associadas às arestas, possuam as mais variadas formas.
Três representações geométricas distintas para o mesmo grafo G
1
2
4
3
1
2
3
4
1
3
4
2
Prof.: Lamounier Josino de Assis
*
*
*
OUTRAS FORMAS DE REPRESENTAÇÃO DE G
Um grafo é uma relação binária em V. Suas arestas são, portanto, elementos dimensionais. Quando se fala em dimensão, alguns entes matemáticos passam a ser lembrados, um deles é a MATRIZ.
VANTAGENS:
O fato de as matrizes serem facilmente manuseáveis.
Toda teoria desenvolvida da álgebra poderá ser aplicada quando se fizer necessária.
Prof.: Lamounier Josino de Assis
*
*
*
COMO UMA MATRIZ REPRESENTARIA UM GRAFO
Linhas e colunas indexadas com i, estarão associadas ao vértice i.
Supondo a não existência de arestas paralelas, o elemento ai j o código 1 se a aresta (i,j)  E, caso contrário ele codificado com o valor 0(zero)
Pelo fato de dois vértices serem denominados adjacentes, quando define uma aresta, a matriz que registra esse relacionamento entre eles é denominada matriz de adjacências do grafo. 
Prof.: Lamounier Josino de Assis
*
*
*
Representação Matricial
Seja o Grafo G(V,E)
A matriz de adjacências do grafo é
1
4
3
2
0	1	0	1
1	0	1	1
0	1	0	0
1	1	0	0			
Prof.: Lamounier Josino de Assis
*
*
*
Representação Matricial
1	1	0	1
1	0	1	0
0	1	0	2
1	0	2	0			
1
 2
3
4
3
*
*
*
GRAFO DIRECIONADO
Em um grafo direcionado, a matriz de adjacência reflete o sentido de orientação das arestas
Em um grafo simples com peso, os elementos na matriz de adjacência podem indicar uma aresta pelo número apropriado,no lugar da aresta de número 1
1	1	0	0
0	0	1	1
0	1	0	0
0	0	1	0			
3
1
 4
 2
*
*
*
LISTA DE ADJACÊNCIA
Nessa estrutura de dados, são utilizadas n listas encadeadas e um vetor de n posições. Cada posição do vetor associa-se a um dos vértices do grafo e contém um ponteiro que indica a posição inicial de uma das lista.
1
3
2
4
4
2
4
3
1
.
.
2
.
2
1
.
1
2
4
3
*
*
*
Lista de Adjacência para Digrafos
Para cada registro na lista, a primeira componente é o vértice, a segunda é o peso da aresta que termina no vértice e a terceira é o ponteiro. 
1
3
2
4
2
3
5
2
1
2
4
3
2
5
4
3
2
4
3
.
.
.
1
1
3
4
.
*
*
*
Comentários
1- para encontrar todos os vértices adjacentes a um determinado vértice vi é necessário olhar toda i-ésima linha da matriz de adjacência, um total de n elementos.
2- Para encontrar todos os vértices adjacentes a vi, é preciso percorrer a lista encadeada
para vi, que pode ter muito menos do que os n elementos que teríamos que examinar na matriz de adjacência.
3- Desvantagem:
	Se quisermos determinar se um determinado vértice vj é adjacente a vi podemos ter que percorrer toda a lista encadeada de vi, ao passo que, na matriz de adjacência, podemos acessar o elemento i, j diretamente
*
*
*
A matriz de adjacências do grafo é
0	1	0	1
1	0	1	1
0	1	0	0
1	1	0	0			
Propriedades
É simétrica, isto é,
 a i j = a j i , i,j
Se o grafo não possui laços, então a soma dos elementos da linha i e a soma dos elementos da coluna j, são iguais ao grau do vértice i
Prof.: Lamounier Josino de Assis
*
*
*
*
*