Resumo MACS - Grafos

Introdução

Muitas vezes as grandes descobertas surgem das mais humildes e inesperadas origens. É esta a ideia matemática a desenvolver neste trabalho, o estudo matemático de como as coisas estão interligadas.
A noção de grafo aparece geometricamente quando se pensa em linhas e extremos de linhas: toda a figura formada com estes elementos pode ser encarada como um grafo. Algébricamente, a noção de grafo aparece quando se associa a um conjunto qualquer uma relação binária, em particular uma relação de ordem.
É portanto perfeitamente natural que a ciência se tenha debruçado sobre esta noção e não só a procurasse definir em termos matemáticos como também a tenha utilizado ao serviço das aplicações práticas. De facto é um conceito fundamental a que expressamente recorrem hoje investigadores que trabalham em domínios variadíssimos.

Um pouco de história...

A nossa história começou há mais de 250 anos atrás na cidade medieval Königsberg na Europa oriental.
Königsberg era dividida pelo rio Pregel em quarto áreas de terras distintas que estavam ligadas por sete pontes.
Um mapa de Königsberg desenhado pelo cartografo Martin Zeiller mostra a disposição da antiga cidade em 1736. Um dia um brilhante jovem matemático Leonhard Euler passou por lá e ouviu um pequeno e inocente enigma de uma simplicidade extrema:
“É possível que uma pessoa ao dar um passeio pela velha cidade consiga passar uma e uma só vez por cada ponte? ”
Os habitantes locais tentaram fazê-lo vezes sem conta mas sem sucesso. Será que Euler conseguiria provar matemáticamente que tal não é possível?
Faremos posteriormente uma abordagem mais pormenorizada a este problema.

Conceitos básicos

Grafo: Entidade matemática (G) constituída por um conjunto V de elementos vi chamados vértices e por um conjunto P de pares ordenados ou não [vi,vj] de elementos de V que denominamos por aresta. Se [vi,vj] forem pares ordenados dizemos que G