Teoria dos Grafos

As pontes de Königsberg

No século 18 havia na cidade de Königsberg um conjunto de sete pontes que cruzavam o rio Pregel. Elas conectavam duas ilhas entre si e as ilhas com as margens.

Por muito tempo os habitantes daquela cidade perguntavam-se se era possível cruzar as sete pontes numa caminhada contínua sem passar duas vezes por qualquer uma delas.

As pontes de Königsberg

Você consegue fazer o caminho das 7 pontes sem repetir nenhuma?

As pontes de Königsberg

Representando o problema em forma de grafo.

Grafo - Conceito

"Um grafo G é um par ordenado G=(V,E) onde V é um conjunto (finito) de elementos e E é um conjunto de dois subconjuntos de V."

Nós e Arestas

Nó ou vértice : representado por um ponto ou círculo.

aresta ou arco : representada por um traço que liga dois nós.

Exemplo

Outro Exemplo