Senhor

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 rota deveria 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 entre os 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 incluir exatamente 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 circuito que 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 da