Re: [obm-l] Problema das Quatro Cores (Teoria dos Grafos)
Entendi... de certa forma estou usando o que quero provar pra fazer a prova, né? Valeu! Hugo. Em 17 de setembro de 2011 23:51, Johann Dirichlet escreveu: > Existe uma demonstração fácil de que 5 cores bastam para pintar um grafo > planar. > Acho que este é seu problema: tentar provar por absurdo algo que se > provaria diretamente. > Certamente, se você usa 4 cores para piontar, alguém que tem um > estoque de 5,6,7,2002 cores também consegue. > > Mas o salto lógico é este: > Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 > nós ligados entre si. > > Se isto não for corretamente demonstrado, adeus demonstração! > > > > Em 17/09/11, Hugo Fernando Marques Fernandes > escreveu: > > Olá, Lista. > > > > Seguinte, estava lendo sobre o "problema das quatro cores", que segundo > > entendi é um teorema da teoria dos grafos que afirma que se pode colorir > > qualquer grafo planar com quatro cores de modo que nós adjacentes (ou > seja, > > que possuam aresta ligando-os) não sejam pintados da mesma cor. > > > > Consta que tal fato permaneceu por séculos sem demonstração, e a que > existe > > hoje depende de recursos computacionais para ser completada, o que > levanta > > dúvidas sobre a mesma. > > > > Minha pergunta então, é a seguinte: > > > > Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 nós > > ligados entre si, isto é, eu teria que ter um sub-grafo do meu grafo > inicial > > que fosse um grafo completo de 5 nós (K5). Ora, sabemos (é fácil > demonstrar, > > já vi em vários livros a demonstração) que K5 não tem realizações > > planares... logo, o teorema segue. > > > > Sei que isso está errado (afinal de contas, se não estivesse, alguém > teria > > visto de cara e o problema não teria ficado séculos em aberto...) mas não > > consigo ver onde está o erro desse raciocínio. Alguém pode me ajudar? > > > > Obrigado. > > > > > -- > /**/ > 神が祝福 > > Torres > > = > 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] Curvas e Equações
Ué, Felipe! Nenhuma restrição de grau? De nada? Acho que não entendi sua pergunta, pois há uma infinidade de curvas que passam por quaisquer n pontos dados. Por exemplo a "curva" (x-x1)(x-x2)...(x-xn) = (y-y1)(y-y2)...(y-yn) passa pelos pontos (x1, y1), (x2, y2),...(xn, yn). Melhor ainda, passa por todos os pontos com x = qq uma das n abscissas e y = qq uma das n ordenadas dos pontos dados. Viajei? Abraços, Nehab Em 16/9/2011 11:40, luiz silva escreveu: Prezados, Alguém sabe se exsite algum teorema que defina as condições para que, dado um conjunto de n pontos (no R2, por exemplo), exsita uma equação para a curva Cx,y que passe por estes pontos. Abs Felipe
Re: [obm-l] Problema das Quatro Cores (Teoria dos Grafos)
Existe uma demonstração fácil de que 5 cores bastam para pintar um grafo planar. Acho que este é seu problema: tentar provar por absurdo algo que se provaria diretamente. Certamente, se você usa 4 cores para piontar, alguém que tem um estoque de 5,6,7,2002 cores também consegue. Mas o salto lógico é este: Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 nós ligados entre si. Se isto não for corretamente demonstrado, adeus demonstração! Em 17/09/11, Hugo Fernando Marques Fernandes escreveu: > Olá, Lista. > > Seguinte, estava lendo sobre o "problema das quatro cores", que segundo > entendi é um teorema da teoria dos grafos que afirma que se pode colorir > qualquer grafo planar com quatro cores de modo que nós adjacentes (ou seja, > que possuam aresta ligando-os) não sejam pintados da mesma cor. > > Consta que tal fato permaneceu por séculos sem demonstração, e a que existe > hoje depende de recursos computacionais para ser completada, o que levanta > dúvidas sobre a mesma. > > Minha pergunta então, é a seguinte: > > Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 nós > ligados entre si, isto é, eu teria que ter um sub-grafo do meu grafo inicial > que fosse um grafo completo de 5 nós (K5). Ora, sabemos (é fácil demonstrar, > já vi em vários livros a demonstração) que K5 não tem realizações > planares... logo, o teorema segue. > > Sei que isso está errado (afinal de contas, se não estivesse, alguém teria > visto de cara e o problema não teria ficado séculos em aberto...) mas não > consigo ver onde está o erro desse raciocínio. Alguém pode me ajudar? > > Obrigado. > -- /**/ 神が祝福 Torres = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Problema das Quatro Cores (Teoria dos Grafos)
Olá, Lista. Seguinte, estava lendo sobre o "problema das quatro cores", que segundo entendi é um teorema da teoria dos grafos que afirma que se pode colorir qualquer grafo planar com quatro cores de modo que nós adjacentes (ou seja, que possuam aresta ligando-os) não sejam pintados da mesma cor. Consta que tal fato permaneceu por séculos sem demonstração, e a que existe hoje depende de recursos computacionais para ser completada, o que levanta dúvidas sobre a mesma. Minha pergunta então, é a seguinte: Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 nós ligados entre si, isto é, eu teria que ter um sub-grafo do meu grafo inicial que fosse um grafo completo de 5 nós (K5). Ora, sabemos (é fácil demonstrar, já vi em vários livros a demonstração) que K5 não tem realizações planares... logo, o teorema segue. Sei que isso está errado (afinal de contas, se não estivesse, alguém teria visto de cara e o problema não teria ficado séculos em aberto...) mas não consigo ver onde está o erro desse raciocínio. Alguém pode me ajudar? Obrigado.
