Re: [obm-l] problema do caminhao
Oi Fábio, Na Eureka! tem diversos artigos sobre grafos. Há muitos livros de grafos também, mesmo em português. Eu estudei o Bollobás (Graph Theory - An Introductory Course), que eu, em particular, adora mas acho bastante denso. Também tenho o Diestel (Graph Theory), que é um pouco menos denso. Ambos são em inglês e da Springer-Verlag. Mas devo avisar que os dois são bastante densos e têm foco mais em Matemática Pura do que em Aplicada. Para começar, recomendo ler antes os artigos da Eureka!. Se quiser, uma lista de todos os artigos da Eureka! (dá para fazer download) até a edição 17 está em http://www.obm.org.br/eureka/abstrac.htm []'s Shine --- fabiodjalma [EMAIL PROTECTED] wrote: Shine, infelizmente nunca estudei grafos. Poderia dar uma dica (livro, artigo ou página) onde eu possa compensar essa deficiência? Em (15:06:29), obm-l@mat.puc-rio.br escreveu: Que tal o caminho A-B-G-H-I-J-K-L-C-D-E-A? Veja que ele passa por todas as cidades e ainda pode voltar para A. O que você descreveu na verdade pode ser visualizado como um dodecaedro. Se você estudou teoria dos grafos, pode notar que o problema pede para provar a existência de um caminho (ciclo) hamiltoniano nesse grafo que é cúbico. Se não me engano (pode ser que eu esteja enganado), todo grafo conexo cúbico (todo vértice tem grau 3) admite um ciclo hamiltoniano. []'s Shine --- eritotutor wrote: Boa tarde, Considere um caminhão que abastece as cidades A, B , C, D, E, F, G, H, I, J, K , L. Duas cidades são adjacentes se existe um caminho entre elas. A é adjacente a B, J, E B é adjacente a A, C, G C é adjacente a L, B, D D é adjacente a E, C, H E é adjacente a D, A , F F é adjacente a L, E, G G é adjacente a H, F, B H é adjacente a I, G, D I é adjacente a K, J, H J é adjacente a K, I, A K é adjacente a J, I, L L é adjacente a K,C,F É possível que o caminhão saia da cidade A e percorra todas as cidades uma única vez? Justifique Desde já agradeço []s __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ Discover Yahoo! Find restaurants, movies, travel and more fun for the weekend. Check it out! http://discover.yahoo.com/weekend.html = 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 = -- Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html = 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 =
Re: [obm-l] problema do caminhao
Shine, infelizmente nunca estudei grafos. Poderia dar uma dica (livro, artigo ou página) onde eu possa compensar essa deficiência? Em (15:06:29), obm-l@mat.puc-rio.br escreveu: Que tal o caminho A-B-G-H-I-J-K-L-C-D-E-A? Veja que ele passa por todas as cidades e ainda pode voltar para A. O que você descreveu na verdade pode ser visualizado como um dodecaedro. Se você estudou teoria dos grafos, pode notar que o problema pede para provar a existência de um caminho (ciclo) hamiltoniano nesse grafo que é cúbico. Se não me engano (pode ser que eu esteja enganado), todo grafo conexo cúbico (todo vértice tem grau 3) admite um ciclo hamiltoniano. []'s Shine --- eritotutor wrote: Boa tarde, Considere um caminhão que abastece as cidades A, B , C, D, E, F, G, H, I, J, K , L. Duas cidades são adjacentes se existe um caminho entre elas. A é adjacente a B, J, E B é adjacente a A, C, G C é adjacente a L, B, D D é adjacente a E, C, H E é adjacente a D, A , F F é adjacente a L, E, G G é adjacente a H, F, B H é adjacente a I, G, D I é adjacente a K, J, H J é adjacente a K, I, A K é adjacente a J, I, L L é adjacente a K,C,F É possível que o caminhão saia da cidade A e percorra todas as cidades uma única vez? Justifique Desde já agradeço []s __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ Discover Yahoo! Find restaurants, movies, travel and more fun for the weekend. Check it out! http://discover.yahoo.com/weekend.html = 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 = --
[obm-l] problema do caminhao
Mas nesse caso, o caminhao não passa pela cidade F. Que tal o caminho A-B-G-H-I-J-K-L-C-D-E-A? Veja que ele passa por todas as cidades e ainda pode voltar para A. O que voc? descreveu na verdade pode ser visualizado como um dodecaedro. Se voc? estudou teoria dos grafos, pode notar que o problema pede para provar a exist?ncia de um caminho (ciclo) hamiltoniano nesse grafo que ? c?bico. Se n?o me engano (pode ser que eu esteja enganado), todo grafo conexo c?bico (todo v?rtice tem grau 3) admite um ciclo hamiltoniano. []'s Shine --- eritotutor <[EMAIL PROTECTED]>wrote: Boa tarde, Considere um caminh?o que abastece as cidades A, B , C, D, E, F, G, H, I, J, K , L. Duas cidades s?o adjacentes se existe um caminho entre elas. A ? adjacente a B, J, E B ? adjacente a A, C, G C ? adjacente a L, B, D D ? adjacente a E, C, H E ? adjacente a D, A , F F ? adjacente a L, E, G G ? adjacente a H, F, B H ? adjacente a I, G, D I ? adjacente a K, J, H J ? adjacente a K, I, A K ? adjacente a J, I, L L ? adjacente a K,C,F ? poss?vel que o caminh?o saia da cidade A e percorra todas as cidades uma ?nica vez? Justifique Desde j? agrade?o []s __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - ? gr?tis! http://antipopup.uol.com.br/ Discover Yahoo! Find restaurants, movies, travel and more fun for the weekend. Check it out! http://discover.yahoo.com/weekend.html = 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 =
Re: [obm-l] problema do caminhao
Se você estudou teoria dos grafos, pode notar que o problema pede para provar a existência de um caminho (ciclo) hamiltoniano nesse grafo que é cúbico. Se não me engano (pode ser que eu esteja enganado), todo grafo conexo cúbico (todo vértice tem grau 3) admite um ciclo hamiltoniano. Isso é falso... até mesmo se nos restringirmos a grafos cúbicos bipartidos 3-conexos, veja http://mathworld.wolfram.com/BicubicGraph.html Há a seguinte conjectura em aberto http://mathworld.wolfram.com/BarnettesConjecture.html [ ]'s = 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 =
[obm-l] problema do caminhao
Boa noite, Domingos, e demais colegas, cmo poderia mostrar então q o grafo não éhamiltoniano? Se você estudou teoria dos grafos, pode notar que o problema pede para provar a existência de um caminho (ciclo) hamiltoniano nesse grafo que é cúbico. Se não me engano (pode ser que eu esteja enganado), todo grafo conexo cúbico (todo vértice tem grau 3) admite um ciclo hamiltoniano. Isso é falso... até mesmo se nos restringirmos a grafos cúbicos bipartidos 3-conexos, veja http://mathworld.wolfram.com/BicubicGraph.html Há a seguinte conjectura em aberto http://mathworld.wolfram.com/BarnettesConjecture.html [ ]'s = 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 =
Re: [obm-l] problema do caminhao
Oi gente, Nossa, quando eu escrevi a outra mensagem eu me esqueci de um grafo cúbico que não é hamiltoniano muito familiar (pelo menos para mim): o grafo de Petersen, símbolo da OPM. Dicas de como demonstrar que esse grafo não é hamiltoniano estão em http://www.opm.mat.br/misc/petersen.php Lá também tem a história do grafo de Petersen, e exatamente como ele serviu como contra-exemplo em vários problemas. As dicas de como provar que o grafo não é hamiltoniano estão no final do artigo. Há três problemas lá também (sendo que um deles é exatamente provar que o grafo não é hamiltoniano). Momento propaganda: aproveitem e visitem o site da OPM, que está de cara nova! http://www.opm.mat.br/ []'s Shine --- eritotutor [EMAIL PROTECTED] wrote: Boa noite, Domingos, e demais colegas, cmo poderia mostrar então q o grafo não é hamiltoniano? Se você estudou teoria dos grafos, pode notar que o problema pede para provar a existência de um caminho (ciclo) hamiltoniano nesse grafo que é cúbico. Se não me engano (pode ser que eu esteja enganado), todo grafo conexo cúbico (todo vértice tem grau 3) admite um ciclo hamiltoniano. Isso é falso... até mesmo se nos restringirmos a grafos cúbicos bipartidos 3-conexos, veja http://mathworld.wolfram.com/BicubicGraph.html Há a seguinte conjectura em aberto http://mathworld.wolfram.com/BarnettesConjecture.html [ ]'s = 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 = __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ __ Do you Yahoo!? Make Yahoo! your home page http://www.yahoo.com/r/hs = 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 =
