Colorir Grafos é Coisa de Gente Grande

O que é um grafo? Se você nunca ouviu falar nisso antes, esta é certamente uma pergunta que você deve estar se fazendo. Vamos tentar matar sua curiosidade contando como foi que a teoria dos grafos surgiu. A história afirma que a teoria dos grafos começou na cidade de Konigsberg em 1736 pelo grande matemático suiço Leonhard Euler. A cidade era cortada pelo rio Pregel, que possuía duas ilhas. 

Como era muito complicado fazer o transporte de cargas e pessoas através de barcos, sete pontes foram construídas para auxiliar neste deslocamento entre as ilhas e as duas margens. Após algum tempo, as pessoas começaram a se perguntar se era possível sair de sua casa, passar por cada ponte uma única vez e voltar para a segurança de seu lar. 

Para resolver o problema, Euler montou um diagrama que representasse o mapa da cidade. Ele o fez da seguinte maneira: A cada ilha e margem ele associou a um ponto, que chamaremos de vértice e a cada ponte uma ligação, que chamaremos de aresta. Essa figura com vários pontos (vértices) e algumas ligações (arestas) é o que denominamos de grafo. Para finalizar seu raciocínio, Euler percebeu que existiam vértices com exatamente três arestas incidentes. 

Por outro lado, como os moradores queriam atravessar cada ponte apenas uma única vez, cada vértice deveria ter um número par de arestas. Logo, se tornaria impossível fazer um percurso  2 seguindo essas regras impostas pelos moradores. No entanto se o número de pontes fosse, digamos seis, haveria tal possibilidade. Hoje, a teoria dos grafos estuda objetos combinatórios – grafos- que são um bom modelo para muitos problemas em vários ramos da matemática, da computação, da engenharia, da química, da psicologia e até da indústria. Ao caminhar pelas ruas você poderá visualizar as aplicações, da teoria dos grafos na resolução de problemas de elaboração de horários, sinalização de trânsito, alocação de tarefas e transporte de bens.

No programa de hoje conversamos com a professora Cláudia Linhares Sales, professora titular do Departamento de Computação da Universidade Federal do Ceará (UFC), sobre teoria dos grafos! Ao longo do programa vamos esclarecer o que é a Teoria dos Grafos, sua conexão com a computação, as aplicações (como o estudo de coloração) e também falamos sobre a história da professora Cláudia.