[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Este problema é tem solução (2)?
Esse e bem legal!!!!!Eu tinha dado a soluçao porrada dessa birosca ha semanas .Da pra demonstrar de outro jeito(de fato a mesma coisa):mostra que ha seis regioes pelo menos determinadas pelo grafo descontando a ilimitada.Essa ideia de contrair quem me ensinou foi o Eduardo Tengan.Ele pensava assim:imagine que uma cidade começa a crescer tanto que engloba algumas de suas vizinhas.Isso e (quem diria?) contraçao.
Alias eu dou outra otima referencia para livros:o Handbook of Combinatorics.Deve ter na Cultura,mas eu pego na USP.Depois eu passo a demonstraçao reciproca de Kuratowsky.
Carlos Yuzo Shine <cyshine@yahoo.com> wrote:
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 ligando 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"
> 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 é
=========================================================================
Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.