Aplicações de Grafos
na
Sala de Aula
Marília Pires
Departamento de Matemática
Universidade do Algarve
EVM07
Onde se ensina:
 Estados-Unidos (alguns estados)
 Holanda
 Portugal
EVM07
Porquê ensinar:
 Necessita de poucos conhecimentos de
outros temas de Matemática
 Representação gráfica intuitiva
 Estrutura o raciocínio
 Exemplos da vida quotidiana
 Entusiasma os alunos
 …
EVM07
A disciplina de Matemática
Aplicada às Ciências Sociais:
30 aulas de 90 minutos:




Circuitos de Euler
Circuitos de Hamilton
Árvores
Problemas Históricos
EVM07
Porquê só em MACS?
? Porque não desde o básico?
? O que se pode ensinar?
? Como ensinar?
? Quando?
? “Receitas mágicas”?
EVM07
RECEITA (não é mágica):








Exemplos
Exemplos
………
Exercícios
Exercícios
………
Problemas
Problemas
EVM07
Um bom exemplo:
 Conduz o aluno à construção do conceito
 Desperta o interesse
 Facilita a reflexão
 Induz a criatividade
 ...
EVM07
A manhã de folga da mãe da Joana
Casa  Finanças  Correio  Banco 
Farmácia  Sapateiro  Florista 
Livraria  Seguro  Emprego
EVM07
A manhã de folga da mãe da Joana…
CTT
Liv.
Fin.
Seg.
Emp.
Banco
Flo.
Casa
Far.
Sap.
Conceito: caminho
EVM07
A manhã de folga da mãe da Joana
Casa  Finanças  Correio  Banco 
Farmácia  Sapateiro  Florista  Livraria
 Seguro  Emprego
Mas será esta a melhor ordem para tratar de
tudo na mesma manhã?
EVM07
A manhã de folga da mãe da Joana…
CTT
300
500
Liv.
Seg.
500
200
Fin.
200
1500
Banco
750
Emp.
Flo.
1000
100
Casa
100
Far.
Sap.
Conceito: caminho mais curto passando por todos os vértices
EVM07
Caminho mais curto de S a A:
2
B
10
4
3
4
G
2
5
A
6
C
5
F
4
2
D
2
S
7
E
8
EVM07
Primeira estratégia:
1. Pedir aos alunos para fazerem uma lista de
todos os caminhos possíveis
2. Calcular o comprimento de cada caminho
3. Escolher o mais curto
•
Como saber que não esquecemos nenhum
caminho?
EVM07
Porque não ensinar um algoritmo?
•
•
•
•
Os alunos gostam de algoritmos
(Quase não se ensinam algoritmos!)
A aplicação de um algoritmo ajuda a
perceber melhor a essência do problema
“Certeza” de obter a solução
EVM07
Algoritmo de Dijkstra:
 Fácil perceber porque funciona
 Fácil de executar
 Eficiente para problemas pequenos
 Algoritmo exacto
