GRAFOS
Observe as figuras que seguem e conclua se é possível encontrar um
caminho passando por todos os pontos sem tirar o lápis do papel.
 Vértices e arestas.
 Vértices adjacentes.
 Aresta incidente ao vértice.
 Laços.
 Arestas paralelas.
Caminhos Eulerianos
São caminhos que utilizam cada aresta uma e somente
uma vez num grafo.
Podem ser:
 Fechados: começam em um vértice e terminam no
mesmo.
 Abertos: começam e terminam em vértices diferentes.
Teorema
 Um grafo conexo G = (V,A) admite caminho Euleriano
se, e somente se, todas arestas tiverem grau par, ou
apenas duas tiverem grau ímpar.
Grau do vértice
 Chamamos de grau de um vértice o número de arestas
com extremidades nesse vértice. Laço contribui duas
unidades para o grau do vértice sobre o qual ele é
incidente.
Grau do Grafo
A soma dos graus dos vértices do grafo é
chamado grau do grafo.
Matriz de incidência
 Def: são matrizes nas quais as linhas estão associadas
aos vértices e as colunas estão associadas às arestas.
Um elemento da linha i e coluna j é 1 se a aresta j é
incidente ao vértice i e 0 caso contrário.
Matrizes de adjacência
 Def: são matrizes nas quais as linhas e as colunas estão
associadas aos vértices. O elemento da linha i e coluna
j é o número de arestas que têm i e j como
extremidades.
Atividade
Dividam-se em dois grupos. Dirijam-se ao seu “bairro” (definido pelas professoras).
As professoras entregarão 5 etiquetas para cada grupo. Em uma etiqueta
escrevam a palavra casa e colem em uma das casinhas (onde escolherem). A
cada uma das outras etiquetas atribuam lugares que o grupo gostaria de visitar
em seu “bairro”, e as colem em casas dentro do mesmo. Entretanto, não poderão
haver locais a serem visitados na mesma “quadra” da casa do grupo.
1) Supondo casa como local A, e os demais locais como B, C, D, e E, façam os
caminhos ABCDEA, ABCEDA, ABDCEA, ABDECA e ACBDEA. Algum destes foi o
caminho mais curto para, partindo de casa, percorrer todos os locais
escolhidos pelo grupo para visitar? Se não foi, qual seria o melhor caminho?
Desenhe pelo menos três dos caminhos percorridos através de grafos, um
destes deverá ser o melhor caminho. Leve em consideração o fato de que há
diversas maneiras de se ir de um ponto A a um ponto B. Lembre-se, você está
se movimentando em um bairro, não poderás “invadir” casas para traçar seu
caminho.
2) Todos estes caminhos são eulerianos? Por quê?
3) Construa as matrizes de incidência e adjacência do caminho mais curto a ser
percorrido.
Créditos
Produção:
Isabel Helena Comerlato
Maria Eduarda Hojnacki Costa
Referências
MALTA, Gláucia Helena Sarmento. Grafos no Ensino Médio –
Uma Inserção Possível. Dissertação (Mestrado em Ensino de
Matemática) – Programa de Pós-Graduação em Ensino de
Matemática, UFRGS, Porto Alegre, 2008. Disponível em
http://www.lume.ufrgs.br/bitstream/handle/10183/14829/00066
8628.pdf?sequence=1 . Acesso em: 17 de ago. 2015.