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>
=========================================================================