TEORIA DE GRAFOS

• LAMOUNIER JOSINO DE ASSIS

2012

Prof.: Lamounier Josino de Assis

APRESENTAÇÃO DO PROBLEMA: Trajeto do Caminhão de Lixo

Condomínio Fechado

Prof.: Lamounier Josino de Assis

Considerações• O caminhão deverá ser utilizado no momento em que

passar pelo cruzamento das ruas, local onde se encontra a portaria.

• O caminhão deverá trafegar dentro do condomínio de tal forma que atenda a todos os moradores.

• O percurso realizado pelo caminhão deverá ser ótimo, ou seja, deve-se levar em conta entre eles:

Custo de um trecho dependendo do grau de dificuldade( plano, congestionado, aclive ).

Custo pela distância percorrida.

Prof.: Lamounier Josino de Assis

TRAJETO ÓTIMO• Dada a Vila Realeza abaixo, verifique se é possível encontrar um trajeto ótimo,

para que Leomar funcionário do sitio toca do Lobo possa entregar as encomendas nos pontos indicados no mapa, passando por todos os trechos de ruas da vila onde mora e, voltar ao sitio novamente.

Correio

Quitanda

Mercado

Bar

Igreja SitioEscola

Prof.: Lamounier Josino de Assis

APRESENTAÇÃO DO PROBLEMA:

Mapa das Rotas de um Avião.Qual é o trajeto ótimo para que um avião saindo de BH voe para todas

as outras Capitais conforme rota indicada e, retorne a BH.

Belo Horizonte

São Paulo

Vitória

Salvador

Rio de Janeiro

Alagoas

Recife

Aracaju

Natal

Prof.: Lamounier Josino de Assis

• 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

MODELAGEM MATEMÁTICA

• Representando os cruzamentos por pontos.

• Enumerando-os.

• Substituindo os trechos por linhas

Prof.: Lamounier Josino de Assis

Modelagem do Problema

Condomínio Representado por Diagrama

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

Modelagem do Problema

• Vila Realeza representada por diagramaPosto 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.

AC D

E

FGH

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

1 2 3 4

78

9 10 11

6

12

5

Prof.: Lamounier Josino de Assis

MATEMÁTICA NO PROBLEMA• Essa dupla de conjuntos define um ente

matemático muito conhecido, denominado GRAFO.

• Um grafo é uma estrutura matemática constituída de dois conjuntos.

• Um conjunto V, finito e não vazio, de n vértices, e outro E, de m arestas, que são pares não ordenados de elementos de V.

Prof.: Lamounier Josino de Assis

• 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

78

9 10 11

6

12

5

Prof.: Lamounier Josino de Assis

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

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

MODELO ABSTRATO USADO POR EULLER

• Diagrama das pontes representado por um Multgrafo(arestas paralelas).

A

B

D

C

Prof.: Lamounier Josino de Assis

• 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

PARALELO ENTRE O PROBLEMA DAS PONTES DE KÖNIGSBERG E O TRAJETO DO CAMINHÃO DE LIXO

PONTES DE KÖNIGSBERGProcura-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

• 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

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 nasarestas– Vértices: cidades– Arestas: estradas– Pesos: distâncias

A

EB

C D

9 6

8

73 2

583

6

Prof.: Lamounier Josino de Assis

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

Aplicações: ArquiteturaAnálise de projetos 1: área exterior

2: hall3: sala4: sacada/varanda5: corredor6: quarto7: banheiro8: estudos/escritório9: cozinha10: área de serviços

Vértices de grau mais baixo áreas mais isoladas ou de maior privacidade

Prof.: Lamounier Josino de Assis

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

RECURSOS COMPUTACIONAIS

• Utilizando recursos computacionais

Problema Real Modelo Matemático

Processamento Do programa

Análise de Resultados

Construção ouEscolha do algoritmo

Elaboração doPrograma

Prof.: Lamounier Josino de Assis

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

Definições - PrimordiaisGrafo 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

6541 2 3

4 5 6Prof.: Lamounier Josino de Assis

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

654

Prof.: Lamounier Josino de Assis

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

bCiclo Euleriano

a – b – c – d – e – f – a – d – b – e - a

Prof.: Lamounier Josino de Assis

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.

C2C1

Prof.: Lamounier Josino de Assis

8

109

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

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

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

• 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

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

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

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

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

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

1 2 3 4

78

9 10 11

6 5

12

Prof.: Lamounier Josino de Assis

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