Modelos de grafos

1

Introdução

Este trabalho realiza-se no âmbito da disciplina

de Matemática Aplicada às Ciências Sociais, de

acordo com as orientações da professora Teresa

Pisco, que nos foram transmitidas no início do

segundo período.

A sua temática diz respeito a uma matéria

abordada no primeiro período, os Modelos de grafos,

sendo o seu principal objectivo o de facilitar e tornar

mais interessante a consolidação destes conteúdos.

2

Introdução aos

grafos

Grafo é uma representação esquemática

constituída por conjuntos finitos de pontos,

usualmente representados por V (vértices ou nós),

e por segmentos, usualmente representados por A

(arestas ou arcos), que unem os pontos.

Grafo conexo é um grafo onde existe sempre uma

sequência de arestas a unir quaisquer dois dos seus

vértices.

3

Dígrafo (ou grafo orientado) é um grafo em que

as arestas têm orientações (sentidos) definidas.

Grafo completo é um grafo em que cada um dos

vértices é adjacente a todos os outros.

4

Trajetos e

circuitos

eulerianos

Grau (ou valência) de um vértice é o número de

arestas que nele concorrem.

Diz-se que um vértice tem grau par se nele

concorre um número par de arestas e que tem grau

ímpar no caso de esse número ser ímpar.

5

Passeio é uma sequência de vértices em que cada

dois vértices consecutivos estão ligados por uma

aresta, podendo haver repetição.

Trajeto (ou trilho) é um passeio em que as arestas

são todas distintas.

6

Caminho é um passeio em que os vértices são

todos distintos.

Circuito (ou ciclo) é um caminho que começa e

acaba no mesmo vértice (único que se pode

repetir).

7

Trajeto euleriano é um trajeto que percorre todas

as arestas de um grafo uma única vez.

8

Circuito euleriano (ou circuito de Euler) é um

trajeto euleriano que começa e acaba no mesmo

vértice.

Regra 1: Num grafo conexo, podemos encontrar

um trajeto euleriano se e só se existirem, no

máximo, dois vértices de grau ímpar.

Regra 2: Um grafo conexo admite um circuito

euleriano se e só se todos os vértices tiverem grau

par.

9

Problema do Carteiro Chinês

O Problema do Carteiro Chinês deve o seu nome

ao matemático Meigu Guan, que em 1962 levantou

este tipo de problemas eulerianos com base na

ideia de um carteiro a fazer a sua distribuição.

Exemplo:

As renas do Pai Natal precisam de uma hora de

descanso na noite do dia 24, mas entretanto o

trabalho não pode parar. No bairro das estrelinhas,

o Pai Natal terá de distribuir as prendas a pé o

mais rápido possível para poder pegar de novo no

seu trenó. As casas estão dispostas da seguinte

maneira:

10

C – Casas

T – Trenó

O Pai Natal tem de percorrer o menor número de

ruas que conseguir, tendo de passar por todas as

que tiverem casas duas vezes (uma em cada

passeio), e acabar e começar junto ao trenó.

O grafo adequado para este problema é o

seguinte:

Este grafo tem dois vértices de grau ímpar, logo

não seria possível efetuar um circuito de Euler. No

entanto, o percurso mais curto, em que o Pai Natal

só teria de percorrer duas vezes uma rua, é o

seguinte:

11

A B E B C D C B A F E D E F A

Eulerizar um grafo consiste em acrescentar-lhe

arestas, por forma a tornar possível encontrar um

circuito euleriano.

12

Regra: Para se adicionarem arestas de forma

correta é preciso que o número de repetições de

arestas seja igual ao número de arestas

acrescentadas.

Circuitos

hamiltonianos

Circuito hamiltoniano (ou circuito de Hamilton)

é um caminho que começa e acaba no mesmo

vértice percorrendo todos os vértices uma só vez

(exceto o primeiro que também é o último).

Um grafo diz-se hamiltoniano se nele se pode

encontrar, pelo menos, um circuito hamiltoniano.

13

Algoritmo dos mínimos sucessivos (ou

algoritmo do vizinho mais próximo)

1. Escolher um dos vértices para ponto de partida.

2. A partir desse vértice escolher a aresta com

menor peso possível (se houver mais que uma

escolhe-se aleatoriamente).

3. Continuar a construir o ciclo, a partir de cada

vértice para um vértice não visitado segundo a

aresta de menor peso.

4. Do último vértice não visitado regressar ao

ponto de partida.

14

Algoritmo por ordenação dos pesos das

arestas (ou algoritmo das arestas

classificadas)

1. Começar por escolher a aresta com menor

peso, qualquer que seja.

