Re: [obm-l] Este problema � tem solu��o (2)?

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Pode-se pensar no problema da �gua, luz e esgoto (ou
provar que K_{3,3} n�o � planar) dessa forma: suponha
que seja planar. Ent�o valeria o teorema de Euler (que
pode ser demonstrado com, para variar, indu��o): V - A
+ F = 2 <=> F = A - V + 2. Mas cada face tem pelo
menos 4 arestas, logo, o n�mero de arestas � maior ou
igual a 4F/2 (cada aresta � comum a duas faces e est�
sendo contada duas vezes). Assim, A >= 2F <=> A >= 2(A
- V + 2) <=> 2V >= A + 4. Mas V = 6 e A = 9, e n�o
vale 2*6 >= 9 + 4 (por pouco!), absurdo. Logo o grafo
considerado n�o � planar.

Voc� pode tentar provar que o grafo de Petersen,
s�mbolo da OPM (veja ele em http://www.opm.mat.br )
tamb�m n�o � planar, do mesmo jeito.

� interessante comentar que um grafo � planar se, e
somente se, n�o possui K_{3,3} (o grafo desse
problema) e n�o possui K_5 (o grafo com 5 v�rtices na
qual ligamos todo par de v�rtices) como minor (este �
o teorema de Kuratowski).

Um grafo X � minor de outro Y se � poss�vel obter X de
Y da seguinte forma: primeiro, divida X em alguns
conjuntos de v�rtices, todos conexos (ou seja, dentro
de cada conjunto existe algum caminho ligando
quaisquer dois de seus elementos); depois, associe a
cada conjunto um v�rtice e ligue dois v�rtices A e B
se e somente se existe alguma aresta ligando algum
v�rtice de A a algum v�rtice de B.

Eu gosto de pensar assim: imagine v�rias cidadezinhas
com estradas lignado elas. Suponha que algumas
cidadezinhas formem vilas (nas vilas � sempre poss�vel
ir de uma cidadezinha a outra). Agora imagine o grafo
como se fossem formado pelas vilas e ligamos duas
vilas se existe um caminho as ligando diretamente.

Tudo isso pode ser encontrado no excelente livro de
grafos do Reinhard Diestel: Graph Theory. Por
curiosidade, na p�gina 167 da segunda edi��o, est� o
nome de um matem�tico brasileiro: o Yoshi. Eu comprei
o livro (editora Springer) na Livraria Cultura, mas
ele pode ser encontrado (mas n�o impresso) na
Internet.

[]'s
Shine

>  "J.C. PAREDE" <joaocarlosparede@yahoo.com.br>
> wrote:
> Fiquei um tempo sem escrever na lista. Por�m na
�ltima vez que escrevi mandei a seguinte pergunta:
> 
> 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.

__________________________________________________
Do you Yahoo!?
Yahoo! Platinum - Watch CBS' NCAA March Madness, live on your desktop!
http://platinum.yahoo.com
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <nicolau@mat.puc-rio.br>
=========================================================================