Atividade: Crie um grafo
- Dê aos alunos um conjunto de pontos e peça que os conectem para criar um grafo.
- Peça-lhes para rotular cada ponto e cada aresta.
- Depois, peça-lhes para desenhar o grafo em um pedaço de papel ou no quadro.
Exercício: Encontre o caminho mais curto
- Dê aos alunos um grafo com alguns pontos e uma distância entre eles.
- Peça-lhes para encontrar o caminho mais curto entre dois pontos.
- Explique aos alunos que eles podem usar o algoritmo de Dijkstra para resolver o problema.
Jogo: Pegue o tesouro
- Crie um grafo com pontos aleatórios e rotule-os.
- Esconda um "tesouro" em um dos pontos do grafo.
- Divida a classe em equipes e peça que elas escolham um ponto para começar.
- A equipe deve seguir as arestas para encontrar o tesouro.
- A primeira equipe a encontrar o tesouro ganha.
Atividade: Construir um labirinto
- Divida a classe em equipes e peça que cada equipe crie um labirinto usando um grafo.
- Os labirintos devem ter um ponto de entrada e um ponto de saída.
- As equipes devem trocar seus labirintos com outra equipe para que elas possam tentar resolvê-los.
Exercício: Encontre o ciclo hamiltoniano
- Dê aos alunos um grafo e peça que encontrem um ciclo hamiltoniano.
- Explique-lhes que um ciclo hamiltoniano é um ciclo que passa por cada ponto do grafo exatamente uma vez.
- Peça-lhes que usem o algoritmo de Held-Karp para encontrar o ciclo.
Jogo: Crie um labirinto
- Dê aos alunos um grafo com alguns pontos.
- Escolha um aluno para criar um labirinto usando o grafo.
- Os outros alunos devem tentar resolver o labirinto.
- O aluno que criou o labirinto ganha se ninguém conseguir resolvê-lo em um determinado período de tempo.
Atividade: Colorindo grafos
- Dê aos alunos um grafo e peça-lhes para colori-lo usando o menor número possível de cores.
- Explique-lhes que isso é chamado de problema de coloração de grafos.
- Peça-lhes que usem o algoritmo de Welsh-Powell para resolver o problema.