Re: problema!

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, 15 Jan 2000, Marcelo Souza wrote:

> Olá,
>          Certa vez quando eu estava em minha escola, um colega meu me propôs 
> o seguinte jogo. Eram dados seis pontos obedecendo o padrão abaixo:
>                   .    .    .
> 
>                   .    .    .
> O jogo era o seguinte: devíamos escolher uma das duas fileiras de três 
> pontos: a de cima, ou a de baixo. Quando isso feito, devíamos escolher um 
> ponto da fileira que escolhemos e ligá-lo aos três pontos acima (ou abaixo, 
> dependendo da fileira escolhida), com uma reta ou com uma linha curva, 
> depois escolheríamos outro dos dois pontos restantes na fileira e faríamos o 
> mesmo, e por fim, com o último ponto, só que seguindo uma regra: nenhuma 
> reta ou linha curva poderia "cortar" uma outra reta ou linha curva que 
> ligasse um outro ponto ao outro de cima (ou de baixo, dependendo da fileira 
> escolhida).
> Por tentativa, percebi que eu não conseguia satisfazer a regra, pois eu 
> sempre acabava cortando, no mínimo, uma reta ou curva que ligasse a um outro 
> ponto na fileira oposta.
> Alguém poderia me explicar (demonstrando) se é possível satisfazer a tal 
> regra e ganhar este jogo?
> Espero Ter sido claro
> Obrigado
> Abraços
> Marcelo
> OBS.: Não há padrão para ligar dois pontos com uma linha curva, ou seja, 
> pode-se fazer o malabarismo que quiser para ligar um outro ponto, somente 
> não pode cruzar uma outra linha que esteja ligando outros dois pontos!
> ______________________________________________________
> Get Your Private, Free Email at http://www.hotmail.com
> 

Se eu bem entendi, este 'e um problema cl'assico de teoria de grafos:
mostrar que o grafo bipartido completo com 3+3 elementos n~ao 'e planar.
O grafo em quest~ao tem tr^es v'ertices brancos e tr^es v'ertices pretos
e todo v'ertice branco deve ser conectado a todo v'ertice preto.
Um grafo 'e planar exatamente quando ele pode ser desenhado conforme voc^e
parece estar tentando descrever. Outro grafo simples n~ao planar 'e o grafo
completo com 5 v'ertices (cada par de v'ertices distintos deve ser conectado).

Nos dois casos uma demonstra,c~ao por an'alise cuidadosa de casos 'e poss'ivel
mas uma demonstra,c~ao muito mais elegante 'e dada pela f'ormula de Euler
(V + F = A + 2, onde V, A e F s~ao o n'umero de v'ertices, arestas e faces
de uma decomposi,c~ao da esfera). Suponha por absurdo que o seu grafo possa
ser desenhado em uma esfera. Temos ent~ao para este desenho V + F = A + 2.
Mas claramente V = 6 e A = 9 donde F = 5. Mas cada face deve ter um n'umero
par de lados (pois os v'ertices s~ao alternadamente brancos e pretos),
donde pelo menos 4 lados. Assim, o n'umero total de lados de faces 'e no
m'inimo 5*4 = 20. Mas cada aresta 'e contada como lado exatamente duas vezes
donde o n'umero de arestas A 'e pelo menos 10, contradizendo A = 9.
O grafo completo com 5 v'ertices fica agora como exerc'icio.

[]s, N.