TEMA_1_-_ARA0175_-_INTRO_ALGORITMOS_EM_GRAFOS

Prévia do material em texto

Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TEMA 1 – Introdução ao Algoritmos em Grafos
ALGORITMOS EM GRAFOS - Ementa Geral
1. CONCEITUAÇÃO E FORMALIZAÇÃO DE GRAFOS
2. CÁLCULO DE CONEXIDADE E DISTÂNCIA
3. CAMINHOS EM GRAFOS
4. TÉCNICAS DE BUSCAS EM GRAFOS
5. GRAFOS PLANARES E COLORAÇÃO
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 2
Processo de Avaliação
Avaliação (AV)
Para a Aprovação na disciplina, o aluno deverá:
• Atingir resultado igual ou superior a 6,0.
• Frequentar, no mínimo, 75% das aulas ministradas.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 3
Processo de Avaliação
Avaliação (AVS)
Caso o aluno não atinja o resultado desejado na prova de AV, ele
poderá recuperar sua nota na prova de AVS.
Será composta por uma prova no formato PNI - Prova Nacional
Integrada, com total de 10 pontos, e substituirá a nota da AV,
caso seja maior.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 4
Informações Gerais 
• Frequências: Lembrando que o aluno(a) deve ter Presença
confirmada igual ou superior a 75% das aulas ministradas.
Presença menor que esse valor o aluno será considerado
Reprovado por Falta (RF) ao final do semestre na disciplina.
• Exercícios e Avaliações: Imagens copiadas de outros e códigos de
programação claramente semelhantes serão desconsiderados e
em caso de Avaliações, terão as notas devidamente descontadas.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 5
Bibliografia Básica - Programação
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 6
Ascencio, Ana Fernanda Gomes; Araújo, Graziela Santos de.
Estruturas de Dados. Algoritmos, Análise da Complexidade
e Implementações em Java e C/C++ [BV:PE]. 1. ed. São
Paulo: Pearson, 2013. Disponível em:
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995/pdf
Manzano, José Augusto N. G. Algoritmos - Lógica para
Desenvolvimento de Programação de Computadores
[BV:MB].. 28. ed. São Paulo: Érica, 2016. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788536518657/cfi/0!/4
/4@0.00:0.00
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995/pdf
https://integrada.minhabiblioteca.com.br/#/books/9788536518657/cfi/0!/4/4@0.00:0.00
Bibliografia Básica - Programação
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 7
Estruturas de Dados e Seus Algoritmos. Jayme Luiz
Szwarcfiter e Lilian Markenzon. Edição: 3|2010. Editora: LTC
Jayme Luiz Szwarcfiter. Teoria Computacional de
Grafos: Os Algoritmos. 2018. Editora GEN LTC; 1ª
edição (8 março 2018)
Bibliografia Básica – Notação e Complexidade
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 8
Algoritmos; CORMEN Thomas H.;
LEISERSON, Charles E.; RIVEST, Ronald L.;
STEIN, Clifford; Elsevier.
Projeto de Algoritmos | Nivio Ziviani | Apresentação (ufmg.br)
PROJETO DE ALGORITMOS COM IMPLEMENTAÇÕES EM 
PASCAL E C, 3ª ED. REV. E AMPL. NIVIO ZIVIANE, CENGAGE 
DO BRASIL, 2010
http://www2.dcc.ufmg.br/livros/algoritmos/
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
CONCEITOS EM TEORIA DOS GRAFOS
Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 10
𝑎2
𝑎1
𝑎3
𝑎4
Um grafo (graph) é um par de conjuntos:
• um conjunto de vértices
• um conjunto de arestas
Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 11
𝑎2
𝑎1
𝑎3
𝑎4
Um grafo (graph) é um par de conjuntos:
• um conjunto de vértices
• um conjunto de arestas
Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 12
𝑎2
𝑎1
𝑎3
𝑎4
Um grafo (graph) é um par de conjuntos:
• um conjunto de vértices
• um conjunto de arestas
Teoria dos Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 13
Um grafo pode conter:
𝑎2
𝑎1
𝑎3
𝑎4
Arestas 
direcionadas
Teoria dos Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 14
Um grafo pode conter:
𝑎2
𝑎1
𝑎3
𝑎4
Arestas 
direcionadas
Vértices com pesos 
associados
𝑎2
𝑎1
𝑎3
𝑎4
23
8
10
2
Teoria dos Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 15
Um grafo pode conter:
𝑎2
𝑎1
𝑎3
𝑎4
Arestas 
direcionadas
Vértices com pesos 
associados
𝑎2
𝑎1
𝑎3
𝑎4
23
8
10
2
Arestas com pesos 
associados
𝑎2
𝑎1
𝑎3
𝑎4
4
-1
0
2
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 16
A Abstração que permite codificar relacionamentos entre pares 
de objetos:
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 17
Exemplo 1: Nível de Iteração de usuários em redes sociais:
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 18
Exemplo 2: Hiperlinks de Páginas Web:
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 19
Exemplo 3: Modelagem de jogos - Sudoku
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 20
Exemplo 3: Modelagem de jogos - Labirinto
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 21
Exemplo 3: Modelagem de jogos - Labirinto
K
L
J
I
G
D
H
A
B
C
F
E
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 22
Exemplo 3: Modelagem de jogos - Labirinto
G
D
H
A B
C F JI
E
K L
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 23
Exemplo 4: Modelagem de jogos – Movimento do Cavalo no xadrez
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 24
Exemplo 5: Representar mapas
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 25
Exemplo 6: Problemas aplicáveis:
Robustez da malha de 
transmissão elétrica 
nacional.
Coloração eficiente de Mapas.
Alocação de canais em redes sem fio.
Grafos - Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 26
Praticando:
1) Sobre problemas modelados em grafos, responda aos questionários:
a) https://olimpiada.ic.unicamp.br/pratique/i1/2020/f2/mapa/
b) https://olimpiada.ic.unicamp.br/pratique/i1/2021/f3/grafo/
c) https://olimpiada.ic.unicamp.br/pratique/i1/2018/f2/grafo/
d) https://olimpiada.ic.unicamp.br/pratique/i1/2019/f1/automato/
https://olimpiada.ic.unicamp.br/pratique/i1/2020/f2/mapa/
https://olimpiada.ic.unicamp.br/pratique/i1/2021/f3/grafo/
https://olimpiada.ic.unicamp.br/pratique/i1/2018/f2/grafo/
https://olimpiada.ic.unicamp.br/pratique/i1/2019/f1/automato/
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 27
Grafos pequenos: Fáceis de visualizar
Grafos – Visualização Gráfica
Grafos – Visualização Gráfica
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 28
Grafos grandes: Difíceis de visualizar
Grafos – Visualização Gráfica
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 29
Grafos grandes: Difíceis de visualizar
Grafo com 400 
vértices e arestas 
aleatórias.
Fonte: irrigation_graph.png (605×465) (usp.br)
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/figs/large-graphs/irrigation_graph.png
Grafos – Visualização Gráfica
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 30
Grafos grandes: Difíceis de visualizar
Email. Ligações de 
email entre 
funcionários de uma 
corporação.
Fonte: kleinberg-easley-corporate-communication-adamic-hier.jpg (400×315) (usp.br)
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/figs/large-graphs/kleinberg-easley-corporate-communication-adamic-hier.jpg
Grafos – Visualização Gráfica
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 31
Grafos grandes: Difíceis de visualizar
Precisamos resolver esse problema de visualizar os grafos 
grandes. Como Vamos resolver?
Um profissional de computação deve ter habilidades que 
resolvam problemas de modelagens do mundo real, e isso 
inclui problemas modelados em grafos.
Grafos – Visualização Gráfica
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 32
Grafos grandes: Difíceis de visualizar
Precisamos resolver esse problema de visualizar os grafos 
grandes. Como Vamos resolver?
Temos duas (2) formas:
Provas de Teoremas em grafos
Algoritmos em Grafos (objetivo dessa disciplina)
Trabalhando com Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 33
Demonstração / Prova: Sequencia de afirmações precisas que
garantem que um dado resultado é verdadeiro.
Teorema: Uma afirmação em que há uma demonstração para ela.
Proposição:O mesmo que teorema, mas utilizado para resultados
simples.
Lema: Um resultado que é utilizado para provar resultados
maiores.
Corolário: Um teorema que é consequência de outro resultado.
Trabalhando com Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 34
Demonstração / Prova: Sequencia de afirmações precisas que
garantem que um dado resultado é verdadeiro.
Teorema: Uma afirmação em que há uma demonstração para ela.
Proposição: O mesmo que teorema, mas utilizado para resultados
simples.
Lema: Um resultado que é utilizado para provar resultados
maiores.
Corolário: Um teorema que é consequência de outro resultado.
Trabalhando com Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 35
Demonstração / Prova: Sequencia de afirmações precisas que
garantem que um dado resultado é verdadeiro.
Teorema: Uma afirmação em que há uma demonstração para ela.
Proposição: O mesmo que teorema, mas utilizado para resultados
simples.
Lema: Um resultado que é utilizado para provar resultados
maiores.
Corolário: Um teorema que é consequência de outro resultado.
Trabalhando com Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 36
Demonstração / Prova: Sequencia de afirmações precisas que
garantem que um dado resultado é verdadeiro.
Teorema: Uma afirmação em que há uma demonstração para ela.
Proposição: O mesmo que teorema, mas utilizado para resultados
simples.
Lema: Um resultado que é utilizado para provar resultados
maiores.
Corolário: Um teorema que é consequência de outro resultado.
Trabalhando com Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 37
Demonstração / Prova: Sequencia de afirmações precisas que
garantem que um dado resultado é verdadeiro.
Teorema: Uma afirmação em que há uma demonstração para ela.
Proposição: O mesmo que teorema, mas utilizado para resultados
simples.
Lema: Um resultado que é utilizado para provar resultados
maiores.
Corolário: Um teorema que é consequência de outro resultado.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 38
Dúvidas?
Bibliografia
• Manzano, José Augusto N. G. Programação de Computadores com C/C++.
Disponível em: Minha Biblioteca, Editora Saraiva,
2014.(https://integrada.minhabiblioteca.com.br/reader/books/978853651
9487/pageid/65)
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 39
Leitura Auxiliar
• Tutorial completo em C (em inglês): C Programming Tutorial
(markburgess.org)
https://integrada.minhabiblioteca.com.br/reader/books/9788536519487/pageid/65
http://markburgess.org/CTutorial/CTutorial.html