Senhor

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2116 palavras )
  • Download(s) : 0
  • Publicado : 30 de novembro de 2011
Ler documento completo
Amostra do texto
DOIS PROBLEMAS SOBRE GRAFOS
Paulo Cezar Pinto Carvalho

IMPA

( Nível Intermediario.

INTRODUÇÃO

A figura abaixo mostra um mapa rodoviário de um país fictício. Neste artigo vamos examinar dois problemas relativos a este mapa:

1. Um funcionário, encarregado de verificar, periodicamente, o estado das estradas, deseja planejar a sua rota de inspeção. Idealmente, esta rotadeveria se iniciar na capital e percorrer cada estrada exatamente uma vez, voltando, então, ao ponto de partida. Existe tal rota?

2. Um representante de vendas de uma companhia deseja planejar uma rota na qual ele visite cada cidade exatamente uma vez, voltando ao ponto de partida. Existe tal rota?

[pic]

Fig. 1 - Mapa rodoviário de um país fictício

Há vários pontos em comum entreos dois problemas. Por exemplo: em ambos se deseja verificar a existência de um circuito (ou ciclo) no grafo determinado pelo mapa (um grafo é um par (V, A), em que V é o conjunto de vértices do grafo, e A é um conjunto de pares de vértices – os arcos do grafo). No primeiro problema, este circuito deve incluir exatamente uma vez cada arco do grafo. No segundo problema, o circuito deve incluirexatamente uma vez cada vértice do grafo. Embora os dois problemas sejam aparentemente semelhantes, há algumas diferenças fundamentais entre eles. Convidamos os leitores a refletir um pouco sobre cada um deles antes de prosseguir.

CIRCUITOS EULERIANOS

O primeiro problema – o do inspetor de estradas – foi estudado pela primeira vez por Euler (1707-1783). Por esta razão, um circuitoque percorre cada arco de um grafo exatamente uma vez é chamado de circuito euleriano e um grafo que possui um tal circuito é chamado de grafo euleriano. A situação estudada por Euler ficou imortalizada como o Problema das Pontes de Könisberg, ilustrado na figura abaixo, e que possivelmente já é conhecido por muitos dos leitores. O objetivo é percorrer exatamente uma vez todas as sete pontes dacidade (hoje Kaliningrado), que conectam as duas ilhas entre si e com as margens do rio, voltando ao ponto de partida.
[pic]
Fig. 2 – O Problema das Pontes de Könisberg

Em linguagem de grafos, trata-se de encontrar um circuito euleriano no grafo da figura acima, no qual os vértices representam as ilhas e as margens e os arcos são as pontes[1]. Euler mostrou a não-existência de talcircuito através de um argumento extremamente simples. Consideremos, por exemplo, a ilha da direita. Um circuito qualquer deve chegar à ilha e sair dela o mesmo número de vezes. Logo, para que exista um circuito euleriano, deve haver um número par de pontes com extremidade nesta ilha. Como existem três pontes nessas condições, concluímos que não é possível encontrar um circuito euleriano. Demodo mais geral, temos o seguinte:

Teorema: Existe um circuito euleriano em um grafo se e somente se o grafo é conexo (isto é, existe um caminho ligando qualquer par de vértices) e cada vértice tem grau par (ou seja, o número de arcos que nele incidem é par).
O argumento acima mostra a necessidade de se ter grau em cada vértice para existir um circuito euleriano. É também óbvio que ografo precisa ser conexo. A prova de que essas duas condições implicam na existência de um circuito euleriano pode ser feita por indução finita no número de arcos do grafo e é deixada como um exercício para o leitor.

[Sugestão: suponha a propriedade verdadeira para grafos com menos de n arcos e considere um grafo com n arcos, satisfazendo às duas condições. Começando em um vértice qualquer,percorra arcos do grafo, até voltar a um vértice já visitado (o caminho gerado possui, então, um ciclo). Retirando do grafo os arcos desse ciclo, obtém-se um ou mais grafos satisfazendo as duas condições e com menor número de arcos (portanto, com circuitos eulerianos, de acordo com a hipótese de indução). Basta explicar como “costurar” esses circuitos eulerianos ao ciclo descrito acima]....
tracking img