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

Over 30 million people build interactive content in Genially.

Check out what others have designed:

Transcript

MACS|11º ano

Modelos de Grafos

Muitas vezes, para resolvermos uma determinada situação problemática, temos tendência a fazer um esquema, ou um modelo, que nos facilite a organização das ideias. Com base nestes modelos, conseguimos visualizar melhor qual é a solução para o nosso problema ou definir uma estratégia para o resolver.Os grafos aparecem-nos como esquemas/modelos onde se utilizam pontos e linhas a ligar os pontos que se relacionam de alguma forma.Vamos analisar alguns desafios, que, apesar de serem muito distintos, podem ser resolvidos com a ajuda da teoria dos grafos.

INFO

A figura representa a rede do Metropolitano de Lisboa. Um diagrama como o seguinte dá-nos uma imagem global das zonas da cidade que comunicam por metro. 1.1 Se estiveres na estação do Oriente e quiseres ir para a Avenida, de quantas maneiras diferentes poderás fazê-lo? Como?

Atividade 1

INFO

1.2 Considera agora apenas as estações terminais de cada uma das linhas. Odivelas Telheiras Oriente Amadora Alameda Baixa-Chiado Cais do Sodré Rato Quantas linhas teriam de ser construidas para que cada estação terminal estivesse diretamente ligada a qualquer uma das outras?

INFO

Grafo Representativo do problema

Num condomínio fechado há vários contentores destinados à recolha do lixo indiferenciado de origem doméstica. Tendo em conta a figura, será possível um percurso de recolha que passe uma única vez por cada contentor?

Atividade 2

INFO

Grafo Representativo do problema

Na antiga cidade de Königsberg situada na Prússia, hoje Kaliningrad na Rússia, existe uma ilha, chamada Kneiphoff, formada pelos dois braços do rio Pregel. Há sete pontes que atravessam esses dois braços.Averigua se é possível uma pessoa deslocar-se na cidade de tal forma que atravesse cada uma das sete pontes uma e uma só vez.

Atividade 3

O problema apresentado na atividade 3 está na base do aparecimento da Teoria dos grafos. “ A teoria dos grafos foi explorada há mais de 200 anos, quando o matemático suíço Leonhard Euler (1736-1783) utilizou um grafo para resolver o problema que diz respeito a percorrer as sete pontes de Königsberg. Esta questão foi encarada como pouco mais do que um problema específico da Matemática, até que, com o aparecimento dos computadores se alargou a aplicação da teoria dos grafos a problemas industriais e comerciais. As aplicações dos grafos estendem-se hoje a áreas muito diversas, como, por exemplo o planeamento de uma rede de comunicações viária, projetos de arquitetura, desenho de circuitos eletrónicos, encaminhamento de necessidades nas telecomunicações, distribuição de produtos e controlo de tráfego urbano.” As atividades 2 e 3 sobre as quais nos debruçámos, prendem-se com dois tipos de grafos muito importantes: grafos hamiltonianos e grafos eulerianos, respetivamente. Para melhor compreendermos estes assuntos teremos de nos familiarizar com questões de linguagem.

Um grafo é uma representação esquemática constituída por conjuntos finitos de pontos, a que chamamos vértices, e por segmentos que unem os vértices, a que chamamos arestas.

Definições

INFO

Grafo orientado, dígrafo ou grafo dirigido é um grafo cujas arestas têm sentidos definidos.

Arestas

Arestas são as linhas que ligam um vértice com outro vértice ou o vértice com ele próprio

Arestas paralelas

Arestas paralelas são arestas distintas que ligam os mesmos vértices.

Lacete

Lacete é uma aresta que liga um vértice a ele próprio.

Vértice Isolado

Vértice isolado é um vértice que não tem arestas incidentes.

+ info

Arestas adjacentes são arestas incidentes no mesmo vértice.

Vértices adjacentes são vértices que têm pelo menos uma aresta que os liga.

INFO

