Re: [obm-l] Desafio

["Leonardo Maia" <lpmaia@xxxxxxxxx>]

Oi, Vivian.

O fato é que você tem um grafo (ou seja, um conjunto de nós e um conjunto de arestas ligando dois nós) bipartido (ou seja, há dois tipos de nós, e os nós de um tipo só podem ser ligados por arestas a nós do outro tipo), com 3 nós de um tipo (os nós A, L e E) e 3 nós do outro tipo (as 3 casas, cada uma indexada por um número, por exemplo: 1, 2 e 3).

O desafio equivale à pergunta: existe um grafo bipartido 3 por 3 em que cada nó de um tipo (as estações) esteja ligado aos 3 nós do outro tipo (as casas) - tal grafo, com todas as arestas possíveis, é um grafo bipartido 
completo - e que seja planar? Um grafo planar é um grafo que admite uma representação gráfica "no mesmo plano" em que quaisquer duas arestas não se cruzam.

É um resultado clássico da teoria de grafos, cuja demonstração pode ser encontrada em vários textos, que tal grafo (denotado por K_3,3) não é planar.

Saudações,
Leo.

On 10/31/07, Vivi H. <xjxjbo@xxxxxxxxx> wrote:

Olá Pessoal...

 

Estava conversando com minha professora de cálculo sobre um desafio que é bem divulgado por aí. A maioria das pessoas afirma que tal desafio é impossível de se resolver, porém, minha professora falou que algumas pessoas falaram que o desafio é possível, mas não mostraram de que jeito é possível...

Gostaria de saber o que vocês acham...

 

Desafio:

Você tem que levar água, luz e esgoto para 3 casas de uma cidade. As fornecedoras de água (A), luz (L) e esgoto (E) permitem que os canos distribuidores não sejam retos... São canos flexíveis e podem ser arrumados da forma que você desejar.

Os canos JAMAIS podem se cruzar e/ou invadir a região interna de qualquer casa e de qualquer fornecedora.

A profundidade de encanamentos sob os terrenos da cidade que a prefeitura tolera é única. Ou seja, assuma no esquema que todos os canos são como linhas no mesmo plano.

Muito obrigada...

Vivian