2. Escolher de seguida a aresta de menor peso

como anteriormente, e assim sucessivamente com

as seguintes restrições:

2.1. Não permitir que se formem ciclos que

não incluam todos os vértices;

2.2. Não permitir que 3 arestas, do ciclo que

estamos a procurar, se encontrem no mesmo

vértice.

Problema do Caixeiro Viajante

O problema do Caixeiro Viajante é aquele em que se

aplicam os circuitos de Hamilton. Os vértices são

pontos cujas ligações estão devidamente

valorizadas consoante a distância, custo, etc. O

objetivo é percorrer todos os pontos uma só vez e

terminar no ponto de partida.

15

Exemplo:

Estão todos de volta ao Pólo Norte, as prendinhas já

foram entregues! Os duendes estão descarregar o

trenó, com sacos vazios e prendas que sobraram

dos meninos mal comportados. “Oh não! Ainda aqui

está uma caixa!”. Abriram-na e descobriram que se

tinham esquecido de deixar um chocolate em cada

casa! E agora? Já é muito tarde, e os meninos não

podem abrir a prenda sem terem o seu bombom do

dia de Natal…

Trabalho para todos: cada um vai ter de ir a um país

entregar os bombons. Duendes, renas, fadinhas e o

Pai Natal, ninguém pode ficar de braços cruzados!

Coube ao Rodolfo distribuir os chocolates na Terra

Cor-de-Rosa, e aqui está o mapa que lhe deram,

com as casas a percorrer, as ruas e as distâncias em

metros:

16

 . Casas  _ Ruas

A B C D E

A - - - - -

B 30 - - - -

C 56 45 - - -

D 60 52 47 - -

E 50 62 69 48 -

- Rodolfo, toca a fazer contas!

Segundo o:

Algoritmo dos mínimos sucessivos:

17

Algoritmo por ordenação dos pesos das

arestas:

R: O percurso mais rápido para a rena é o

apresentado em ambas as soluções, que

corresponde a 220 metros.

18

Peso é um número que se atribui a cada uma das

arestas de um grafo. Pode representar distâncias,

custos, tempo, etc.

A um grafo com pesos atribuídos chamamos grafo

ponderado.

Árvore é um grafo conexo e sem circuitos.

19

Árvores

abrangentes

mínimas

Árvore abrangente (ou árvore geradora) é uma

árvore que contém todos os vértices de um grafo

dado.

Árvore abrangente mínima é uma árvore em que

a soma dos pesos das arestas é mínima.

20

Algoritmo de Kruskal: as arestas do grafo vão-se

unindo por ordem crescente dos pesos, desde que

não se formem circuitos e se garanta que no final

todos os vértices estão na árvore.

Caminho crítico é uma sequência de tarefas que

deve ser realizada no tempo previsto, de forma que

determinado trabalho ou projeto seja concretizado

dentro do prazo. A sua duração é aquela que

21

determina o menor tempo para a conclusão do

projeto e corresponde à maior duração global.

22

Aplicação a um exemplo real

Inicialmente, nós tencionávamos fazer um trabalho unicamente sobre um exemplo prático e, através dele, desenvolver todo o trabalho.

No entanto, após alguma reflexão sobre as espectativas de cada uma acerca do trabalho e também depois de sermos aconselhadas pela professora, decidimos que faríamos um trabalho mais teórico. Porém, não seria de todo este o motivo para o mesmo ser mais entediante e menos interessante, antes pelo contrário, e por isso, decidimos colocar o nosso exemplo prático, de modo a sermos mais bem sucedidas na apresentação do trabalho.

Com efeito, o nosso exemplo real, visível através da figura abaixo, era, fundamentalmente, o trajeto do camião do lixo na Nazaré, mais concretamente no Sítio da Nazaré.

23

Mas, sendo o nosso principal objetivo tornar este trajeto mais percetível e funcional para que qualquer um o compreenda e, uma vez que os grafos têm um carácter essencialmente prático, o nosso grupo criou, a partir da figura anterior, um grafo, representado na figura a seguir indicada.

Como vemos, a partir deste grafo, podemos perceber muito melhor o caminho percorrido pelo

24

camião do lixo, situação que, sem um grafo, seria mais dificilmente entendida, dado que, com todas as casas e ruas a volta, este é um pouco mais confuso.

25

Aplicações ao jogoA Teoria de Grafos é talvez, de entre as teorias

matemáticas, aquela que mais se pode usar com aplicações lúdicas, com o propósito de resolver ou compreender jogos. É uma teoria relativamente recente, nascida no século XVIII, e que entrou nos programas do ensino secundário no fim do século XX. Duas razões importantes para essa entrada: a grande aplicação prática mas também a possibilidade de introduzir os conceitos teóricos através de utilização de jogos.

