[obm-l] Re: [obm-l] ESTE PROBLEMA É INSOLÚVEL?

["Eduardo Fischer" <sondudu@xxxxxxxxxxxxx>]

Não é possível. Sajam as casas 1, 2 e 3 e A, L e E as coisas.

 

    E    L    A

 

 

    1    2     3

 

É imposível, pois não acontecem as ligações 1-A e E-3 não podem ocorrer ambas por dentro ou ambas passando por fora ( por dentro forma um x e por fora a ligação duma tranca um dos vértices da outra ).

Podemos supor que 1-A é por dentro e E-3 por fora. Consideremos 2-L.. Essa ligação faria um x com 1-A se fosse por dentro. Por fora não ocorre pois qualquer forma de ligação de E-3 tranca ou L ou 2.

 

----- Original Message -----

From: J.C. PAREDE

To: OBM

Sent: Tuesday, January 14, 2003 5:07 PM

Subject: [obm-l] ESTE PROBLEMA É INSOLÚVEL?

Faz um tempo que venho quebrando a cabeça para resolver o seguinte problema.

"Em um bairro estão três casas, uma ao lado da outra e a distribuidora de água, de esgoto e de luz, sendo as distribuidoras também localizadas uma ao lado da outra em uma reta suporte paralela a reta suporte das casas. Deve-se por meio de tubulações levar água, esgoto e luz para todas as casas, sem que as tubulações se cruzem e tendo todas as tubulações a mesma profundidade. Como se deve fazer esta ligação?"

Tentei quebrar a cabeça sozinho, dei uma olhada em termos de Geometria Euclidiana Plana, ouvi dizer que pode ser resolvida por grafos (porém não sei nada de grafos); e esses dias ouvi que este problema não tem solução; porém o camarada que disse isto disse que não tinha como provar.

Afinal, este problema tem ou não solução?

Já foi citado na lista problemas sobre grafos. Há alguma literatura no nível "grafos para iniciantes" que alguém conheça?

Obrigado

 JOÃO CARLOS PAREDE

---

Busca Yahoo!
O melhor lugar para encontrar tudo o que você procura na Internet