Upload
ana-petinga
View
29
Download
1
Embed Size (px)
Citation preview
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