Com efeito, vamos dar, a seguir, dois exemplos simples de aplicações de grafos.

Labirinto de Hampton

Um exemplo frequente de aplicação de grafos à resolução de jogos é o caso dos labirintos. O objetivo num labirinto costuma ser sair do labirinto. Então, no grafo, bastará encontrar um caminho que satisfaça esse objetivo. Um labirinto famoso encontra-se nos jardins do Palácio Real de Hampton, do qual temos uma vista aérea na figura seguinte.

26

Vamos definir um grafo onde os vértices representam determinadas posições do labirinto, um dos vértices será o ponto de partida e o ponto de chegada será a saída do labirinto. No esquema seguinte definimos a colocação dos vértices.

Somos, portanto, conduzidos ao grafo da figura seguinte, onde o vértice 14 é o ponto de partida e o vértice 1 é o ponto de chegada. Temos então de averiguar se existe um caminho desde o vértice 14 até ao vértice 1.

27

A existência do caminho pretendido é óbvia por observação da representação do grafo. Basta seguir a sequência de vértices: 14,12,11,10,8,6,4,2,1.

Desenhar sem levantar o lápis:

Na secção relativa às considerações históricas escrevemos sobre o problema das pontes de Königsberg, problema importante em termos históricos mas também um problema que retracta uma situação que nos é colocada frequentemente em alguns jogos, quando nos pedem para desenhar uma figura sem levantar o lápis do papel, passando uma única vez em cada linha.

De facto, conseguir efetuar tal desenho corresponde a determinar um atalho de Euler e portanto podemos usar a teoria apresentada para decidir por simples observação do desenho em que situações vai existir solução.

28

Suponhamos que pretendemos desenhar a figura abaixo:

Alguém inexperiente começará por efetuar várias tentativas e rapidamente começará a suspeitar da impossibilidade da tarefa que lhe foi proposta.

Este desenho é o que se obtêm no caso das pontes de Königsberg.

Na figura abaixo relembramos o esquema de Königsberg e as suas pontes.

29

A partir da figura com as pontes podemos desenhar um grafo usando as letras das regiões para identificar os vértices do grafo e as letras das pontes para identificar as arestas.

Na figura abaixo vemos o grafo originado.

Este grafo tem cinco vértices de grau ímpar, o vértice A com grau 5 e os restantes vértices com grau 3. Existem mais do que dois vértices de grau ímpar, logo, baseados na teoria apresentada, não será possível efetuar o desenho sem levantar o lápis do papel e passando uma única vez em cada linha.

30

Contudo, efetuando uma pequena alteração ao desenho, com a mudança da posição de um dos riscos, podemos agora efetuar o mesmo nas condições já referidas.

Note-se que, em termos de Königsberg, isto corresponderia a mudar a posição de uma das pontes. A ponte ‘e’ deixa de unir as regiões A e D e passa a unir as regiões B e C, obtendo este novo esquema:

31

O grafo obtido passa a ser o seguinte:

Vemos, neste momento, que não existem vértices de grau ímpar, logo, já é possível efetuar o desenho nas condições pedidas.

Na verdade, é até possível efetuar esse desenho acabando na posição onde se começou, como foi enunciado anteriormente.

32

Consideremos ainda mais duas figuras. Apesar de ser mais complexa, é possível desenhar a figura abaixo.

De facto, tendo apenas dois vértices de grau ímpar é possível efetuar o desenho desde que se comece em algum desses dois vértices.

Abaixo temos o grafo correspondente onde numerámos apenas os vértices, ignorando as arestas, por se tratar de um grafo simples.

33

Os vértices de grau ímpar são o 7 e o 10. Vamos começar no vértice 10 e acabar no vértice 7. O atalho pretendido é então:

10,7,11,12,16,15,12,8,7,3,2,6,10,11,15,14,10,9,14,13,9,5,1,2,5,6,7.

Na figura abaixo é indicado esse atalho através de setas sobre as arestas e um número em cada aresta indicando a ordem pela qual é percorrido o atalho.

34

Conclusão

Com este trabalho pudemos consolidar algumas noções acerca de Grafos e de alguns Modelos de Grafos, tais como: Trajetos e circuitos eulerianos, circuitos hamiltonianos e árvores abrangentes mínimas.

Além disso, tivemos não só a oportunidade de relembrar os problemas do carteiro chinês e do caixeiro viajante, bem como as melhores soluções para estes serem resolvidos, isto é, os melhores algoritmos a usar.

35

36