Comprimento de um circuito: Chama-se comprimento de um circuito ao número de arestas por que é constituído.

Circuito : Chama-se circuito a um caminho que começa e acaba no mesmo ponto.

Caminho : Sejam A e B dois vértices de um grafo G. Um caminho de A para B é uma sequência alternada de vértices e arestas adjacentes de G. Esta sequência começa em A e termina em B. ( Coloca-se o lápis em A e termina-se em B, sem o levantar).

Caminho e Circuito

Um grafo G é chamado subgrafo do grafo H se todo o vértice de G é vértice de H e se toda a aresta de G é aresta de H.

Subgrafo

Grafo conexo é um grafo no qual existe sempre uma sequência de arestas a unir quaisquer dois dos seus vértices.

Grafo conexo

INFO

A ordem de um grafo representa o número de vértices desse grafo.

Grau, ou valência, de um vértice é o número de arestas que nele incidem.

Grau de um vértice e ordem de um grafo

Existe uma relação entre a soma de todos os graus dos vértices e o número de arestas de um grafo.

Relação entre a soma de todos os graus dos vértices e o número de arestas de um grafo

Grafo completo é um grafo em que qualquer par de vértices está ligado por uma aresta.

Grafo Completo

Grafo Kn

Os grafos completos e simples são designados por Kn, e n representa a ordem do grafo

Todos os vértices têm o mesmo grau (4)Grafo de ordem 5, porque tem 5 vérticesGrafo completo e simples de ordem 5 (K5)

Consideremos o seguinte grafo:

Um grafo é bipartido quando existe uma partição do seu conjunto de vértices em G1 e G2 para que não existam arestas entre qualquer par de vértices de G1 nem entre qualquer par de vértices de G2.

Grafos Bipartidos

  • Em 1º lugar, definimos quais são as ruas e cruzamentos que queremos representar no grafo;
  • Seguidamente, procedemos ao desenho dos vértices (cruzamentos) e das ruas (arestas);
  • Se as ruas forem de sentido único utilizamos um digrafo indicando o sentido correto da circulação;
  • Quanfo for necessário utilizar dois lados da rua , ligam se os respetivos vértices por duas arestas paralelas.

Quando pretendemos construir um grafo a partir de um mapa fazemos da seguinte forma:

Construção de grafos a partir de mapas

Exemplo 11

Exemplo 12

O problema das pontes de Kaliningrad

Na cidade de Kaliningrad (antiga Kõnigsberg) existe uma ilha, chamada Kneiphoff, formada pelos braços do rio Pregel. Há sete pontes que atravessam esses dois braços. Será possível uma pessoa deslocar-se na cidade de tal forma que atravesse cada uma das sete pontes uma e uma só vez?

Grafos de Euler

Resolução

A solução ótima para este tipo de problemas obtém-se quando o grafo que traduz a situação admite um circuito de Euler.

  • Caminho de Euler ou caminho euleriano é um caminho que passa uma única vez em cada aresta.
  • Circuito de Euler é um caminho euleriano que começa e acaba no mesmo vértice.
  • Um grafo diz-se euleriano se admite um circuito de Euler.

Definições:

Teorema do caminho de Euler

  • Um grafo conexo admite um circuito de Euler se e só se todos os vértices tiverem grau par.
  • Num grafo conexo podemos encontrar um caminho de Euler se e só se existirem, no máximo, dois vértices de grau ímpar.
  • Tal caminho terá início num dos vértices de grau ímpar e termina no outro vértice de grau ímpar.

Teorema de Euler

Só será possível uma pessoa deslocar-se na cidade de tal forma que atravesse cada uma das sete pontes uma e uma só vez se este grafo admitir um caminho de Euler. Segundo o Teorema do caminho de Euler, não pode existir mais de 2 vértices de grau ímpar. Os 4 vértices têm grau ímpar! Logo, a deslocação na cidade de forma a atravessar cada uma das sete pontes uma e uma só vez é impossível!!!

De volta à resolução do problema…

