Grafos orientados e problemas resolvidos com grafos
Lê grafos orientados, conta apertos de mão e jogos de um campeonato e descobre o percurso mais curto transformando o problema num grafo.
📖 Começa aqui: lê os passos da «Lição» por ordem (1, 2, 3 …) e responde a cada pergunta. Depois continua com «Praticar».
- Rússia: 7.º ano
Guia
Os grafos não fazem parte do programa de Matemática do ensino básico em Portugal; este estúdio é uma extensão. Um grafo é um modelo útil: os vértices são pessoas, terras ou equipas e as arestas são relações (amizade, estradas, jogos). Se a relação tem sentido («A ultrapassou B»), a aresta desenha-se com uma seta: é um grafo orientado. Cada vértice tem então um número de setas que saem e um de setas que chegam.
Problemas clássicos: apertos de mão num grupo de n pessoas (cada uma com cada uma, uma só vez) e jogos de um campeonato (cada equipa joga com todas as outras). A soma dos graus é o dobro do número de arestas, por isso as arestas são metade da soma dos graus; com n vértices todos ligados obtém-se n·(n − 1) : 2.
Um erro frequente é contar cada aresta duas vezes. Outro é confundir as setas que saem com as que chegam. Um problema de percurso resolve-se contando as arestas da cadeia mais curta.