Aula_01_-_Introdu__o_a_Algoritmos_em_Grafos (2)

Prévia do material em texto

ARA0175-ALGORITMOS EM GRAFOS
1. CONCEITUAÇÃO E FORMALIZAÇÃO DE GRAFOS
1.1 APLICAÇÕES CONTEMPORÂNEAS PARA GRAFOS
Tema
2ARA0175-ALGORITMOS EM GRAFOS
•1. CONCEITUAÇÃO E FORMALIZAÇÃO DE GRAFOS
•1.1 APLICAÇÕES CONTEMPORÂNEAS PARA GRAFOS
Agenda
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Objetivos da aula
• Motivação
• Contexto
• Introdução
• Conceitos e formalização de grafos. 
• Aplicações contemporâneas que utilizam grafos.
• Exemplos de problemas reais que podem ser representados com grafos.
- Problema das sete pontes de Konigsberg
- Problema do caixeiro viajante
- Problema do caminhão de lixo
- Problema do carteiro chinês
ARA0175-ALGORITMOS EM GRAFOS
Objetivos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
-Compreender os conceitos fundamentais sobre teoria dos grafos;
ARA0175-ALGORITMOS EM GRAFOS
-Empregar técnicas para resolver problemas baseados em grafos;
-Aplicar os fundamentos e conceitos dos grafos, com base nos requisitos e nas
melhores estratégias algoritmicas.
Contexto
AULA 1: APRESENTAÇÃO DA DISCIPLINA
Pode-se dizer que a matemática é a matéria prima da computação, os
problemas resolvidos com uma solução computacional, de alguma
forma, faz uso da matemática para chegar até a solução. A exemplo
disso temos a teoria dos grafos que é uma área de conhecimento da
matemática que aplicada a computação consegue resolver problemas de
natureza complexa, até então, não resolvidos.
ARA0175-ALGORITMOS EM GRAFOS
Motivação
AULA 1: APRESENTAÇÃO DA DISCIPLINA
-Grafos: conceito introduzido por Euler, em 1736 – Problema da Ponte de
Könisberg
-Modelos matemáticos para resolver problemas práticos do dia a dia.
-Muito usados para modelar problemas em computação -> ênfase em aspectos
computacionais
ARA0175-ALGORITMOS EM GRAFOS
História
AULA 1: APRESENTAÇÃO DA DISCIPLINA
Leonhard Euler é considerado o pai da Teoria dos grafos, o matemático nasceu na
Basileia-Suíça no ano de 1707.
ARA0175-ALGORITMOS EM GRAFOS
Quem é o inventor da Teoria dos grafos?
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
A teoria de grafos pode ser definido como uma estrutura, onde um conjunto
discreto e ordenado de pontos chamados vértices e um conjunto de linhas
chamadas arestas, onde cada aresta está conectada em pelo menos um vértice.
ARA0175-ALGORITMOS EM GRAFOS
O que é teoria de grafos?
Definições
AULA 1: APRESENTAÇÃO DA DISCIPLINA
De acordo com Euler, um caminho simples ou um circuito simples é dito euleriano
se ele contém todas as arestas de um grafo.
Um grafo do tipo circuito euleriano, é um grafo que contem um caminho que
visita toda aresta exatamente uma vez.
ARA0175-ALGORITMOS EM GRAFOS
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
Geometricamente falando, um vértice é um ponto em que duas ou mais curvas,
onde as retas ou arestas se encontram.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma vértice?
vértice
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
Geometricamente falando, um aresta é um tipo específico de segmento de reta que
liga dois vértices.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma Aresta?
aresta
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
A teoria de grafos pode ser definido como uma estrutura, onde um conjunto
discreto e ordenado de pontos chamados vértices e um conjunto de linhas
chamadas arestas, onde cada aresta está conectada em pelo menos um vértice.
ARA0175-ALGORITMOS EM GRAFOS
O que é teoria de grafos?
Vértices
Arestas
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
-Grafos: conceito introduzido por Euler, em 1736 – Problema da Ponte de
Könisberg, que é uma cidade alemã localizada no estado de Baviera.
-Modelos matemáticos para resolver problemas práticos do dia a dia.
-Muito usados para modelar problemas em computação -> ênfase em aspectos
computacionais
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição (Ex. Telefonia ou Provedores de internet)
• Relações de parentesco entre pessoas (arvore genealógica)
• Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Pag-A
Pag-B
Pag-C
Pag-D
Pag-E
Pag-F
Pag-Z
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore 
genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Aplicações contemporâneas que utilizam grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Redes de distribuição
• Relações de parentesco entre pessoas (arvore 
genealógica)
• Outras Redes Sociais
• Rotas entre cidades/vôos
• Redes (físicas e lógicas) de computadores
• Páginas da Web
• Serviço de distribuição elétrica
ARA0175-ALGORITMOS EM GRAFOS
Exemplos de problemas reais que podem ser representados com grafos.
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Controle de Frota de veiculo (estabelecer a melhor rota) 
• Mapeamento de rede de computadores
• Otimização de problemas computacionais
• Pesquisa operacional
• Resolver problemas como roteamento de pacotes da Internet
• Selecionar rotas de transportes com problemas de pesquisa operacional
ARA0175-ALGORITMOS EM GRAFOS
Problema que envolvem Grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
- Problema das sete pontes de Konigsberg
- Problema do cacheiro viajante
- Problema do caminhão de lixo
- Problema do carteiro chinês
ARA0175-ALGORITMOS EM GRAFOS
Problema das sete pontes de Konigsberg
AULA 1: APRESENTAÇÃO DA DISCIPLINA
Em que consiste?
ARA0175-ALGORITMOS EM GRAFOS
No século 13, um enigma mobilizouuma pequena cidade localizada ao norte da
Europa. Tratava-se do desafio das sete pontes de Königsberg, atual Kaliningrado.
Seis delas interligavam duas ilhas às margens do Rio Pregel e uma que fazia a
ligação entre as duas ilhas. O problema consistia na seguinte questão: como seria
possível fazer um passeio a pé pela cidade de forma a se passar uma única vez por
cada uma das sete pontes e retornar ao ponto de partida?
Problema das sete pontes de Konigsberg
AULA 1: APRESENTAÇÃO DA DISCIPLINA
Em que consiste?
ARA0175-ALGORITMOS EM GRAFOS
No século 13, um enigma mobilizou uma pequena cidade localizada ao norte da
Europa. Tratava-se do desafio das sete pontes de Königsberg, atual Kaliningrado.
Seis delas interligavam duas ilhas às margens do Rio Pregel e uma que fazia a
ligação entre as duas ilhas. O problema consistia na seguinte questão: como seria
possível fazer um passeio a pé pela cidade de forma a se passar uma única vez por
cada uma das sete pontes e retornar ao ponto de partida?
Problema do caixeiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Em que consiste?
Consistem em passar por um conjunto de cidades e uma matriz de distâncias
entre elas, o PCV consiste, então, em encontrar uma rota que:
• Parta da cidade origem;
• Passe por todas as demais cidades uma única vez;
• Retorne à cidade origem ao final do percurso;
• Percorra uma rota que dá a menor distância possível.
Problema do cacheiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Em que consiste?
Problema do cacheiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Se você precisasse viajar ate a cidade de Bucareste partindo de
Arad, qual percurso seguiria?
Problema do cacheiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Se você precisasse viajar ate a cidade de Bucareste partindo de
Arad, qual percurso seguiria?
Origem
Problema do cacheiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Se você precisasse viajar ate a cidade de Bucareste partindo de
Arad, qual percurso seguiria?
Origem
Problema do cacheiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Se você precisasse viajar ate a cidade de Bucareste partindo de
Arad, qual percurso seguiria?
Origem
Problema do cacheiro viajante-PCV
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Se você precisasse viajar ate a cidade de Bucareste partindo de
Arad, qual percurso seguiria?
Destino
Problema do caminhão do lixo
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Em que consiste?
Consiste em realizar a coleta do lixo de forma mais
otimizada possível, onde cada rota pode ser otimizada
de uma forma que o motorista receba o itinerário na
ordem em que deve realizar as coletas. Reduzindo
assim, o tempo de deslocamento entre as residências
e outra, levando à redução de custos com a melhoria
na logística, utilizando os melhores trajetos para
realização de cada coleta.
Problema do carteiro chinês
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Em que consiste?
O nome do problema está relacionado ao problema
do planejamento de rotas de carteiros: dada uma cidade com várias ruas de
diferentes comprimentos e um posto de carteiros, encontrar a menor rota
que um carteiro deve percorrer de modo a passar por todas ruas da cidade
entregando cartas e voltar ao posto de carteiros no fim de sua rota.
Problema do carteiro chinês
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Em que consiste?
O matemático chinês Meigu Guan publicou um estudo que generalizava
ainda mais o problema dos grafos eulerianos. Esse problema foi
denominado Problema da Inspeção de Rotas, ou, como também é
conhecido hoje: Problema do carteiro chinês (PCC), nomeado assim em
homenagem a Guan.
Problema do carteiro chinês
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Representação de problema com arvore de decisão
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Kahoot!
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Acessar:
www.kahoot.it
Sistemas Embarcados
Bibliografia Básica
NETTO, Paulo O. B.; JURKIEWICZ, Samuel. Grafos: 
Introdução e Prática. 2 ed.. São Paulo:
Blucher, 2017. Disponível em: 
https://plataforma.bvirtual.com.br/Acervo/Publicacao/173348
SCHEINERMAN, Edward R. Matemática Discreta: uma 
introdução. São Paulo: Cengage
Learning., 2016. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788522125388
/cfi/0!/4/2@100:0.00
SIMÕES PEREIRA, J.M.S. Grafos e Redes: Teoria e 
Algoritmos Básicos. RJ: Ed. Rio de Janeiro,
2013. Disponível em: 
https://plataforma.bvirtual.com.br/Leitor/Publicacao/42049/pdf
ARA0175-ALGORITMOS EM GRAFOS
Sistemas Embarcados
Bibliografia Complementar
AIGNER, Martin. Paul. Erdós: As mais belas demonstrações matemáticas. São Paulo: 
Blucher,2017. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788521210047/cfi/0!/4/2@100:0.00
DASGUPTA, Sanjoy. Algoritmos. Porto Alegre: AMGH, 2010.
Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/cfi/0!/4/2@100:0.00
DROZDEK, Adam. Estrutura de Dados e Algoritmos em C++. São Paulo: Cengage
Learning Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788522126651/cfi/0!/4/2@100:0.00
LOESCH, CLa?udio; HEIN, Nelson. Pesquisa Operacional: Fundamentos e modelos. São 
Paulo:Saraiva, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788502088924/cfi/0!/4/2@100:0.00
STEIN, Clifford; DRYSDALE, Robert L.; BOGART, Kenneth. Matemática Discreta para 
Ciência da Computação. São Paulo: Pearson, 2013.
Disponível em: https://plataforma.bvirtual.com.br/Acervo/Publicacao/3824
ARA0175-ALGORITMOS EM GRAFOS