Exemplo 1

Exemplo 2

Exemplo 3

  • O que fazer quando um grafo não é de Euler?
  • Existem ou não formas de procurar percursos que minimizem repetições e otimizem gastos e recursos?

Eulerização de grafos

A figura seguinte representa uma parte de uma planta de Aveiro. O Sr. José é carteiro e todos os dias sai dos correios e estaciona a carrinha junto à Igreja do Carmo. A sua tarefa consiste em distribuir o correio pelas casas das ruas indicadas a azul escuro. O Sr. José quer cumprir a sua tarefa da forma mais eficiente possível:

  • Percorrer todas as ruas;
  • Acabar a distribuição no sítio que começou;
  • Não repetir passos a não ser que seja absolutamente
  • necessário.
Como poderá fazê-lo?

Problema do carteiro

  • Este grafo é conexo mas tem vértices de grau ímpar (B, C, D, F, G e I). Não possui, portanto, circuitos de Euler e, por conseguinte, não é possível percorrer todas as ruas sem repetir nenhum troço.

Representar o problema por um grafo:

Resolução

  • É necessário encontrar uma forma de repetir o mínimo possível.
  • Repetir um troço significa duplicar uma aresta no grafo inicial, de forma a que todos os vértices passem a ter grau par e se garanta a existência de um circuito de Euler;
  • Existem 6 vértices de grau ímpar (B, C, D, F, G e I), podemos então duplicar as arestas BC, DF e IG.

Resolução (continuação)

O novo grafo, com 3 arestas paralelas é um grafo de Euler

Pretende-se duplicar arestas já existentes e não criar novas arestas!

Nota importante!!!

Ao processo que consiste em transformar um grafo que não é de Euler num grafo de Euler, duplicando arestas, chama-se eulerizar um grafo.

Para resolver problemas do tipo do Carteiro , temos de encontrar forma de conseguir “eulerizar a situação”, isto é, repetindo o mínimo de arestas possível, conseguir definir um circuito de Euler.

Exemplo 1

Exemplo 2

  • 1º passo: Parte-se do grafo dado e acrescentam-se arestas por duplicação das já existentes, até que se obtenha um grafo conexo e só com vértices de grau par.
  • 2º Passo: As arestas que acrescentamos devem ter uma cor diferente de modo que se destaquem das do grafo original.
  • 3º Passo: Indicar um circuito de Euler (verificação)
A indicação do circuito de Euler funciona como a verificação da resolução do problema proposto.

Chama-se melhor eulerização àquela que acrescenta o número mínimo de arestas. Pode haver mais do que uma "melhor eulerização". Para obter uma eulerização de um grafo, procede-se do seguinte modo:

Uma melhor eulerização

Nos exercícios que estivemos a resolver anteriormente o importante era descobrir percursos em que cada aresta fosse percorrida uma e uma só vez. Neste tipo de situação a nossa atenção é voltada para as arestas. Porém, a nossa análise pode centrar-se nos vértices de um grafo, ou seja, na procura de soluções que exijam a passagem, sem repetição, por determinados vértices e não por arestas. Este tipo de problemas tem muito interesse para os circuitos de distribuição. Encontramos este tipo de problemas na resolução do problema dos contentores. O estudo destas situações foi feito pelo matemático irlandês William Hamilton

Circuito de Hamilton

Um grafo que admite um circuito hamiltoniano é chamado um grafo de Hamilton ou um grafo hamiltoniano.

Um circuito hamiltoniano é um caminho que percorre todos os vértices de um grafo conexo uma única vez, começando e terminando no mesmo vértice (único que se repete).

Definição

Observe o seguinte grafo e verifique se podemos encontrar um circuito hamiltoniano.

Exemplo 1

Circuito: ACDBFEA

Há vários circuitos hamiltonianos neste grafo:

Resolução:

No entanto, podemos sempre observar o seguinte (em grafos conexos):

  • Num grafo com pontes não existem circuitos de Hamilton;
  • Num grafo completo existem sempre vários circuitos de Hamilton.

