Turan: o grafo que nao possui K_p completo possui no máximo (1-1/p-1)n^2
arestas... .. Cara eu acredito que tenha usar grafo orientado pois nao
reciprocidade em odiar senador enfim .. Vamos pensar mais..
Em quinta-feira, 19 de setembro de 2013, Esdras Muniz escreveu:
> Pensei no seguinte, não sei se ta certo:
> Vamos transformar o problema num grafo, cada senador é um vertice, e se u
> odeia v ligamos u a v por uma aresta. No final teremos n grupos, e em cada
> grupo não temos dois vertices ligados por aresta. Olhe então o complementar
> do grafo, todos os grupos serão grafos completos, então o maior grupo tem
> pelomenos {parte inteira de 51/n} vertices. Vamos olhar a situação então
> assim: não é possível fazer isso com n-1 grupos, ou seja, não há um grafo
> completo com {parte inteira de 51/(n-1)} vertices. Então , temos que o
> nosso grafo complementar tem pelomenos (51 escolhe 2) - 3*51 arestas e não
> pode ter um subgrafo completo com {parte inteira de 51/(n-1)} vertices.
> então, você usa o teorema de turan assim:
> T(|G|,P)<=(51 escolhe 2) - 3*51 onde |G|=51 e P={parte inteira de 51/n}+1.
> Vou parar aqui pois não lembro como é a expreção do teorema de Turan.
>
>
> Em 16 de setembro de 2013 11:41, Jeferson Almir
> <jefersonram...@gmail.com<javascript:_e({}, 'cvml',
> 'jefersonram...@gmail.com');>
> > escreveu:
>
>> Essa questão é do Mathematical Olympiad Summer Program e acreditei que
>> sairia por grafos.. mas até agora nada.. partir para casa dos pombos. .quem
>> puder ajudar serei grato. . fiz uns casos iniciais e acredito n<=8
>>
>> Há 51 senadores em um senado. O Senado precisa ser dividido em n comitês de
>> tal forma que cada senador está em exatamente um comitê. Cada senador
>> odeia exatamente três outros senadores. (Se o senador A odeia senador B,
>> então
>> o senador B "não" necessariamente odeia o senador A.) Encontre o menor n tal
>> que sempre é possível organizar os comitês de modo que nenhum senador
>> odeia outro senador em seu comitê.
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
>
>
>
> --
> Esdras Muniz Mota
> Graduando em Matemática Bacharelado
> Universidade Federal do Ceará
>
> "Se algum dia ele recuou, foi para dar um grande salto"
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
