RESUMO MACS
5- Modelos de Grafos.
|
ASSUNTO: Grafos- Introdução |
Livro: TEXTO 11 páginas: 8 |
||||||||
|
|
|
||||||||
|
Um grafo G é um par (V, A), em que V é o conjunto de vértices e A o conjunto de arestas.
Uma aresta liga um vértice a outro ou a ele próprio.
Ordem de um grafo:Representa o número de vértices de um grafo. Um grafo é conexo quando qualquer vértice está ligado por uma aresta ou por uma sequência de arestas a qualquer um dos outros vértices do grafo. .
Grafo completo: Grafo em que quaisquer dois dos seus vértices são adjacentes, isto é, há pelo menos uma aresta para cada par dos seus vértices.
Grau( ou valência) de um vértice: Número de arestas que começam (ou terminam) nesse vértice.
|
|||||||||
|
|||||||||
|
ASSUNTO: Grafos EULERIANOS Grafos HAMILTONIANOS |
Livro: TEXTO 11 páginas: 12/ 26 |
||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||
|
Grafos de Euler
Circuito: Caminho que começa e acaba no mesmo vértice.
Circuito de Euler: Circuito que passa uma e uma única vez em cada aresta do grafo.
Um caminho de Euler é um caminho que passa uma e única vez em cada aresta. O grafo tem que ser conexo e só pode ter dois vértices de grau ímpar: o início e o fim.
Se o grafo for euleriano, isto é, admitir um circuito de Euler, então é possível percorrer todas as arestas de uma só vez sem repetir qualquer aresta do grafo, começando e terminando no mesmo vértice.
Uma condição necessária e suficiente para que um grafo seja euleriano é ser conexo e todos os seus vértices serem de grau par (Teorema de Euler);
Se o grafo admitir um caminho de euler, então também é possível percorrer todas as arestas de uma só vez sem repetir qualquer aresta, começando num vértice de grau ímpar e terminando noutro vértice de grau impar.
Eulerização de grafos. Processo que consiste em acrescentar arestas, por duplicação das já existentes, para que o grafo resultante seja euleriano, isto é, para que o grafo resultante seja conexo e tenha só vértices de grau par.
Circuito de Hamilton Caminho que começa e acaba no mesmo vértice, passando por todos os vértices e não mais que uma vez por cada um deles.
O problema do caixeiro-viajante.
“Admita que um caixeiro-viajante pretende visitar n cidades diferentes iniciando e terminando a sua viagem numa das cidades. Suponha, também, que não importa a ordem com que as cidades são visitadas e de cada uma delas se pode ir directamente a qualquer outra. O problema do caixeiro viajante consiste em descobrir o percurso que torna mínima a distância total da viagem visitando cada cidade uma só vez.” Método das árvores, árvore. ( desenhamos a árvore)
1º) Encontrar todos os circuitos de hamilton possíveis (a partir de um determinado vértice); 2º) Adicionar os pesos das arestas utilizadas em cada um dos circuitos;
3º) Escolher o circuito para o qual a soma dos pesos das arestas percorridas é menor.
Algoritmo dos mínimos sucessivos.
1º) Definimos a cidade (vértice ) de partida. 2º) Seleccionamos a cidade mais próxima tal que: • Se houver duas à mesma distância escolhemos aleatoriamente; • Não podemos repetir nenhuma cidade exceto a última, depois de terem sido todas visitadas, voltando ao ponto de partida.
Algoritmo da ordenação do peso das arestas. 1º) Ordenam-se as arestas pelos seus pesos; 2º) Seleccionam-se sucessivamente as arestas com menor peso, tal que:
• Um vértice nunca poderá aparecer três vezes; • Nunca se fecha um circuito havendo vértices por visitar
3º) Ordena-se a solução conforme o vértice de partida escolhido.
Nota: Os algoritmos “cidade mais próxima” e “peso das arestas” não garantem encontrar o circuito hamiltoniano mínimo (o ótimo), garantindo apenas encontrar um dos melhores. Mesmo não obtendo o circuito ótimo, a aplicabilidade destes dois algoritmos é fácil, rápida e rentável.
Com o algoritmo das árvores, ” encontra-se o circuito hamiltoniano mínimo, pois experimentamos todas as possibilidades mas, ao contrário dos outros é de aplicabilidade difícil e moroso, sendo mesmo impossível, na maioria dos casos, de aplicá-lo sem recorrer aos computadores.
Árvores abrangentes mínimas.
Árvores são grafos conexos que não têm circuitos.
Uma árvore que contenha todos os vértices de um grafo chama-se árvore abrangente ou árvore geradora desse grafo.
Uma árvore abrangente mínima de um grafo pesado é uma árvore abrangente com custo mínimo.
Algoritmo de Kruskal para encontrar a árvore abrangente mínima: 1º) Escolhem-se as duas arestas com o menor peso;
2º) Escolhe-se a aresta seguinte com o menor peso, desde que esta não feche um caminho;
3º) Repete-se o ponto anterior até que todos os vértices façam parte da árvore;
4º) Se houver empate na escolha de arestas, seleciona-se aleatoriamente.
Nota: a aplicação do algoritmo de Kruskal garante-nos que a árvore abrangente encontrada é a mínima.
|
|||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||
|
EXEMPLO : Caminhos Crítico Página do livro: 48
|
|
6) Para a execução de um determinado projecto, são necessárias 10 tarefas.
Sabemos que a tarefa T10 demora 16 dias e depende das tarefas T5 e T7.
A Tarefa T5, assim como as Tarefas T1, T2, T4 e T6 demoram, cada uma, 12 dias.
A tarefa T2 depende de T1. A tarefa T3 depende de T2 e demora 11 dias.
A tarefa T5 depende da tarefa T3. A tarefa T9 demora 6 dias e depende das tarefas T4 e T6. A tarefa T8 depende da tarefa T9 e demora 7 dias.
A Tarefa T7 depende da tarefa T8 e demora 17 dias.
As tarefas T1, T4 e T6 não têm qualquer dependência.
6.1) Apresente uma tabela em que na primeira coluna coloque as tarefas T1 a T10, na segunda coluna indique a duração (em dias) e na terceira coluna indique as dependências de cada uma.
6.2) Apresente o digrafo correspondente.
6.3) Ao fim de quanto tempo terá concluídas as seguinte tarefas: T1? T2? T3? T4? T5? T6? T7? T8? T9? T10?
6.4) Determine o tempo mínimo necessário para concluir o projecto.
|
|
Resolução: |
|
|
|
EXEMPLO |
||||||||||||||||||||||||||||||||||||
|
3) A tabela seguinte representa as tarefas a realizar para ser cumprido um determinado projecto:
3.1) Desenha o grafo
que represente a situação.
3.2) Ao fim de quanto tempo estarão concluídas as seguintes tarefas: T1? T2? T3? T4? T5? T6? T7? T8? T9? T10? T11?
3.3) Determina tempo mínimo necessário para concluir o projecto.
|
||||||||||||||||||||||||||||||||||||
|
Resolução: |
||||||||||||||||||||||||||||||||||||
|
|
|
EXEMPLO |
|
2)
Numa escola existem 10 turmas ( T1, T2, T3, T4, T5, T6, T7, T8, T9, T10) e 7 professores (A, B, C, D, E, F, G). 3) Cada professor tem as seguintes turmas:
Professor: / Turmas A à 1, 2, 3 Bà 5, 6, 4 Cà 7, 8, 9 Dà 2, 1, 10 Eà 6, 4, 2 Fà 8, 10, 3 G à 9, 5, 7
Pretendemos fazer reuniões com todas as turmas de modo que cada professor não tenha mais do que uma reunião por dia.
Indique o número mínimo de dias para efectuar as reuniões de todas as turmas indicando em cada dia quais as turmas que têm reunião.
|
|
Resolução: |
|
|
|
EXEMPLO |
|||||||||||||||||||||||||||||||||||
|
5) Uma comissão de exames nacionais pretende calendarizar os exames, de modo que os alunos não tenham dois exames no mesmo dia. A tabela que se segue mostra os exames que os alunos A, B, C e D têm de realizar.
5.1) Desenha um grafo que sirva de modelo à informação disponível.
5.2) Considerando que cada aluno não pode fazer mais do que um exame por dia, diz qual é o número mínimo de dias necessários para a realização dos exames e apresenta a distribuição dos exames pelos vários dias.
|
|||||||||||||||||||||||||||||||||||
|
Resolução: |
|||||||||||||||||||||||||||||||||||
|
|
