Teoria Grafos

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

MODELAGEM MATEMÁTICA
Representando os cruzamentos por pontos.
Enumerando-os.
Substituindo os trechos por linhas 
Prof.: Lamounier Josino de Assis
7
Percurso Ótimo: É aquele de mínimo custo dentre todos os possíveis trajetos
Substituição do problema real pelo o abstrato, reescrevendo todas as hipóteses do problema em termos Matemáticos formalizando a linguagem. Isto evita ambiguidade.
Prof.: Lamounier Josino de Assis
6
 Modelagem do Problema 
Vila Realeza representada por diagrama
Posto Correio 
Escola
Quitanda
Armazém
Igreja
Bar
Sitio Toca do Lobo
Prof.: Lamounier Josino de Assis
Modelagem do Problema
Mapa das Rotas de um Avião representado por um Grafo.
A
C
D
E
F
G
H
I
J
Prof.: Lamounier Josino de Assis
	DIAGRAMA MEDIANTE DOIS CONJUNTOS
Um conjunto de pontos, que, no problema real, são as esquinas, ou seja, os cruzamentos das ruas.
Um conjunto formado por pares desses pontos, que correspondem aos trechos de rua do condomínio. 
Prof.: Lamounier Josino de Assis
11
1
2
3
4
7
8
9
10
11
6
12
5
Prof.: Lamounier Josino de Assis
Modelagem do Problema
Condomínio Representado por Diagrama
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
8
V={1,2,3,4,5,6,7,8,9,10,11,12}
E={(1,1),(1,2),(1,8),(2,3),(2,7),(2,8),(3,4), 	(3,5),(3,6),(4,5),(5,6),(5,12),(6,7),(7,8),
		(8,9),(9,10),(10,7),(11,6),(11,12)}
1
2
3
4
7
8
9
10
11
6
12
5
Prof.: Lamounier Josino de Assis
14
A BUSCA DA SOLUÇÃO MEDIANTE O ESTUDO DA TEORIA DE GRAFOS
Século XVIII – Ponte de Könisgsberg, hoje Kalininigrado - Problema das setes pontes
B
C
A
D
Prof.: Lamounier Josino de Assis
15
PROBLEMA DAS SETES PONTES
Existe um trajeto que, tendo qualquer uma das pontes da terra como origem, percorra todas as pontes, exatamente uma vez e retornar ao ponto inicial.
Euller(1707- 1783), matemático suíço, nascido na Basiléia, sendo informado sobre o problema, não só o resolveu, como também ,ao estudar a questão, criou a Teoria dos Grafos.
Prof.: Lamounier Josino de Assis
16
MODELO ABSTRATO USADO POR EULLER
Diagrama das pontes representado por um Multgrafo(arestas paralelas).
A
B
D
C
Prof.: Lamounier Josino de Assis
17
Após criar essa nova estrutura e definir alguns conceitos elementares, Euler utilizou-os para reescrever a questão do problema.
Existe um ciclo de origem arbitrária no grafo da figura anterior, contendo todos as suas arestas?
Convém observar que cada aresta deve ocorrer exatamente uma vez, já que, em ciclos, não é permitida a repetição delas. 
Prof.: Lamounier Josino de Assis
18
PARALELO ENTRE O PROBLEMA DAS PONTES DE KÖNIGSBERG E O TRAJETO DO CAMINHÃO DE LIXO 
	PONTES DE KÖNIGSBERG
Procura-se um trajeto que, tendo uma das partes de terra como ponto inicial, percorra todas as pontes exatamente uma vez e retorne ao ponto de partida. No grafo, esse trajeto corresponde à determinação de um ciclo de origem arbitrária que contenha todas as suas arestas
	TRAJETO DO CAMINHÃO 	DE LIXO
