Matemática Discreta · IFC São Bento do Sul
Uma vila de gatos entre telhados, becos e muros. Cada lugar é um vértice, cada passagem é uma aresta e cada aresta tem um peso. Com funções e o algoritmo de Dijkstra, descobrimos a rota mais barata entre dois pontos e explicamos por que ela vence.
Parte 1 · Teoria
Explicamos cada conceito com nossas palavras e já mostramos onde ele aparece na Vila dos Miados. As verificações abaixo são calculadas a partir dos próprios dados do grafo.
Uma relação entre dois conjuntos é só uma forma de dizer quais pares combinam. Formalmente, é um subconjunto do produto cartesiano: R ⊆ V × V. Não precisa ter número, nem regra de cálculo: basta decidir, para cada par, se ele está ou não na relação.
Na vila usamos a relação de adjacência: dois lugares estão relacionados quando existe uma passagem direta entre eles.
Uma função é uma relação com uma exigência a mais: cada elemento do domínio tem exatamente uma saída. Se a mesma entrada pudesse dar dois resultados, não seria função.
No grafo, a função de peso recebe uma aresta e devolve o custo de atravessá-la. Toda aresta tem um único peso, então é função. Mas arestas diferentes podem ter o mesmo peso, então ela não é injetora.
Um grafo junta dois conjuntos: vértices (os pontos) e arestas (as ligações). Quando cada aresta tem um número, o grafo é ponderado. Se a ligação vale nos dois sentidos, ele é não direcionado.
Um caminho é uma sequência de vértices ligados por arestas, e o seu custo é a soma dos pesos. O grafo não é um mapa em escala: só importa quem se liga com quem, e com qual peso.
É um algoritmo guloso para achar o menor custo a partir de uma origem. Ele mantém uma distância provisória para cada lugar e, a cada rodada, fecha o lugar não visitado mais barato, usando-o para tentar baratear os vizinhos (isso se chama relaxar uma aresta).
Ele só é correto com pesos não negativos: se nenhum trecho pode diminuir o custo, quem foi fechado com o menor valor nunca mais será superado.
Parte 2 · Modelagem
A vila é um grafo ponderado e não direcionado. Os pesos medem uma mistura de tempo, esforço e risco: quanto maior, pior para o gato. Passe o mouse (ou toque) num lugar para ver seus vizinhos.
Escolha um lugar para ver N(v), o conjunto de vizinhos, e o grau.
| Aresta | Lugares | w(e) | tipo(e) |
|---|
Cada célula mostra w({a, b}), ou fica vazia se a e b não se relacionam. A matriz é igual à sua transposta (A = Aᵀ): essa é a simetria da relação vista de outro jeito. A diagonal vazia mostra que a relação não é reflexiva.
Parte 3 · Nosso enfoque
Sem funções, o grafo é só um desenho de pontos e linhas. Com elas, cada elemento ganha um significado que dá para ler e comparar. Estas são as funções que usamos para interpretar os resultados.
w : E → ℕ
Diz quanto custa atravessar cada passagem. É a função que o Dijkstra minimiza.
tipo : E → T
Classifica o trecho como rápido, seguro, comum ou arriscado. Não entra na conta do Dijkstra, mas explica o custo e ajuda a escolher quando há empate.
grau : V → ℕ
Conta quantas passagens saem de cada lugar, ou seja, grau(v) = |N(v)|. Lugares de grau alto são "entroncamentos" da vila.
custo(v₀ … vₖ) = Σ w({vᵢ, vᵢ₊₁})
Leva um caminho a um número: a soma dos pesos das arestas usadas. É ela que permite comparar rotas com quantidades diferentes de trechos.
Menos trechos não quer dizer menor custo: custo(M, C, F) = 8 + 9 = 17 usa só 2 arestas e sai mais caro.
dₛ : V → ℕ ∪ {∞} e antₛ : V → V ∪ {nulo}
Fixada uma origem s, o algoritmo constrói duas funções: dₛ(v), o menor custo de s até v, e antₛ(v), o lugar que vem logo antes de v na melhor rota encontrada. O caminho é reconstruído aplicando antₛ várias vezes a partir do destino: F → ant(F) = P → ant(P) = B → ant(B) = M.
Um ponto importante para interpretar os testes: dₛ é sempre uma função (cada lugar tem um único menor custo), mas "ser um caminho mínimo" não é função do par origem–destino. Quando há empate, o mesmo par tem dois caminhos mínimos diferentes, e isso é uma relação, não uma função.
Parte 4 · Implementação
Escolha origem e destino e avance passo a passo. A vila 3D, o grafo 2D, a tabela e o código mostram o mesmo estado ao mesmo tempo. No fim, o gato percorre o menor caminho.
arraste para girar · botão direito ou Shift para mover
Escolha origem e destino e aperte Executar.
Parte 5 · Testes e análise
Os resultados abaixo não foram digitados à mão: são gerados pela
mesma função dijkstra() do arquivo
dijkstra.js. Para conferir, listamos
também todas as rotas alternativas (caminhos simples) e seus
custos.
Parte 6 · Apresentação
A ordem que vamos seguir em sala, com onde cada critério da avaliação aparece nesta página.
A Vila dos Miados e o que os pesos medem.
InícioRelações, funções, grafos e Dijkstra com nossas palavras.
Teoria · 35%V, E, w, tipo, matriz de adjacência e a simetria.
Modelagem · 25%w, tipo, grau, custo, d e ant: o foco do nosso grupo.
FunçõesExecução passo a passo e o código comentado.
Implementação · 20%M → F, T → F e J → P, empates e interpretação.
Análise · 20%Matemática Discreta
Professora Wilcilene Maria Kowal
Instituto Federal Catarinense · Campus São Bento do Sul