EVM07
Algoritmo de Dijkstra:
Princípio do algoritmo:
O caminho mais curto entre dois vértices
contém os caminhos mais curtos entre todos
os vértices desse caminho
EVM07
Caminho mais curto de S a A:
2
B
10
4
3
4
G
2
5
A
6
C
5
F
4
2
D
2
S
7
E
8
EVM07
Algoritmo de Dijkstra:
Vértice
S
Distância
mínima
0
Distância
estimada
-
Antecedente
8
S
5
S
-
A
B
C
D
E
F
G
EVM07
Algoritmo de Dijkstra:
Vértice
S
Distância
mínima
0
Distância
estimada
-
Antecedente
8
S
5
S
-
A
B
C
D
E
F
G
EVM07
Algoritmo de Dijkstra:
Vértice
S
Distância
mínima
0
Distância
estimada
-
Antecedente
8
S
5
S
-
A
B
C
D
E
F
G
5
EVM07
2
B
10
4
3
4
(5)
G
2
5
A
6
C
5
F
4
2
D
2
S
7
E
8
(0)
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
11
G
E
87
SG
F
7
G
5
S
S
Distância
mínima
0
-
A
B
C
D
G
5
EVM07
Algoritmo de Dijkstra:
Vértice
S
Distância
mínima
0
Distância
estimada
-
Antecedente
11
G
87
SG
7
G
5
S
-
A
B
C
D
E
7
F
G
5
EVM07
2
B
10
4
3
4
(5)
G
2
5
A
6
C
5
F
4
2
D
2
S
7
E
(0)
8
(7)
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
C
11
G
D
14
E
87
SG
7
G
5
S
S
Distância
mínima
0
-
A
B
E
7
F
G
5
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
C
11
G
D
14
E
S
Distância
mínima
0
-
A
B
E
7
87
SG
F
7
7
G
G
5
5
S
EVM07
2
B
10
3
4
G
5
F
(7)
4
(5)
2
5
A
6
C
4
2
D
2
S
7
E
8
(0)
(7)
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
A
12
F
B
11
F
C
11 10
GF
D
14 9
EF
S
Distância
mínima
0
-
E
7
87
SG
F
7
7
G
G
5
5
S
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
A
12
F
B
11
F
C
11 10
GF
S
Distância
mínima
0
-
D
9
14 9
EF
E
7
87
SG
F
7
7
G
G
5
5
S
EVM07
2
B
10
3
4
G
5
F
(7)
4
(5)
2
5
A
6
C
4
2
D
(9)
2
S
7
E
8
(0)
(7)
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
A
12
F
B
11
F
C
11 10
GF
S
Distância
mínima
0
-
D
9
14 9
EF
E
7
87
SG
F
7
7
G
G
5
5
S
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
A
12
F
B
11
F
S
Distância
mínima
0
-
C
10
11 10
GF
D
9
14 9
EF
E
7
87
SG
F
7
7
G
G
5
5
S
EVM07
(10)
2
B
10
3
4
G
5
F
(7)
4
(5)
2
5
A
6
C
4
2
D
(9)
2
S
7
E
8
(0)
(7)
EVM07
Algoritmo de Dijkstra:
Vértice
S
Distância
mínima
0
A
Distância
estimada
-
Antecedente
12
F
-
B
11
11
F
C
10
11 10
GF
D
9
14 9
EF
E
7
87
SG
F
7
7
G
G
5
5
S
EVM07
(11)
(10)
2
B
10
3
4
G
5
F
(7)
4
(5)
2
5
A
6
C
4
2
D
(9)
2
S
7
E
8
(0)
(7)
EVM07
Algoritmo de Dijkstra:
Vértice
Distância
estimada
-
Antecedente
S
Distância
mínima
0
A
12
12
F
B
11
11
F
C
10
11 10
GF
D
9
14 9
EF
E
7
87
SG
F
7
7
G
G
5
5
S
-
EVM07
Algoritmo de Dijkstra:
Vértice
S
A
B
C
D
E
F
G
Distância
mínima
0
12
11
10
9
7
7
5
Distância
estimada
12
11
11 10
14 9
87
7
5
Antecedente
F
F
GF
EF
SG
G
S
SG FA
EVM07
2
B
10
4
3
4
G
2
5
A
6
C
5
F
4
2
D
2
S
7
E
8
EVM07
Problema do Carteiro Chinês:
Correio
Mei Ko Kwan (1962)
EVM07
Problema do Carteiro Chinês:
3
2
2
3
2
EVM07
Problema do Carteiro Chinês:
3 4
2
2
2
4
3
EVM07
Problema do Carteiro Chinês:
2
300
3
150
2
500
400
200
2
180
3
EVM07
Problema do Carteiro Chinês:
4
2
3
150
2
4
500
200
2
3
4
EVM07
Algoritmo de Fleury:
1. Escolher um vértice qualquer para começar;
2. Escolher uma qualquer aresta não marcada
incidente nesse vértice e marcá-la;
3. Repetir 2 até chegar a um vértice onde todas as
arestas estão marcadas
4. Se todas as arestas estão marcadas acabar
5. Escolher um vértice com uma aresta não
marcada e recomeçar
EVM07
Problema do Carteiro Chinês:
A
B
F
E
I
G
D
H
C
J
EVM07
Problema do Carteiro Chinês:
4
5 A
3
B
F
I
4
G
4
E
2
D
5
3
H
6
C
J
4
EVM07
Agrupamentos possíveis:
• AB  CD
• AC  BD
• A  D  B  C
EVM07
Problema do Carteiro Chinês:
3
A
6
1
B
3
1
1
F
4
2
E
2
I
3
2
2
G
3
D
H
2
4
3
4
C
1
1
J
5
EVM07
Caminhos mais curtos:
•
•
•
•
•
•
AB3
AC 4
AD4
BC6
BD4
CD4
(A  G  F  B)
(A  H  J  C)
(A  G  D)
(B  F  G  H  J  C)
(B  E  D)
(C  J  H  D)
EVM07
Custo de cada agrupamento:
• AB  CD3+4=7
• AC  BD4+4=8
• A  D  B  C  4 + 6 = 10
EVM07
Custo de cada agrupamento:
• AB  CD3+4=7
• AC  BD4+4=8
• A  D  B  C  4 + 6 = 10
EVM07
Problema do Carteiro Chinês:
3
A
6
1
B
3
1
1
F
4
2
E
2
I
3
2
2
G
3
D
H
2
4
3
4
C
1
1
J
5
EVM07
Problema do Caixeiro Viajante:
Visitar Castelos
A
A
-
B 100
B
C
D
100 10
30
-
40
40
-
100
C
10
40
D
30
40 100
-
EVM07
Problema do Caixeiro Viajante:
•
•
•
•
•
•
A  B  C  D  A  100 + 40 + 100 + 30 = 270
A  B  D  C  A  100 + 40 + 100 + 10 = 250
A  C  B  D  A  10 + 40 + 40 + 30 = 120
A  C  D  B  A  10 + 100 + 40 + 100 = 250
A  D  B  C  A  30 + 40 + 40 + 10 = 120
A  D  C  B  A  30 + 100 + 40 + 100 = 270
EVM07
Problema do Caixeiro Viajante:
•
•
•
•
•
•
A  B  C  D  A  100 + 40 + 100 + 30 = 270
A  B  D  C  A  100 + 40 + 100 + 10 = 250
A  C  B  D  A  10 + 40 + 40 + 30 = 120
A  C  D  B  A  10 + 100 + 40 + 100 = 250
A  D  B  C  A  30 + 40 + 40 + 10 = 120
A  D  C  B  A  30 + 100 + 40 + 100 = 270
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
Heurística de inserção do vizinho
mais próximo:
Construir o circuito escolhendo a aresta de
menor custo saindo do vértice em que se está.
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
B
100
40
40
30
D
A
100
10
C
EVM07
Problema do Caixeiro Viajante:
A
B
C
A
-
10
9
B
50
-
10
C
40
50
-
EVM07
B
10
50
10
50
A
9
40
C
EVM07
B
10
50
10
50
A
9
40
C
EVM07
B
10
50
10
50
A
9
40
C
EVM07
B
10
50
10
50
A
9
40
C
EVM07
B
10
50
10
50
A
9
40
C
A  C  B  A  9 + 50 + 50 = 109
EVM07
MAS:
B
10
50
10
50
A
9
40
C
A  C  B  A  9 + 50 + 50 = 109
A  B  C  A  10 + 10 + 40 = 60
EVM07
Um funcionário de uma empresa de parques de
estacionamento tem que percorrer todas as ruas onde
funciona estacionamento pago, para recolher o
dinheiro das máquinas, uma vez por dia. As
máquinas encontram-se a intervalos regulares ao
longo das ruas cujo mapa se desenha a seguir. Os
números sobre as arestas correspondem aos
comprimentos das ruas, em centenas de metros.
Determine o percurso a percorrer pelo funcionário,
de modo a minimizar o espaço percorrido.
EVM07
6
H
A
5
3
3
4
7
D
G
B
4
4
6
3
I
8
E
10
5
7
C
7
F
EVM07
6
H
A
5
3
3
4
7
D
G
B
4
4
6
3
I
8
E
10
5
7
C
7
F
EVM07
Agrupamentos possíveis:
• (B,C) + (D,H) → 9 + 7 =16
• (B,D) + (C,H) → 7 + 15 = 22
• (B,H) + (C,D) → 11 + 8 = 19
EVM07
Agrupamentos possíveis:
• (B,C) + (D,H) → 9 + 7 =16
• (B,D) + (C,H) → 7 + 15 = 22
• (B,H) + (C,D) → 11 + 8 = 19
EVM07
6
H
A
5
3
3
4
7
D
B
G
4
4
6
3
I
8
E
10
5
7
C
7
F
EVM07
a
b
g
f
Graphs: An Introductory approach
Wilson & Watkins
e
d
c
EVM07
c
d
g
e
f
a
b
Grafo de compatibilidades
EVM07
c
d
g
e
f
a
b
Encontrar subgrafos completos
cde abc gf
EVM07
c
d
g
e
f
a
b
Subgrafos completos
abf cde gf
EVM07
Alternativa 1: abc cde gf
c
d
b
a
g
e
0
20
f
40
60
Tempo de espera:
Total:
a, b, d, e, f, g : 40 segundos
260 segundos
c: 20 segundos
EVM07
Vamos escolher a roupa da Joana
A Joana leu numa revista de moda que não se deve misturar mais do
que 3 cores. Ela quer vestir-se de modo a que peças que se toquem
não tenham a mesma cor. Será possível?
EVM07
Sapatos
Meias
Saia
Cinto
Mala
Lenço
Blusa
Laços
EVM07
Sapatos
Meias
Saia
Cinto
Mala
Lenço
Blusa
Laços
EVM07
Expedição a Marte:
 10 candidatos
 Escolher duas tripulações
 Não pôr na mesma tripulação pessoas que não se