Deve-se determinar um trajeto que parta do vértice 1, percorra todos os trechos de rua pelo menos uma vez e retorne ao vértice 1, com o menor custo possível. No grafo, esse trajeto corresponde à determinação de uma cadeia fechada de origem 1, de custo mínimo, que contenha todas as suas arestas 
Prof.: Lamounier Josino de Assis
19
Ao fixar o vértice 1, como inicial, no problema do caminhão de lixo, o problema das pontes fica particularizado e, caso seja obtida uma solução que percorra cada trecho de rua exatamente uma vez, evidentemente esse percurso terá custo mínimo.
Diante dessas semelhanças, a solução obtida por Euler para o problema das pontes poderia ser usada para encontrar bons resultados para o problema do caminhão de lixo.
Prof.: Lamounier Josino de Assis
20
OUTRAS APLICAÇÕES
O Problema do Caixeiro Viajante: Um caixeiro viajante deseja visitar um número de cidades e voltar ao ponto de origem de maneira que ele visite todas as cidades e percorra a menor distância possível. Como escolher sua rota?
Representação: grafo com peso nas
	arestas
Vértices: cidades
Arestas: estradas
Pesos: distâncias
A
E
B
C
D
9
6
8
7
3
2
5
8
3
6
Prof.: Lamounier Josino de Assis
21
Aplicações: hierarquização
 Biólogos utilizam grafos para determinar funções específicas de genes e proteínas via hierarquização.
Prof.: Lamounier Josino de Assis
22
Aplicações: Arquitetura
Análise de projetos
1: área exterior
2: hall
3: sala
4: sacada/varanda
5: corredor
6: quarto
7: banheiro
8: estudos/escritório
9: cozinha
10: área de serviços
Vértices de grau mais baixo  áreas mais isoladas ou de maior privacidade
Prof.: Lamounier Josino de Assis
23
FASES DE RESOLUÇÃO DE PROBLEMAS
Utilização da Matemática como ferramenta para a obtenção da solução
Problema Real
Modelo
 Matemático
Resolução do Modelo 
Matemático
Análise de
 Resultados
Prof.: Lamounier Josino de Assis
24
RECURSOS COMPUTACIONAIS
Utilizando recursos computacionais
Problema Real
Modelo
 Matemático
Processamento 
Do programa
Análise de
 Resultados
Construção ou
Escolha do 
algoritmo
Elaboração do
Programa
Prof.: Lamounier Josino de Assis
25
Algoritmo de Euler
Entrada: Grafo G conexo contendo apenas vértices de grau par.
Saída: Ciclo Euleriano C.
Escolha um vértice arbitrário do grafo como origem e, a partir dele, encontre um ciclo C1 em G.
C:= C1
Exclua todas de C1 de G.
Enquanto G for não nulo faça
Escolha um vértice de C, extremo de alguma aresta remanescente de G. A partir desse vértice, encontre outro ciclo C1 de G.
C:= C o C1( Concatene C1 com C).
Exclua todas as arestas de C1 de G.
Imprima C, o ciclo euleriano procurado.
Prof.: Lamounier Josino de Assis
26
Definições - Primordiais
Grafo Conexo – É aquele que possui um caminho entre todos os pares de seus vértices, ou seja, a partir de um vértice arbitrário do grafo é possível alcançar todos os demais.Caso contrário, ele é grafo desconexo. 
 desconexo
conexo
1
2
3
6
5
4
1
2
3
4
5
6
Prof.: Lamounier Josino de Assis
27
Definições - Primordiais
Caminho Simples- É um caminho com vértices distintos. Ex: < 1,4,5,2,3 >
Ciclo de origem v- É um caminho fechado, isto é, com origem e término em v. Ex: < 1,4,5,2,1 >
Grau de um vértice- É o número 
de incidências de arestas em um vértice.
 		Ex: vértice 1- grau 2
		 vértice 2- grau 3	
 		 vértice 3- grau 1
 		 vértice 4- grau 2
		 vértice 5- grau 3
 vértice 6- grau 1
