Leo, Como ficaria um esquema com a solução deste problema?
Saudações, Joao Victor On 11/1/07, Leonardo Maia <[EMAIL PROTECTED]> wrote: > 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 > > > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
