As sete pontes de Königsberg

Sete pontes de Königsberg

Grafo estilizado das sete pontes de Königsberg

Sete pontes de Königsberg é um famoso problema histórico da matemática resolvido por Leonhard Euler em 1736, cuja solução originou a teoria dos grafos.

Retrato de Leonhard Euler,

O problema é baseado na cidade de Königsberg (território da Prússia até 1945, atual Kaliningrado), que é cortada pelo Rio Prególia, onde há duas grandes ilhas que, juntas, formam um complexo que na época continha sete pontes, conforme mostra a figura ao lado. Das sete pontes originais, uma foi demolida e reconstruida em 1935, duas foram destruídas durante a Segunda Guerra Mundial e outras duas foram demolidas para dar lugar a uma única via expressa. Atualmente apenas duas pontes são da época de Leonhard Euler.

Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes sem repetir nenhuma. Havia-se tornado uma lenda popular a possibilidade da façanha quando Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.

Euler usou um raciocínio muito simples. Transformou os caminhos em retas e suas intersecções em pontos, criando possivelmente o primeiro grafo da história.

Grafo de Königsberg

Então percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse exatamente zero ou dois pontos de onde saísse um número ímpar de caminhos. A razão de tal coisa é que de cada ponto deve haver um número par de caminhos, pois será preciso um caminho para "entrar" e outro para "sair". Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de um para entrar e um para sair, respectivamente. Se não houver pontos com número ímpar de caminhos, pode-se (e deve-se) iniciar e terminar o trajeto no mesmo ponto, podendo esse ser qualquer ponto do grafo. Isso não é possível quando temos dois pontos com números ímpares de caminhos, sendo obrigatoriamente um o início e outro o fim.

Duas das sete pontes originais da cidade foram destruídas durante o bombardeamento de Königsberg em agosto de 1944.
Origem: Wikipédia, a enciclopédia livre.

Ilha das sete pontes da antiga Königsberg (atual Kaliningrado)

Kaliningrado - Federação Russa - Imagem Google earth

Kaliningrado

Origem: Wikipédia, a enciclopédia livre.

Caliningrado ou Kaliningrado (em russo: Калининград, tradução: em Inglês: Kaliningrad; em polaco: Królewiec; em lituano: Karaliaučius) é a capital da província russa homônima, enclave russo entre a Polonia e a Lituânia, à beira do Mar Báltico. Fundada em 1255 pelos Cavaleiros Teutónicos sob o nome de Conisberga (em alemão: Königsberg, "montanha do rei"), foi de 1466 a 1656 parte da Polonia. Também foi a capital da Prússia Oriental, e depois fez parte do Império Alemão a partir de 1871. 

Famosa por ter tido entre os seus habitantes o filósofo Immanuel Kant, a cidade também é célebre pelo problema das sete pontes de Königsberg, resolvido por Euler em 1736. 

Seu nome é uma homenagem ao revolucionário bolchevique Mikhail Kalinin.

História

A Região de Kaliningrado foi formada em 1945. Durante a Conferência de Potsdam com a União Soviética, os Estados Unidos e a Grã-Bretanha sobre a Eliminação da Prússia Oriental, a parte norte de lá após a Segunda Guerra Mundial passou para União Soviética.

A cidade e sua população sofreram no final da Segunda Guerra Mundial os severos bombardeamentos aliados, sendo bastante devastada. Após a Guerra, foi rebatizada para "Caliningrado" (do nome do presidente do Comité Central do Partido Comunista, Mikhail Kalinin), quando a União Soviética anexou os territórios da região de Caliningrado.

O problema das pontes de Königsberg.

Uma tentativa de solução "pegadas" é traçada (pontos na cor vermelho escuro). Neste caso, apenas cinco pontes foram cruzadas e o pedestre está de volta em casa. Se em seguida, uma sexta ponte é atravessada (pontos na cor cinza), não é possível voltar para casa. Todas as sete pontes não podem ser percorridas num único caminho sem repetir uma delas.

Mapa: Baedeker, Atlas do Norte da Alemanha, 1890.

Mapas Históricos

Mapa de Königsberg de 1905

Mapa de Königsberg - mapa da cidade - 1887

Mapa de Königsberg - Meyers b9 s1020a
Livro 9 da 4ª edição do Meyers Konversationslexikon

Teoria dos grafos

Origem: Wikipédia, a enciclopédia livre.

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G (V, A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.

Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de links da Wikipédia pode ser representada por um digrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Digrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.

Histórico

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. 

É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

Definições de grafos e digrafos

Na literatura, as definições básicas da teoria dos grafos variam bastante. Aqui estão as convenções usadas nesta enciclopédia.

Um grafo direcionado (também chamado digrafo ou quiver) consiste de

• um conjunto V de vértices;
• um conjunto E de arestas e;
• mapas s, t: E → V, onde s(e) é a fonte e t(e) é o alvo da aresta direcionada e.

Um grafo não direcionado (ou simplesmente grafo) é dado por

• um conjunto V de vértices;
• um conjunto E de arestas e;
• uma função w: E → P(V) que associa a cada aresta um subconjunto de dois ou de um elemento de V, interpretado como os pontos terminais da aresta.

Em um grafo ou digrafo com pesos, uma função adicional E → R associa um valor a cada aresta, o que pode ser considerado seu "custo"; tais grafos surgem em problemas de rota ótima tais como o problema do caixeiro viajante.

Glossário dos conceitos básicos de teoria dos grafos

Um grafo com 6 vértices e 7 arestas

Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta.

Note que essa representação gráfica (o layout) não deve ser confundida com o grafo em si (a estrutura abstrata, não gráfica). Vários diferentes layouts podem corresponder ao mesmo grafo. O que importa é quais vértices estão conectados entre si por quantas arestas.

O grafo de exemplo exibido à direita é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (com o mapeamento w sendo a identidade). 

Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta. A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas. Em um digrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada. 

Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjacentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5. Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência. 

Na computação, um grafo finito direcionado ou não direcionado (digamos com n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornecem o número de arestas do i-ésimo ao j-ésimo vértices. 

Se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo, diz-se que o grafo é conexo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então se diz que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e, portanto 1-conexo), mas não é 2-conexo. 

Em um grafo genérico G, o corte associado a um conjunto X de vértices é o conjunto de todas as arestas que têm uma ponta em X e outra em V(G)-X, onde V(G) é o conjunto de todos os vértices pertencentes ao grafo G.

Tipos de grafos 

Grafo simples é um grafo não direcionado, sem laços e que existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

Em teoria dos grafos, um grafo é simples se ele não tem laços nem mais de uma aresta ligando dois vértices. 

Em grande parte dos textos o adjetivo simples (ou regular) é omitido estando, no entanto, subentendido. Um grafo que não é simples, diz-se um multigrafo.

Número de arestas

Número de arestas

O número de arestas de um grafo simples G é expresso por:

Grafo completo é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

Um grafo completo é um grafo simples em que todo vértice é adjacente a todos os outros vértices. O grafo completo de n vértices é frequentemente denotado por kn. 

Número de arestas

O grafo Kn tem arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

Planaridade

O teorema de Kuratowski tem como consequência que um grafo Kn é um grafo planar se e somente se Kn ≤ 4.

Grafo K4 plano

Grafo com 4 vértices e 6 arestas. 

É um grafo completo, conexo e planar.

Grafo bipartido completo

Grafo bipartido completo

Existem vários outros tipos de grafos conforme consta em:
Fonte: http://pt.wikipedia.org/wiki/Teoria_dos_grafos