|
Definir e caracterizar um circuito de Hamilton.
Identificar as condições para um grafo admitir um circuito hamiltoniano.
Para cada modelo, procurar esquemas combinatórios (árvores) que permitam calcular pesos totais de caminhos possíveis.
Encontrar algoritmos - decisões passo a passo para encontrar soluções.
Discutir sobre a utilidade e viabilidade económica (e não só) da procura de soluções ótimas.
Apresentar situações que sejam modeladas por grafos, em que o que interessa é visitar todos os vértices de preferência sem repetições e com partida e chegada do mesmo ponto (problema do caixeiro viajante).
Proporcionar situações de trabalho com “árvores” que visa facilitar as somas de pesos atribuídos às arestas de modo a ser possível comparar os pesos totais das várias soluções.
Incentivar a procura de algoritmos próprios para obter soluções aceitáveis.
Promover discussões que envolvam a otimização de recursos ou produtos, por exemplo, menor número de quilómetros, menor consumo de combustível, menos poluição, mais lucro ou preços mais baixos. As discussões devem enquadrar as variáveis relevantes como por exemplo a localização dos armazéns e dos clientes numa cadeia de distribuição comercial ou ainda a localização de unidades de tratamento de resíduos, aterros sanitários ou pontos de recolha
?? Kruskal?? árvores abrangentes?? (Dar?...)
|