<<Resumo

RESUMO MACS

5- Modelos de Grafos.

Testes

Questões de Exame

 

 

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.

 

EXEMPLO : Grafo ponderado                                                  Página do livro: 32

1)         O que é um grafo ponderado?

 

Resolução:

 

 

EXEMPLO : Grafo completo.                                          Página do livro: 11

 

2) Desenhe um grafo completo de ordem 5.

Quantas arestas tem um grafo completo de ordem 6?

 

 

Resolução:

 

 

 

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

 

3) observe o grafo que se segue:

 

3.1) Indique o grau de cada um dos vértices.

 

3.2) este grafo Admite um circuito euleriano? se achar que sim, apresente-o. Se achar que não, justifique e apresente uma possível eulerização.

 

3.3) este grafo admite um circuito hamiltoniano? . Em caso afirmativo apresente um.

 

 

Resolução:

 

 

 

 

EXEMPLO

1)            Numa região existem 5 cidades que designamos pelas letras A, B, C, D, E. As ligações existentes entre estas cidades e as respectivas distâncias estão representadas no grafo abaixo:

 

 

1.1) Com base nos valores que estão neste grafo, complete os espaços em branco da seguinte tabela:

 

 

A

B

C

D

A

//////////////////

/////////////////////

/////////////////////

///////////////////

B

 

 

/////////////////////

////////////////////

///////////////////////

//////////////////////

///////////////////

 

C

 

 

 

////////////////////

////////////////////

/////////////////////

/////////////////////

D

 

 

 

 

/////////////////////

/////////////////////

E

 

 

 

 

 

1.            2)Suponha que pretende visitar todas estas cidades e voltar à cidade inicial, percorrendo a menor distância possível. Obtenha uma solução para a escolha do melhor trajecto, usando

 

1.2.1) o algoritmo dos mínimos sucessivos.

 

1.2.2) Algoritmo por ordenação dos pesos das arestas. 

 

1.2.3) o método das árvores, admitindo que pretendemos visitar em primeiro lugar a cidade A. Em segundo vamos para B ou para C. No final voltamos à cidade A.  

 

1.3)     Se o objectivo fosse ligar as cidades por um cabo de fibra óptica e as distâncias fossem as que estão no grafo indicado, qual seria a árvore abrangente mínima? Apresente a árvore e a respectiva distância.

 

1.4)     Será possível iniciar um percurso na cidade B, percorrer todas as estradas uma única vez e voltar à cidade B? Se acha que sim, justifique e apresente um percurso possível. Se acha que não, apresente uma justificação. 

 

 

 

Resolução:

 

 

 

 

EXEMPLO

4) Cinco localidades, que designaremos pelas letras A, B, C, D, E, estão ligadas entre si por diversas estradas. 

 

As estradas existentes e as respectivas distâncias são:

 

[AB] 7km,   [AE]  17km,   [BC]  10Km , [BD] 21Km,

 [CE] 8Km, [CD] 12 Km,   [ED] 33Km, [EB] 11Km. 

 

4.1) Representando as localidades por vértices e as estradas por arestas, represente as referidas ligações através de um grafo. Indique também os pesos das arestas.

 

4.2) Admita que a equipe de manutenção das estradas pretende inspeccionar o estado de conservação do asfalto e, para tal, precisa de passar por todas as estradas. Será possível começar e acabar em A, passando uma única vez em cada uma das estradas? justifique. Se achar que sim, indique um percurso possível. Se achar que não, apresente uma eulerização que repita o mínimo de arestas possível.

 

4.3) Suponha que um vendedor pretende visitar as cinco localidades, começando e acabando na mesma cidade, e procura o caminho mais curto possível. Ajude-o a encontrar a solução usando o método:

 

4.3.1) mínimos sucessivos. ( apresente todas as possibilidades).

 

4.3.2) ordenação dos pesos das arestas. Comece por apresentar todas as arestas ordenadas por ordem crescente de pesos. 

 

4.4) Suponha agora que o vendedor pretende visitar as cinco localidades mas já decidiu começar e terminar em  "A". Use o método das árvores para encontrar o caminho mais curto possível. Apresente todas as possibilidades de forma organizada e as respectivas distâncias.

 

4.5) Nesta mesma zona vai ser construída uma canalização para abastecimento de água e pretendemos planear a obra de modo a usar a menor quantidade possível de tubos. Admita que só pode construir tubagens de acordo com as ligações e as distâncias acima indicadas. Utilize o algoritmo de Kruskal para resolver o problema. Apresente a árvore abrangente mínima correspondente e o seu comprimento total. 

 

 

Resolução:

 

 

 

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:

 

Tarefas

Tempo ( minutos)

Dependências

T1

9

Nenhuma

T2

12

T1

T3

8

T1

T4

7

T1

T5

14

T3, T4

T6

12

T2, T3, T4

T7

13

T5, T6

T8

25

T6

T9

10

T7, T8

T10

10

T9

T11

9

T10, 

 

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.

 

 

Português

Matemática

IDES

História

Biologia

Psicologia

A

X

X

 

 

X

 

B

X

 

 

X

 

X

C

X

 

X

X

 

 

D

X

X

 

 

 

X

 

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: