[obm-l] K(3,3),K(5),Kuratowsky,agua luz telefone e coisas assim...

[peterdirichlet1985@xxxxxxxxxxxxxx]

Esse e bem legal.Alguem da lista pediu essa informaçao.Da pra demonstrar
o teorema de Kuratowsky que diz que os grafos planares tem como menores
proibidos o:
*K(3,3),que e um grafo bipartido completo tres tres,ou seja,e algo como
o troço da agua luz e telefone com as tres casas;e o
*K(5)que e o grafo completo cinco,onde ha cinco pessoas em que todos sao
amigos de todos.Parece uma estrela dentro de um pentagono.
Essa historia de menores o Tengan,o Fabricio e o Shine podem explicar bem
melhor do que eu,mas e algo intuitivo como estar contido:um grafo e menor
de outro se pode ser obtido pela contraçao e retirada de arestas do primeiro.
A demonstracao do K(3,3) e na verdade feita toda vez que um leigo tenta
resolver.Pegue as casas C1,C2,C3 e as estaçoes A,L,T. Desenhe sem cruzar
as ligaçoes de C1 e C2 com A e L.Voce forma um "quadrilatero" ou ciclo elementar
AC1LC2.Veja que tanto faz o C3 estar dentro ou fora.Ao ligar C3 a A e L
temos dois ciclos encaixados.Basta dai verificar que tentar colocar o T
em qualquer lugar nao da pois alguem fica sem.E fim!
Acho que pro K5 deve sair assim mesmo.Mas a volta do teorema e a parte que
pega.Deve ter no livro Handbook of Combinatorics.Vouy tentar tirar copias
ou comprar o dito.

Ate mais!!!Ass.:Johann
Lembre-se:


TEA WITH ME THAT I BOOK YOUR FACE


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