dão bem
Problemas divertidos de Teoria de Grafos
O.I. Melnikov – Minsk 2001
EVM07
Resultado dos testes psicológicos:
1
2
3
4 5
1
 *
*
*
2
* 
3
*
4
*
5
8

9 10
*

*

*
*

*
*
 *
*
*
*  *
*
9
10
8
*
6
7
6 7
*
*
* 
*
*

EVM07
2
8
5
9
1
7
3
4
6
10
EVM07
2
8
5
9
1
7
3
4
6
10
EVM07
Bactérias:
Há uma bactéria que se divide inicialmente
em 3. As bactérias seguintes ou não se
dividem ou se dividem em 2 ou em 4.
Observa-se a cultura e há 102 bactérias.
Quais os números máximos e mínimos de
divisões em 4 e em 2 bactérias?
EVM07
Só as bactérias representadas a castanho serão observadas
EVM07
Nó inicial: grau 3
Nós finais: grau 1
Nós intermédios: grau 3 ou grau 5
1 vértice de grau 3
k vértices de grau 3
número de vértices:
1 + k + p + 102
p vértices de grau 5
102 vértices de grau 1

soma dos graus dos vértices:
3 + 3k + 5p + 102
número de arestas:
k + p + 102
EVM07
Lema dos apertos de mão:
A soma dos graus dos vértices é o dobro do número de arestas
3 + 3k + 5p + 102 = 2  ( k + p + 102 )

k + 3p = 99
k = 0  p = 33
k = 99  p = 0

0 divisões em 2 e 33 em 4
99 divisões em 2 e 0 em 4
EVM07
Arquitectura: elaboração de plantas
• Entrada principal – ligação ao hall
• Entrada pelo jardim
• Hall – ligado a escritório, sala de estar, sala
de jantar e escada
• Escritório perto de WC
• Sala de jantar ligada à zona de serviço
(cozinha, copa, wc serviço, lavandaria)
• Zona de serviço com acesso directo à
entrada
EVM07
jantar
escritório
hall
estar
WC
entrada
lavagens
cozinha
copa
jardim
wc
EVM07
WC
escritório
Sala de estar
wc
hall
jardim
sala de jantar
lavagens
copa
cozinha
entrada
EVM07
Espaço de manobra ilimitado
Exemplos devem requerer trabalho
intelectual
EVM07