Want to create interactive content? It’s easy in Genially!

Get started free

Trabalho de Macs- grafos

Gabriela Silva

Created on October 29, 2022

Start designing with a free template

Discover more than 1500 professional designs like these:

Psychedelic Presentation

Chalkboard Presentation

Witchcraft Presentation

Sketchbook Presentation

Genial Storytale Presentation

Vaporwave presentation

Animated Sketch Presentation

Explore all templates

Transcript

MACS-11ºAno

Eularizar um grafo

Trabalho realizado por: Gabriela Silva 11ºD.Salomé Lopes 11ºD.

1. O que é eulerização de grafos?

índice

8. 4º exercício e resolução

2. 1º exercício e resolução

9. Eulerização de grelhas não retangulares

3. 2ºexercício e resolução

4. Melhor eulerização

10. 5º exercício e resolução

5. 3ºexercício e resolução

6. Eulerização de grafos-grelha

11. Sites usados

7. Exemplo de grafos-grelha

O que é Euleriação de grafos?

É um processo que consiste em acrescentar arestas, por duplicação das já existentes, para que o grafo resultante seja euleriano.

1º exercício

Resolução:

2º exercício

Resolução:

UMa melhor eulerização

Na maior parte dos casos há a possibilidade de se fazer mais do que uma eulerização do grafo. Chama-se melhor eulerização àquela que acrescenta o número mínimo de arestas. Pode haver mais do que uma "melhor eulerização".

3º exercício

Qual é a melhor eulerização do seguinte grafo?

Resolução:

Eulerização de grafos-grelha

1º percorrer o grafo, andando à volta do retângulo2º quando se encontra um vértice de grau ímpar, liga-se ao próximo vértice duplicando a aresta 3º se o vértice que foi ligado ficar com grau par, continua-se a percorrer o retãngulo até encontrar um vértice de grau ímpar 4º quando se encontra um novo vértice de grau ímpar, acrescenta-se uma nova aresta, ligando ao vértice seguinte 5º continua-se este percurso sucessivamente, até o grafo estar eulerizado

Exemplos de grafos-grelha

4º exercício

Resolução:

Eulerização de grelhas não retangulares

1º Localizar os vértices de grau ímpar2º Formar pares com esses vértices 3º Se for preciso, reorganizar os pares para que haja uma melhor eulerização, ou seja, que a soma do número de arestas seja mínima

5º exercício

Resolução:

Sites utilizados:

https://pt.scribd.com/document/446385996/MACS-Teste3-11ano-01-2020 https://cf0f0185-cf1a-493c-8cab-420d8273bb76.filesusr.com/ugd/5831f3_ed216d375e0c48f4949ddd50cb63ee34.pdf https://cf0f0185-cf1a-493c-8cab-420d8273bb76.filesusr.com/ugd/5831f3_1a43257cb97343f79a5b6ada18128605.pdf https://cf0f0185-cf1a-493c-8cab-420d8273bb76.filesusr.com/ugd/5831f3_fc004ef115704269ae6ebeb1c84a2a86.pdf https://pedronoia.net/TX11/Tr1T41.pdf Manual de MACS