Make your own free website on Tripod.com


Grafos Eulerianos

 

Um grafo G é dito ser euleriano se há um ciclo em G que contenha todas as suas arestas. Este ciclo é dito ser um ciclo euleriano. O grafo da figura ao lado, por exemplo, é euleriano já que ele contém o ciclo: (u1, u2, u3, u4, u5, u3, u6, u7, u1), que é euleriano.

O teorema que se segue provê um solução simples para determinar que grafos e multigrafos são eulerianos:

Teorema: Um multigrafo M é euleriano se e somente se M é conexo e cada vértice de M tem grau par.

Agora, considere um multigrafo G tenha uma trilha (não um ciclo) contendo todas as arestas de M. Então G é dito ser um grafo atravessável e a trilha é dita ser uma trilha euleriana. No grafo ao lado, a trilha: (u1, u2, u3, u4, u1, u3, u5) é atravessável.

O teorema seguinte indica precisamente que grafos são atravessáveis:

Teorema: Um multigrafo M é atravessável se e somente se M é conexo e tem exatamente dois vértices de grau impar. Consequentemente, qualquer trilha euleriana de M começa em um dos vértices de grau impar e termina no outro vértice de grau impar.

Provavelmente, o exemplo mais antigo de problema que faz uso de grafos (ou conceito correlatos) como modelo matemático é o Problema das Pontes de Königsberg. Ele foi resolvido pelo matemático suiço Leonhard Euler (1707-1783) em 1736, a partir do qual gerou-se toda uma classe de grafos que levam o nome de Euler.

Problema das Pontes de Königsberg

No século 18 havia na cidade de Königsberg um conjunto de sete pontes (identificadas pelas letras de a até f na figura ao lado ) que cruzavam o rio Pregel . Elas conectavam duas ilhas  (A e D) entre si e as ilhas com as margens (B e C).

Por muito tempo os habitantes daquela cidade perguntavam-se se era possível cruzar as sete pontes numa caminhada contínua sem que se passasse duas vezes por qualquer uma delas.

Problema do desenho da casa

No desenho ao lado, uma criança diz ter posto a ponta do lápis numa das bolinhas e com movimentos contínuos (sem levantar e sem retroceder o lápis) traçou as linhas que formam o desenho da casa, traçando cada linha uma única vez.

A mãe da criança acha que ela trapaceou pois não foi capaz de achar nenhuma seqüência que pudesse produzir tal resultado. Você concorda com esta mãe?

O Caso Count Van Diamond


O cenário ao lado é a residência do bilionário Count Van Diamond, que acaba de ser assassinado. Sherlock Gomes (um conhecido detetive que nas horas vagas é um estudioso da Teoria dos Grafos) foi chamado para investigar o caso. O mordomo alega ter visto o jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar sair daquela sala pela mesma porta que havia entrado. O jardineiro, contudo, afirma que  ele não poderia ser a pessoa vista pelo mordomo, pois ele havia entrado na casa, passado por todas as portas uma única vez e, em seguida, deixado a casa. Sherlock Gomes avaliou a planta da residência (conforme figura abaixo) e em poucos minutos declarou solucionado o caso. Quem poderia ser o suspeito indicado por Sherlock Gomes? Qual o raciocínio utilizado pelo detetive para apontar o suspeito?

O Problema da pavimentação de estradas

Tertuliano Gonçalves havia prometido casamento a Josefina das Graças. O evento
deveria ser realizado, segundo ele, assim que acabasse o contrato de trabalho recém assinado com uma empresa encarregada de pavimentar toda a rede de estradas que ligava Santana do Caixa Prego (cidade onde morava Josefina)  às cidades da região. O trabalho iria começar em Santana e prosseguir em continuidade, estrada após estrada, terminando, segundo explicou Tertuliano, na própria Santana. A rede de estradas é dada pela matriz de adjacência ao lado, na qual a cidade de Santana  do Caixa Prego é representada pelo número 1.

  • Você que leu esta estória acha que Tertuliano estava sendo sincero com Josefina? Por quê?
  • E se o itinerário 1-5-9-10 estivesse a cargo de outra empresa, estaria ele sendo sincero?