Não existe nenhum processo que nos permita, dado um grafo qualquer (exceto se for completo), verificar de imediato se existe ou não um circuito hamiltoniano, contrariamente ao que acontece com os circuitos eulerianos. Alguns teoremas garantem apenas a existência de um circuito hamiltoniano para um determinado tipo de grafo. A única forma de saber se um grafo admite ou não um circuito hamiltoniano é proceder a uma procura exaustiva.

Notas

Para cada um dos grafos seguintes, verifique se são hamiltonianos e, em caso afirmativo, indique um circuito:

Exercício 1

Exercício 1 (continuação)

Será que o consegue fazer? Entretanto, houve uma rutura de um cano na rua que liga o armazém C, impossibilitando a sua utilização. Sendo assim, será que consegue fazer o percurso nas mesmas condições?

Na altura das férias, o Gervásio decidiu ocupar o tempo a trabalhar e, assim, ganhar algum dinheiro extra. Foi fazer a distribuição de jornais e revistas na sua vila. Considera o grafo, em que os pontos são locais de distribuição e as arestas são as vias de acesso possíveis entre cada ponto. O Gervásio quer ganhar tempo e pretende passar pelos postos de venda uma única vez, mas tem de partir e chegar ao armazém A.

Exercício 2

Teorema de Ore

Seja G um grafo conexo e simples com ordem n maior ou igual a 3 . Se a soma dos graus de cada par de vértices não adjacentes é maior ou igual a n, então G tem um circuito de Hamilton.

Há um procedimento que pode ser utilizado para determinar se alguns grafos contêm circuitos de Hamilton, pelo Teorema de Ore e Teorema de Dirac, embora este último seja uma consequência do anterior.

Se G (V, A) é um grafo conexo e simples com ordem maior ou igual a 3, tal que o grau de cada vértice é maior ou igual a metade da ordem do grafo, então G é hamiltoniano.

Teorema de Dirac

• Se o número de linhas e o número de colunas é par, o grafo-grelha tem circuitos hamiltonianos. ( exemplo: grelha 4 x 4 ) • Se o número de linhas ou de colunas é um número par e o outro é ímpar então o grafo-grelha tem circuitos hamiltonianos. (exemplo: grelha 4 x 5 ou 5 x 4) • Se ambos, número de linhas e número de colunas, são ímpares então o grafo-grelha não tem circuitos hamiltonianos. (exemplo: grelha 3 x 3 )

Circuitos de Hamilton e grafos-grelha

Através da fórmula (n(n-1))/2 podemos calcular o número de arestas de Kn ( a dimensão do grafo)

A fórmula que permite calcular quantos circuitos hamiltonianos tem kn é ( n - 1 )!

Os grafos completos (cada um dos vértices é adjacente a todos os outros) têm sempre um circuito de Hamilton. Qual o número de circuitos de Hamilton dos grafos completos kn?

Circuitos de Hamilton e grafos completos

Estes grafos chamam-se grafos pesados ou ponderados porque a cada aresta está atribuído um número chamado peso.

Peso é um número que se atribui a cada uma das arestas de um grafo.

Definição:

A solução ótima para este tipo de problema consiste em encontrar um circuito de Hamilton de comprimento mínimo.

O problema do caixeiro-viajante

Um caixeiro viajante tem de visitar um determinado número de cidades e cada deslocação entre duas cidades envolve um certo custo. Qual será a volta mais económica, visitando cada uma das cidades uma única vez e regressando aquela de onde partiu?

No problema anterior, o número de circuitos hamiltonianos pesados diferentes é 3.Quando os grafos têm muitos vértices (o que pode corresponder a grafos de ordem superior a 5), acaba por ser impraticável obter uma solução ótima em virtude de demorar muito tempo. Por este motivo foram criados algoritmos que nos permitem resolver o problema mais rapidamente, ou seja, em tempo útil. Através destes algoritmos podemos não encontrar a solução ótima, mas sim uma solução próxima da solução ótima.

