Re: [obm-l] Problema de grafos

[Daniel da Silva]

Obrigado pela ajuda Esdras e Matheus.

Daniel Rocha da Silva

> Em 2 de set de 2017, às 13:23, Esdras Muniz  
> escreveu:
> 
> Cada vértice pode ter como grau um número de 0 a n-1, porém o 0 e o n-1 
> não podem ambos ser graus de vértices, pois se um tem grau n-1 então ele 
> está ligado a todos os outros vértices. Então há apenas n-1 
> possibilidades para o grau de cada vértice. Pelo pcp há dois vértices com 
> o mesmo grau.
> 
> Em 2 de set de 2017 12:34 PM, "Daniel Rocha"  
> escreveu:
>> Bom dia,
>> 
>> Seja G um grafo com n vértices, n maior que 1. Suponha que G não possua
>> loops nem mais de uma aresta unindo pares de vértices. Prove que G possui
>> dois vértices de graus iguais.
>> 
>> Obrigado,
>> Daniel
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> Â acredita-se estar livre de perigo.
>> 
>> 
>> =
>> Instruções para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
>> =
> 
> -- 
> 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.

Re: [obm-l] Problema de grafos

[Esdras Muniz]

Cada vértice pode ter como grau um número de 0 a n-1, porém o 0 e o n-1 não
podem ambos ser graus de vértices, pois se um tem grau n-1 então ele está
ligado a todos os outros vértices. Então há apenas n-1 possibilidades para
o grau de cada vértice. Pelo pcp há dois vértices com o mesmo grau.

Em 2 de set de 2017 12:34 PM, "Daniel Rocha" 
escreveu:

> Bom dia,
>
> Seja G um grafo com n vértices, n maior que 1. Suponha que G não possua
> loops nem mais de uma aresta unindo pares de vértices. Prove que G possui
> dois vértices de graus iguais.
>
> Obrigado,
> Daniel
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
>  acredita-se estar livre de perigo.
>
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

Re: [obm-l] Problema de grafos

[Matheus Secco]

Olá Daniel, veja que os graus podem variar de 0 até n - 1. Entretanto, não
é possível ter um vértice com grau 0 e outro com grau n - 1. Desta forma,
em vez de n possibilidades para o grau de cada vértice, há n - 1
possibilidades para o grau de cada vértice. Como há n vértices, pelo
Princípio da Casa dos Pombos, há dois com o mesmo grau.
Abraços,
Matheus Secco

2017-09-02 11:26 GMT-03:00 Daniel Rocha :

> Bom dia,
>
> Seja G um grafo com n vértices, n maior que 1. Suponha que G não possua
> loops nem mais de uma aresta unindo pares de vértices. Prove que G possui
> dois vértices de graus iguais.
>
> Obrigado,
> Daniel
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
>  acredita-se estar livre de perigo.
>
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Problema de grafos

[Daniel Rocha]

Bom dia,

Seja G um grafo com n vértices, n maior que 1. Suponha que G não possua
loops nem mais de uma aresta unindo pares de vértices. Prove que G possui
dois vértices de graus iguais.

Obrigado,
Daniel
-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

Re: [obm-l] Problema de grafos

[Mauricio de Araujo]

valeu demais!!

