MACS

Exemplos:

O principal objetivo de Euler ao criar este modelo matemático foi com o intuito de conseguir passar em todas as arestas do grafo sem repetir nenhuma e, voltar ao mesmo vértice. Algumas definições são então: só é grafo de euler se e só se o grafo for conexo e se tiver todos os vértices com grau par.CIRCUITO EULER:circuito que passa uma única vez em cada aresta e volta ao mesmo vértice onde teve ínicio. CAMINHO DE EULER:só é caminho de euler quando o grafo é conexo e quando tem no máximo dois vértices com grau ímpar. (nota: tem que ter ínicio e fim num dos vértices com grau ímpar.

grafo conexo e com todos os vértices de grau par, logo,é um grafo de euler.

Leonhard Euler

+ info

o grafo não é conexo e tem dois vértices com grau ímpar, sendo assim vamos ter que eulerizar este grafo. Ou seja,vamos ter que adicionar uma aresta ou mais para que os vértices de grau ímpar fiquem com grau par. Neste caso adicionaríamos uma aresta em AB.

Trabalho realizado por Marta Falcão no âmbito da disciplina de macs

Escola básica e secundária dom martinho vaz de castelo branco

livro: manual macs máximo 11º ano

Problema do caixeiro viajante:consiste em encontrar um circuito hamiltoniano com ínicio num dos vértices e com menor tempo possível. Algoritmo da cidade mais próxima:o objetivo deste método é encontrar um caminho que percorras todas as cidades com menor kms possíveis e volta a cidade onde teve ínicio,e se possível evitar a repetição de cidades. Algoritmo do peso das arestas:neste método escolhe-se o circuito com arestas menos pesadas,sem repetir nenhum vértices 3 vezes,sem fechar o circuito e só se pode visitar uma vez cada cidade

O objetivo de hamilton ao contrário de euler, era percorrer todos os locais,porém,nao precisava que passar em todas as arestas mas sim em todos os vértices. Vamos passar então as definições deste tipo de grafos: Circuito de hamilton:circuito que começa e acaba no mesmo vértice porém nao pode passar mais do que uma vez no mesmo vértice

William Hamilton

(exemplo de um grafo hamiltoniano)

Dentro dos grafos de hamilton temos mais 3 métodos.

livro: manual macs máximo 11ºano