COMPUTAÇÃO NA ESCOLA

Grafos

Como sabes, no século XVIII a Internet ainda não tinha sido inventada e, por isso, as pessoas tinham de procurar outras formas de entretenimento. Algumas ocupavam o tempo a jogar xadrez; outras preferiam assistir a execuções públicas de criminosos. Enfim, há gostos para tudo... até para resolver problemas de matemática!

ENSICO(Texto)

O famoso Problema das Sete Pontes de Königsberg foi resolvido em 1736 por um grande matemático chamado Leonard Euler, tendo a sua solução inspirado, séculos depois, resultados numa área da matemática conhecida por Teoria de Grafos.

Na cidade de Königsberg, situada na antiga Prússia, corria o boato de que seria possível atravessar todas as pontes da cidade exatamente uma vez.

A figura abaixo esquematiza a posição destas sete pontes.

No entanto, Euler demonstrou que não era possível executar tal façanha, reformulando o problema em termos abstratos. De facto, podemos representar cada região por um ponto e cada ponte unindo duas regiões por uma linha, obtendo uma figura semelhante a esta, que designamos por grafo:

A observação fundamental é que todos os pontos são incidentes com um número ímpar de linhas. Mas, se pensares um pouco, hás de reparar que a existência de um caminho atravessando todas as linhas uma única vez só seria possível se houvesse no máximo dois pontos incidentes com uma quantidade ímpar de linhas... Não acreditas? Podes encontrar a prova aqui 😊

Agora deves estar a pensar: o que tem isto a ver com Ciências da Computação? A resposta é simples: os grafos constituem uma das estruturas de dados mais importantes em computação, servindo para modelar imensas situações da vida real. E olha que os grafos são como as batatas fritas – existem em várias formas e feitios!

Por exemplo, ao invés de pontos e linhas, podem ser constituídos por pontos e setas, ou seja, atribui-se uma orientação a cada linha. Na figura abaixo encontras um grafo deste género, que pretende modelar as relações entre vários utilizadores no Instagram:

Por exemplo, a expressão Maria > Isabel indica que a Maria segue a Isabel no Instagram; a expressão Joana > Pedro indica que a Joana segue o Pedro, etc.

Para analisarmos estas relações de forma eficiente, gostaríamos de representar este grafo num computador. Como podemos fazer isso? Tal como no artigo que escrevemos sobre o DICIONÁRIO, vamos representar este grafo como uma sequência de pares, em que, por exemplo, o par (Maria, Isabel) ilustra o facto da Maria seguir a Isabel no Instagram. Obtemos então a seguinte sequência, a que chamamos simplesmente “instagram”:

Grafos com etiquetas

Imagina agora que pretendemos também registar no grafo em que ano é que uma pessoa começou a seguir outra. Para tal, basta colocarmos etiquetas em cima das setas com o ano em questão:

Ficamos assim a saber que, em 2018, a Maria começou a seguir a Isabel e a Joana começou a seguir o Rui. Como é que podemos transmitir estas informações extra ao computador?

É muito simples: basta agora considerarmos uma sequência de pares em que cada par é do tipo ((pessoa, pessoa), ano). Sim, é um par com outro par dentro, mas o computador lida bem com isso! Vamos chamar a esta nova sequência “instagram”:

Deste modo, poderíamos agora implementar vários algoritmos num computador para analisar esta rede social e responder a questões como: “Qual é o número médio de seguidores de cada utilizador?”, “No ano de 2021, que novas relações foram estabelecidas?”, etc. Claro que, se considerarmos apenas estas 10 pessoas, é fácil respondermos a estas perguntas “à mão”. Mas acredita que a tarefa se torna bem mais complicada se tivermos de lidar com todos os mil milhões de utilizadores que estão registados no Instagram! Meu amigo, aí só mesmo um computador é que nos salva... 😩

Antes de continuarmos, vamos pôr à prova as tuas capacidades de interpretação desafiando-te a responder às seguintes questões, com base nos grafos e/ou sequências acima.

1. Quem está a seguir que pessoas no Instagram há mais tempo?

2. Qual é a pessoa mais popular?

3. Que pessoas são seguidas há menos tempo por alguém?

4. Se a Isabel decidir abandonar o Instagram, como é que fica a sequência "instagram"? E o respetivo grafo?

Mãos à obra

Para não pensares que os grafos só servem para modelar redes sociais, vamos mostrar-te que podem até ser utilizados para planear as obras de uma casa.

Não sabemos se a tua está a precisar de obras ou não, mas, em caso afirmativo, os grafos fornecem um diagrama prático para determinares durante quanto tempo vais ter de ouvir a harmoniosa melodia de uma rebarbadora...

No grafo ao lado, a expressão paredes > telhado etiquetada com um “5” indica que:

as paredes levarão 5 semanas a erguer, e que
o telhado só pode começar quando as paredes estiverem acabadas.

As restantes expressões e respetivas setas (e etiquetas) transmitem informações análogas.

Há muitas outras situações da vida real em que os grafos são a ferramenta ideal para as analisar.

Por exemplo, podemos considerar um grafo constituído pelos vários locais de Portugal e distâncias entre eles e, de seguida, tentar conceber um algoritmo para determinar o caminho mais curto entre dois desses locais. Pode vir a dar jeito da próxima vez que planeares uma road trip com os teus pais ou amigos! E, por determinares a rota ideal a seguir, achamos que mereces ter o direito de escolher as músicas que vão tocar durante a viagem... 😏

A mãe de todas as redes

No mundo computorizado que é o nosso, a presença de grafos no quotidiano é tão vasta que podemos mesmo afirmar que sem eles o mundo não seria o mesmo. É, por exemplo, a estrutura matemática que regista o facto de “estarmos todos ligados”, isto num mundo que se quer global. É igualmente a base utilizada na gestão e otimização de grande parte das redes – redes elétricas, redes de água, redes de gás, redes sociais, redes de transporte, etc. Uma das imagens mais icónicas associada a estas redes é talvez a da planta do metro de Londres.

Mas há mais, muito mais a saber sobre grafos, sobre a sua origem e sobre o seu futuro. E por isso a ENSICO se associou ao PÚBLICO na Escola, nesta parceria intitulada «Computação na Escola».

Colaboração de Mano a Mano Graphic Design Club

[Às quintas-feiras, o PÚBLICO na Escola dá espaço às ciências da computação, numa parceria com a ENSICO - Associação para o Ensino da Computação.]

António Machiavelo, professor e investigador em matemática na Faculdade de Ciências da Universidade do Porto (FCUP), está aqui para te ajudar a entender um pouco melhor porque é que esta área do conhecimento, com trabalhos matemáticos marcantes a partir do século XVIII e com um forte impacto nas ciências da computação, continua a assumir uma importância vital nas sociedades modernas.