2012/6/5 Ralph Teixeira ralp...@gmail.com

 Versao relampago:
 casa-dos-pombos, 68,68,68,69,69,69,70,70,70,...,100,100,100,101,101,101,
 contradicao.

 Versao explicada:
 Ha 101-67=34 numeros entre 68 e 101 (que sao os possiveis numeros de
 amigos) de cada fulano.
 Seja xi o numero de estudantes com i amigos (onde i=68,69,...,101). Note
 que sao 34 numeros xi, cuja soma eh 102. Queremos provar que algum deles eh
 maior ou igual a 4, certo?
 Entao suponha por contradicao que todos eles sao menores ou iguais a 3.
 Entao a soma eh no maximo 34x3=102, o que soh serah atingido se TODOS forem
 iguais a 3. Entao chegamos aa conclusao de que o unico jeito do nosso
 teorema furar seria se houvesse 3 alunos com 68 amigos, outros 3 com 69
 amigos, e assim por diante, e 3 com 101 amigos, exatamente.

 Agora seja yk o numero de amigos do fulano k (k=1,2,3,...,102) -- ou seja,
 a lista dos numeros yk seria aquela lista lah em cima. A soma dos yk tem
 que ser par (afinal, quando voce soma os yk's, voce estah contando o
 numero de amizades, soh que em dobro, porque cada amizade eh contada duas
 vezes -- estamos fazendo a hipotese aqui de que, se A eh amigo de B, entao
 B eh amigo de A). Como 68+68+68+69+69+69+...+101+101+101 = 17x169 eh impar,
 esta nao eh uma configuracao possivel. Acabou.

 Abraco,
Ralph

 2012/6/5 Mauricio de Araujo mauricio.de.ara...@gmail.com

 Amigos, gostaria de uma luz para fazer o problema abaixo:

 Cada um dos 102 estudantes ´e amigo de pelo menos 68 outros alunos. Prove
 que existem quatro
 estudantes com o mesmo n´umero de amigos.

 --
 --
 Abraços
 oɾnɐɹɐ ǝp oıɔıɹnɐɯ
 *momentos excepcionais pedem ações excepcionais*





-- 
-- 
Abraços
oɾnɐɹɐ ǝp oıɔıɹnɐɯ
*momentos excepcionais pedem ações excepcionais*

[obm-l] Problema de grafos

[Mauricio de Araujo]

Amigos, gostaria de uma luz para fazer o problema abaixo:

Cada um dos 102 estudantes ´e amigo de pelo menos 68 outros alunos. Prove
que existem quatro
estudantes com o mesmo n´umero de amigos.

-- 
-- 
Abraços
oɾnɐɹɐ ǝp oıɔıɹnɐɯ
*momentos excepcionais pedem ações excepcionais*

Re: [obm-l] Problema de grafos

[Ralph Teixeira]

Versao relampago:
casa-dos-pombos, 68,68,68,69,69,69,70,70,70,...,100,100,100,101,101,101,
contradicao.

Versao explicada:
Ha 101-67=34 numeros entre 68 e 101 (que sao os possiveis numeros de
amigos) de cada fulano.
Seja xi o numero de estudantes com i amigos (onde i=68,69,...,101). Note
que sao 34 numeros xi, cuja soma eh 102. Queremos provar que algum deles eh
maior ou igual a 4, certo?
Entao suponha por contradicao que todos eles sao menores ou iguais a 3.
Entao a soma eh no maximo 34x3=102, o que soh serah atingido se TODOS forem
iguais a 3. Entao chegamos aa conclusao de que o unico jeito do nosso
teorema furar seria se houvesse 3 alunos com 68 amigos, outros 3 com 69
amigos, e assim por diante, e 3 com 101 amigos, exatamente.

Agora seja yk o numero de amigos do fulano k (k=1,2,3,...,102) -- ou seja,
a lista dos numeros yk seria aquela lista lah em cima. A soma dos yk tem
que ser par (afinal, quando voce soma os yk's, voce estah contando o
numero de amizades, soh que em dobro, porque cada amizade eh contada duas
vezes -- estamos fazendo a hipotese aqui de que, se A eh amigo de B, entao
B eh amigo de A). Como 68+68+68+69+69+69+...+101+101+101 = 17x169 eh impar,
esta nao eh uma configuracao possivel. Acabou.

Abraco,
   Ralph

2012/6/5 Mauricio de Araujo mauricio.de.ara...@gmail.com

 Amigos, gostaria de uma luz para fazer o problema abaixo:

 Cada um dos 102 estudantes ´e amigo de pelo menos 68 outros alunos. Prove
 que existem quatro
 estudantes com o mesmo n´umero de amigos.

 --
 --
 Abraços
 oɾnɐɹɐ ǝp oıɔıɹnɐɯ
 *momentos excepcionais pedem ações excepcionais*