jdact e cortesia de wikipedia
Grafos
«Basicamente, um “grafo” é um diagrama de um problema. O “grafo” para o
problema das pontes de Kônigsberg está representado a seguir.
O grafo para o problema das pontes de Kônigsberg.
jdact
Um “grafo” é constituído por vértices e arcos. Diz-se que percorremos,
ou traçamos, um “grafo” quando passamos uma única vez por todos os arcos.
Qualquer vértice pode ser cruzado as vezes que quisermos.
Na figura anterior os vértices do problema das pontes de Kônigsberg
estão designados por A, B, C, D. Repare no número de arcos que passam por cada
vértice - A tem 3, B tem 5, C tem 3 e D tem 3. Uma vez que todos os números são
ímpares, os vértices são vértices ímpares. Um vértice par terá um número par de
arcos a atravessá-lo.
Cortesia de wikipedia
Euler descobriu várias propriedades relacionadas com o número de
vértices pares e ímpares que um grafo pode ter para ser traçável.
Especificamente, notou que se existe um vértice ímpar é necessário começar, ou
acabar, o trajecto nesse vértice. Levando este facto em linha de conta,
concluiu que um grafo traçável só podia ter dois vértices ímpares, já que tem
apenas um ponto de partida e outro de chegada. Assim, já que no problema das
pontes existem quatro vértices ímpares, o grafo não pode ser percorrido.
jdact
Quais destes “garfos” são traçáveis? Podem ser percorridos sem passar
mais do que uma vez pelo mesmo arco.
jdact
Será possível desenhar um caminho que passe apenas uma vez por cada uma
das portas, sem levantar o lápis? Tente demonstrar a sua solução desenhando um “garfo”».
In Theoni Pappas, The
Joy of Mathematics, Fascínios da Matemática, Editora Replicação, Lda, 1ª
edição, 1998, ISBN 972-570-204-2.
Cortesia de Theoni Pappas/JDACT
