[obm-l] Re: [obm-l] Re: [obm-l] Dúvida de vestibular

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

Eu [ainda] não sei resolver o problema do Okakome mas...

On Wed, Feb 26, 2003 at 04:39:33PM -0300, Domingos Jr. wrote:
> >     Oi Pessoal,
> >   Estava estudando análise combinatória por uma
> > apostila de um curso pré-vestibular, e encontrei o
> > seguinte problema, que achei interessante, mas minha
> > solução foi muito longa, e não sei se está certa,
> > porque tinha muitos casos. Se estivesse num
> > vestibular, o que faria?
> >   Num país, as estradas ligam duas cidades e são de
> > mão única (pode haver mais de uma estrada entre duas
> > cidades). O número de estradas que partem de cada
> > cidade é igual ao número de estradas que chegam nessa
> > cidade. Um mapa da cidade C é um conjunto de rotas
> > que: 1) levam C a cada uma das outras cidades do país,
> > sem passar por uma cidade mais de uma vez. 2) Se uma
> > rota parte de C a D passando por E, então a rota que
> > vai de C a E coincide com o começo da rota de C a D.
> > Prove que o número de mapas da cidade C é igual ao
> > número de mapas de qualquer outra cidade.
> 
> Acho que esse enunciado não está completo:
> - se existe uma cidade com nenhuma estrada partindo ou chegando possui um
> número de rotas 0 e não vai ser igual as demais, até aí é um caso idiota que
> pode ser excluído do problema.

Neste caso não existe nenhum mapa pois é impossível ligar C a X,
a cidade sem estradas. O problema fica correto pois o número
de mapas é sempre 0.

> - se existem conjuntos de cidades "disjuntos" ou seja cidades de um conjunto
> A não possuem rota nenhuma para as cidades do conjunto B e vice-versa:
> 
> C1 <-------> C2 ( 1 estrada de C1 -> C2 e outra de C2 -> C1  )
> C3 <======> C4 ( 2 estradas de C3 -> C4 e duas de C4 -> C3 )
> 
> neste caso temos que o número de rotas de N(C1) = N(C2) = 1, mas N(C3) =
> N(C4) = 2.

Também neste caso o número de mapas é sempre 0.

> além disso, há um trecho que eu considero confuso:
> 
> "2) Se uma rota parte de C a D passando por E, então a rota que vai de C a E
> coincide com o começo da rota de C a D"
> nessa situação parece que a rota de C a E deve ser única, mas podem haver
> outras rotas de C até E sem que uma cidade seja visitada mais de uma vez...
> mesmo que sempre fossem escolhidos os caminhos que passem por menos cidades
> isso poderia ocorrer já que é permitido haver mais de uma estrada ligando
> duas cidades.

Acho que ajuda considerar o caso em que todas as estradas são de mão dupla:
neste caso um mapa nada mais é do que uma árvore maximal e o problema
fica trivial.

[]s, N.
=========================================================================
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>
=========================================================================