Num grafo hamiltoniano de n vértices, o número de circuitos pesados diferentes é dado pela expressão: (n-1)! /2

O Gustavo precisa de visitar alguns clientes para entregar encomendas. O grafo seguinte traduz os pontos da região onde se encontram os clientes, bem como as distâncias (em km) entre eles. Determine qual é o melhor percurso (percurso mínimo), que o Gustavo deve escolher, a começar e a acabar na cidade E.

Exemplo

Algoritmo da cidade mais próxima

1.º passo: Seleciona-se a cidade de partida;2.º Passo: Segue-se de cidade em cidade, indo para a cidade mais próxima ainda não visitada:

  • Evitando voltar à mesma cidade, se o próximo passo nos leva à cidade anteriormente visitada; escolhe-se a cidade ainda não visitada a que corresponde o peso mais baixo possível;
  • Obrigando a visita a todas as cidades e voltando finalmente à cidade de partida.

Algoritmo do peso das arestas

1.º Passo: Ordenam-se as arestas pelos seus pesos;2.º Passo: Escolhe-se sucessivamente as arestas de menor peso que verifiquem as seguintes condições:

  • Um vértice nunca poderá aparecer 3 vezes;
  • Nunca se fecha um circuito havendo vértices por visitar;
  • Pretende-se visitar uma e uma só vez todas as cidades.
3.º Passo: Ordena-se a solução conforme o vértice da partida escolhido.

Um outro tipo de grafos que podemos estudar são as árvores. Definição: Um grafo G diz-se uma árvore se e só se é conexo e não tem circuitos. (não podem ter arestas paralelas nem lacetes)

Árvores

A Leonor, que é delegada de informação médica, tem na sua agenda várias farmácias que deve visitar em diferentes cidades. Para escolher o melhor percurso, em termos de distância (quilómetros), decidiu fazer o esquema que se apresenta ao lado. Supondo que sai da cidade A, qual é o percurso mais curto que lhe permite visitar todas as cidades e regressar a A?

Exemplo 1:

Resolução:

Resolução (continuação)

Temos 5 amigas, em casas diferentes, que pretendem ligar os seus computadores em rede. Para isto ser possível não é necessário que cada um esteja ligado aos 4 restantes simultaneamente, o que é preciso é que haja uma ligação que permita a comunicação entre quaisquer 2 computadores. Assim, o que pretendemos saber é qual é o menor número de ligações a fazer, e entre que computadores, de modo a que sejam abrangidas todas as máquinas.

Exemplo 2:

Consideremos o grafo seguinte, em que os vértices correspondem às casas e as arestas são todas as ligações possíveis.

Resolução

A este grafo que abrange todos os vértices do nosso grafo inicial, mas utiliza apenas algumas arestas, chamamos árvore abrangente. (subgrafo)

Então, uma solução que serve as nossas intenções será (por exemplo):

Continuação ...

No caso dos cinco amigos que querem ligar os computadores em rede, são também exemplos de árvores abrangentes do grafo considerado, para além do já referido, os seguintes:

Dado um grafo conexo qualquer G, chama-se árvore abrangente ou árvore geradora de G a qualquer subgrafo conexo que, sendo árvore, contém todos os vértices de G.

Definição:

O problema colocado em relação à ligação dos computadores em rede pode pôr-se relativamente a outras situações: canalizações, de água ou gás, cabos de fibra ótica para telecomunicações (telefone, televisão por cabo, etc), gasodutos que atravessam vários países, só para referir algumas. Em qualquer uma destas situações o objetivo principal é, não só servir da melhor forma, mas também minimizar os custos (sejam eles mão-de-obra, tempo ou distância).A principal diferença entre este tipo de problema e o PCV é que neste caso não temos de regressar ao ponto de partida: só temos de encontrar um percurso que visite todos os vértices sem criar circuitos. Estaremos, então, à procura de uma árvore especial, a árvore abrangente mínima.