1
2
3
6
5
4
Prof.: Lamounier Josino de Assis
28
CICLO EULERIANO
É aquele que possui todas as arestas do grafo, isto é, se podemos percorrer cada aresta uma e só uma vez partindo de um vértice e a ele retornando. 
c
d
e
f
a
b
Ciclo Euleriano
a – b – c – d – e – f – a – d – b – e - a 
Prof.: Lamounier Josino de Assis
29
CONCATENAÇÃO
Dois ciclos C1 e C2, disjuntos por arestas, podem ser concatenados se possuírem um vértice em comum.
Origem 1
8
2
8
7
9
10 origem
O primeiro passo é alterar a origem de C2 para v. em seguida, os vértices de C2 devem substituir uma ocorrência do vértice v em C1.
C2
C1
Prof.: Lamounier Josino de Assis
30
8
10
9
passa ser origem 8
7
9
10 
Concatenando, temos: C1 o C2 =<1,2,8,7,10,9,8,1>
7
9
10 
8
 1
 2
origem
Prof.: Lamounier Josino de Assis
31
A OBTENÇÃO DA SOLUÇÃO
Obedecendo as condições impostas pelo algoritmo de Euler, esse pode ser aplicado ao grafo G(V,E) 
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
32
Sendo fictícia a aresta (1,1), já que o trecho de rua a ele associado não pertence ao condomínio, e sendo inserida apenas viabilizar a construção do modelo, é conveniente que o processamento seja iniciado por ciclo que a contenha, para tão logo o ciclo euleriano seja encontrado, ela seja seccionada, restaurando as condições iniciais do problema.
Iniciando a aplicação do algoritmo, sejam C = Ø, C1=<1,1>.
Seja, agora, C= <1,1>.
Escolhendo-se o vértice 1 e, a partir dele, determinando um novo ciclo em G-C1 , encontra-se C1=<1,2,3,4,5,6,7,8,1>.Excluindo-se todas as arestas de C1 de G, obtém-se o grafo a seguir. 
Prof.: Lamounier Josino de Assis
33
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de
Assis
34
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
35
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
36
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
37
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
38
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
39
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
40
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
41
1
2
3
4
7
8
9
10
11
6
5
12
Concatenando C1 a C, encontra-se C=<1,1,2,3,4,5,6,7,8,1> e sendo G um grafo não nulo, deve-se iniciar a segunda iteração do algoritmo. Escolhendo-se o vértice 2, a partir dele, encontra-se o novo ciclo C1=<2,7,10,9,8,2>. A seguir tem-se o grafo
 G –C1. 
Prof.: Lamounier Josino de Assis
42
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
43
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
44
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
45
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
46
1
2
3
4
7
8
9
10
11
6
5
12
Concatenados C e C1,,obtém-se: 
C=<1,1,2,7,10,9,8,2,3,4,5,6,7,8,1>. Escolhendo o vértice 3 e determinando-se o novo ciclo C1=<3,5,12,11,6,3>. Excluindo-se de G as aresta de C1, surge o grafo a seguir
Prof.: Lamounier Josino de Assis
47
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
48
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
49
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
50
1
2
3
4
7
8
9
10
11
6
5
12
Prof.: Lamounier Josino de Assis
51
1.
2 .
3.
4 .
 7.
 8 .
 9.
 10 .
 11.
 6.
5.
12.
Fazendo-se concatenação de C com C1, determina-se:
C=<1,1,2,7,10,9,8,2,3,5,12,11,6,3,4,5,6,7,8,1>. Sendo G nulo, c é ciclo euleriano procurado. Excluindo-se de c a aresta (1,1), que representa o movimento do caminhão fora do condomínio, determina-se o ciclo:
C=<1,2,7,10,9,8,2,3,5,12,11,6,3,4,5,6,7,8,1>, que é trajeto ótimo do caminhão de lixo, resolvendo-se, assim o problema proposto.
Prof.: Lamounier Josino de Assis
52