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. <[EMAIL PROTECTED]> 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 >