Árvore Abrangente Mínima é uma árvore em que a soma dos pesos das arestas é mínima. Para encontrar a árvore abrangente mínima existe um algoritmo que garante que o resultado obtido é sempre a solução ótima.

Definição

Este algoritmo garante que a solução encontrada é uma solução ótima, ao contrário dos algoritmos utilizados para os problemas do tipo do Caixeiro Viajante.

As arestas do grafo vão-se unindo por ordem crescente dos pesos, desde que não se formem circuitos, sendo que, no final, todos os vértices estão na árvore.

Algoritmo de Kruskal

Determine o percurso mínimo e desenhe a árvore abrangente correspondente

Um camião deve recolher resíduos tóxicos de 7 instalações e, ao fazê-lo, deve percorrer a menor distância possível. A empresa responsável distribuiu ao condutor um esquema, com as instalações a visitar e as distâncias entre elas (em km), que está representado a seguir sob a forma de grafo:

Exemplo

Resolução

Continuação

  • 1.° Passo) Encontrar a aresta com menor peso (se houver mais do que uma, escolhemos ao acaso) e "marcá-la";
  • 2.° Passo) Encontrar a aresta seguinte com menor peso (se houver mais do que uma, escolhemos ao acaso) e "marcá-la".
  • 3º Passo) Encontrar a aresta seguinte com menor peso que não feche um ciclo e marcá-la a cor (uma vez mais, se houver mais do que uma escolhemos ao acaso). Se a aresta a escolher fechar um ciclo, não consideramos essa aresta.
  • 4º Passo) Repetir os passos anteriores até que todos os vértices tenham sido visitados.

Algoritmo de Kruskal

  • 1.° Passo) Escolher a aresta com menor peso, marcá-la e marcar os vértices adjacentes;
  • 2.° Passo) Marcar outra aresta com menor peso, que tenha um vértice já marcado e outro não, marcando este último.
  • 3º Passo) Continuar o 2º passo até marcar todos os vértices.

Algoritmo de Prim

Os grandes projetos requerem uma calendarização de execução, um acompanhamento constante e uma perfeita coordenação das tarefas inerentes à sua concretização, não só para evitar atrasos mas também para evitar custos adicionais. Essas tarefas não podem ser feitas de forma aleatória uma vez que a realização de uma, ou mais, pode estar dependente da realização de outras. Foi a procura de uma otimização na realização de projetos que levou à criação do método do caminho crítico.

Caminho Crítico

Para representar este tipo de situações problemáticas recorremos a um dígrafo. (grafo em que as arestas têm sentidos definidos).

Sequência de tarefas que deverão ser realizadas nos tempos previstos para a concretização de um certo trabalho ou projeto dentro do prazo. A sua duração é aquela que determina o menor tempo para a conclusão do projeto e corresponde à maior duração global.

Definição

Um dos trabalhos realizados diariamente nos aeroportos de todo o mundo e que exige grande coordenação de equipas responsáveis por tarefas diferentes, é o que é necessário fazer desde que um avião aterra na pista até ficar novamente pronto para seguir viagem.A tabela resume a informação relativa a este tipo de trabalho.

Exemplo

Resolução

Representação por um dígrafo da programação deste trabalho

  • As tarefas T1 e T3 iniciam-se ao mesmo tempo e ao fim de 8 minutos pode começar T2.
  • 14 minutos depois podem começar as tarefas T4 , T5 e T7.
  • São necessários mais 13 minutos para dar início a T6.
  • Quando T6 começa, T2 já terminou, mas T4 e T7 ainda não. Para concluir T4 são necessários 14 minutos (para realizar T3) mais 25 minutos.
  • As tarefas T2 , T5 ,T6 e T7 não dependem da realização de T4 e já estarão terminadas quando esta acaba.
Conclusão: O caminho crítico é formado pelas tarefas T3 e T4 , com uma duração de 14 + 25 = 39 minutos.