domingo, 27 de fevereiro de 2011

Solucionando o problema das 3 casas através da Teoria do Grafos - FINAL




Eis o desfecho da solução:

Se cada região tem no mínimo grau 4 e se há 5 regiões, então a soma dos graus (SG) será no mínimo 5.4=20, logo o grafo terá no mínimo 10 arestas:

20=2A
2A=20
A=20/2
A=10

 (lembre-se que SG=2A, ou seja, a soma dos graus é igual ao dobro do número de arestas).

Mas sabemos que o nosso grafo deverá ter 9 arestas, logo o que obtemos foi uma contradição.

Portanto não existe um grafo planar com 6 vértices, 9 arestas e 5 regiões, em outras palavras, o grafo é não planar: as arestas irão se cortar (ou cruzar, ou intersectar ou passar uma por cima da outra).

Então, ainda que você fique a eternidade desenhando jamais vai obter sucesso, pois o problema de construir a figura é insolúvel.

O argumento resumido é este:

Supondo que seja possível, o desenho pretendido deverá ser um grafo planar. Mas se tal grafo existir e for planar, então:

(i) O grafo deverá possuir 6 vértices e 9 arestas e 5 regiões.

(ii) Cada região terá no mínimo grau 4.

(iii) A soma dos graus das faces será igual ao dobro das arestas.

(iv) Como conseqüência de (i) e (ii) concluímos que a soma dos graus será no mínimo 5.4=20.

(v) Como conseqüência de (iii) e (iv) concluímos que o grafo deverá ter pelo menos 10 arestas.

Partimos do princípio de que o grafo deverá ter 9 arestas e fazemos a suposição de ele ser planar. Então concluímos, por meio de procedimentos matemáticos legítimos, que o grafo deverá ter no mínimo 10 arestas, o que evidentemente é uma contradição. Portanto, o único elo fraco da argumentação deve necessariamente ser a suposição de o grafo ser planar, logo o grafo não é planar.

Referência:

LIPSCHUTZ, Seymour; LIPSON, Marc L. Teoria dos Grafos. In: Teoria e Problemas de Matemática Discreta2. ed. Porto Alegre: Bookman, 2004. (p.188-228)

*Qualquer crítica ao conteúdo apresentado pode ser feita aqui.

PS: a referência citada contém erros gráficos (assim como edições de outros livros da mesma coleção), contudo é acessível gratuitamente.

9 comentários :

  1. então e o desenho ?

    ResponderExcluir
    Respostas
    1. Desculpe, não entendi o seu comentário. Será que você não está conseguindo visualizar as figuras? Se for o caso, sugiro que acesse o blog de um computador e utilize o navegador chrome.
      Pedro R.

      Excluir
  2. Poxa vida! então este desafio não tem solução??? ou seja, não tem como ligar água, luz e energia para as três casa???

    ResponderExcluir
  3. Isso mesmo Anônimo, não tem solução! Abraço. Pedro R.

    ResponderExcluir
  4. Eu apresentei uma resposta em 3D ao meu professor e consegui passar de ano...
    Não acredito que simplesmente não possa ser feito, só tem que ter um pouco de criatividade =)

    ResponderExcluir
    Respostas
    1. como foi me diz vai la cara se conseguir eu passo de ano eu te eneploro

      Excluir
    2. como foi me diz vai la cara se conseguir eu passo de ano eu te eneploro

      Excluir

Arquivo do BLOG MANTHANO

Atualizações dos nossos parceiros: