Re: [obm-l] Desafio

["Joao Victor Brasil" <jvbrasil@xxxxxxxxx>]

Leo,

Como ficaria um esquema com a solução deste problema?

Saudações,
Joao Victor

On 11/1/07, Leonardo Maia <lpmaia@xxxxxxxxx> 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. <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
> >
>

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================