Re: [obm-l] Problema de grafos
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
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
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 =