21. Pontes e grafos

  Como um passatempo de atravessar pontes de uma cidade criou todo um ramo novo da Matemática.

pkma  A cidade de Kaliningrad é uma cidade na Rússia. Na verdade, é uma cidade num exclave da Rússia, entre a Polónia e a Lituânia, situada a 510 quilómetros da Rússia, com 15 mil e 100 m2 e perto de 1 milhão da habitantes. Um enclave é um território estrangeiro rodeado por um único outro país. Um exclave é um território nacional separado geograficamente da maioria do país. Assim, Kaliningrad é um exclave da Rússia. Não é um enclave porque faz fronteira com 2 países: Polónia e Lituânia. Após a 2.ª Guerra Mundial, a região urbana de Königsberg passou a fazer parte da Rússia e o seu nome foi mudado, em 1946, para Kaliningrad como homenagem ao recém-falecido Mikhail Kalinin, um dos primeiros bolcheviques. Há alguns factos curiosos ligados ao passado alemão da cidade: o filósofo alemão Immanuel Kant (1724-1804) era natural de lá; o matemático alemão Christian Goldbach (1690-1764) era também natural de lá; o matemático alemão David Hilbert (1862-1943) residiu lá, apesar de ser natural de Wehlau, cidade na Prússia Oriental com capital em Königsberg; a cidade foi fundada, em 1255, pelos Cavaleiros Teutónicos e só deixou de ser alemã após a 2.ª Guerra Mundial, em 1945, passando a integrar a Rússia.

prssUm outro facto relevante relacionado com Kaliningrad prende-se com a cidade que anteriormente se chamava Königsberg (“montanha do Rei” em Alemão). Berlim era a capital da Prússia (atualmente o norte da Alemanha, norte da Polónia, a Lituânia, Letónia e Estónia), o estado alemão que unificou todos os outros estados germânicos no final do século XIX para formar a Alemanha, até então um conjunto de estados independentes cada um com o seu Rei. Juntos formaram o Império Alemão, tendo como soberano o Kaiser prussiano Wilhelm II. A Alemanha entrou na Grande Guerra para honrar o pacto que tinha com o Império Austro-Húngaro (que iniciou a Grande Guerra). Perderam-na e a Alemanha tornou-se uma república. Até que Hitler chegou ao poder. Após a derrota na 2.ª Guerra Mundial a Alemanha foi dividida em 2: a Alemanha Federal (a união dos sectores de ocupação inglesa, francesa e americana) e a Alemanha Democrática (o sector de ocupação soviética). Além disso, perdeu importantes partes do seu território. A Prússia, elemento unificador da Alemanha, foi dividida entre a Polónia e a Rússia. Könisberg passou a ser uma cidade russa e mudou de nome para Kaliningrad.

7pontesMas, no século XVIII, era prussiana. A cidade foi construída à volta do rio Pregel. A meio do rio há uma ilha chamada Kniephof. Para unir todas as partes da cidade foram construídas 7 pontes. Os habitantes da cidade gostavam de passear pelas pontes e tentavam encontrar uma forma de atravessar todas as pontes apenas uma vez. Mas, por muito que tentassem, não conseguiam encontrar um forma. Os nomes das 7 pontes de Königsberg eram: Kraemer «lojista»; Schmiede «ferreiro»; Holz «madeira»; Honig «mel»; Greune «verde»; Koettel «entranha»; Hohe «alta/o»;

grafo-euler   Pediram então ajuda a um grande Matemático suíço, de nome Euler «ói+lâ». Este começou por analisar o problema focando-se nos pontos relevantes e descartando os desnecessários (a típica abordagem matemática). Para isso simplificou o esquema das pontes: cada terreno a atingir seria um ponto e cada ponte o traço que os unia e tudo o mais era desnecessário à resposta. Este tipo de rede (pontos e ligações) chama-se um grafo. Com este esquema verificou ser impossível atravessar cada ponte uma única vez. Como todos os 4 pontos tinham um número ímpar de traços, qualquer caminho único depois de atravessar uma delas só conseguiria passar para um lado e não conseguiria regressar. Desta forma Euler criu um novo ramo da Matemática (a Topologia, que estuda as características que não são alteradas quando são distorcidas ou esticadas sem rasgar), mostrou que era impossível esse caminho pelas pontes da cidade e criou a Teoria dos Grafos, que é o estudo das
redes de pontos unidos. Um resultado importante desta Teoria é: Num grafo, para que haja um caminho que une todos os pontos uma só vez apenas 2 deles podem ter um gr_imp_posnúmero ímpar de ligações (o ponto inicial e o ponto final) ou têm todos um número par de ligações. Como se vê no esquema, os 4 pontos do Grafo das pontes de Konisberg, têm ligações ímpares. É impossível percorrer todas as pontes apenas uma vez.

ptkg Mas os grafos com 2 pontos com ligações ímpares têm solução. Um dos mais conhecidos é o da Casa Cruzada. Como se constata facilmente, apenas 2 pontos têm ligações ímpares (os da base), pelo que é possível traçar a casa uma única vez sem passar 2 vezes pela mesma linha. Várias soluções são possíveis e é apresentada uma delas. O início do trajecto é o ponto inferior esquerdo e o fim o inferior direito, que são os pontos com ligações ímpares. As soluções começarão num ou noutro ponto (ímpar). A Teoria dos Grafos fornece também o método para os encontrar mas só o facto de permitir saber de antemão se um dado desenho se pode fazer de uma vez é uma óptima ajuda.

pks   Um método de resolução é:                                     numerar os vértices do grafo; em seguida constrói-se uma tabela onde são colocados os vértices; representa-se nessa tabela as arestas que unem os diferentes vértices; verifica-se quais os vértices ímpares (se os houver); escolhe-se um vértice para começar a resolução. Se houver 2 ímpares é um deles, se não houver qualquer um pode ser escolhido; verifica-se qual a primeira aresta livre na linha do vértice escolhido; marca-se essa aresta (2 vezes, uma vez que 2-5 é a mesma que 5-2); na linha do vértice onde a aresta anterior se liga marca-se a primeira aresta livre;   repete-se até todas as arestas estarem escolhidas.

grafo_casa_pontos_solucao   No exemplo acima dado, uma forma de desenhar o grafo é unir os vértices:  4 – 2 – 1 – 3 – 2 – 5 – 3 – 4 – 5. Não é a única forma de desenhar este grafo mas de certeza que este método indica uma delas. Escolhendo outros vértices neste método (e desde que se garanta que todas as arestas foram escolhidas) obtêm-se outras formas. No grafo ao lado, outra solução é 4-1-3-5-2-3-4-5

   Durante a 2.ª Guerra Mundial,  a cidade e as suas 7 pontes foram destruídas, tendo sido reconstruídas apenas 5 das pontes originais (e mais outra acrescentada). Eis as 6 pontes que existem atualmente:

kaliiningrad

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *