TEORIA DOS GRAFOS E APLICAÇÔES
Resumo
A teoria dos grafos é um ramo da Matemática Discreta que estuda objetos denominados grafos. O pioneiro desta teoria é o matemático suíço Leonhard Euler (1707-1783), que formulou e resolveu o problema das pontes de Königsberg, o qual surgiu como desafio e acabou por contribuir para o desenvolvimento teórico e prático acerca dos grafos.
Um grafo pode ser definido como uma estrutura, onde é um conjunto discreto e ordenado de pontos chamados vértices e um conjunto de linhas chamadas arestas, onde cada aresta está conectada em pelo menos um vértice. Com a idéia de pontos interligados por linhas, a representação por grafos pode facilitar o entendimento e a resolução de problemas. Desta forma, um mapa da estrutura organizacional de uma empresa, redes de rotas de transporte, redes de comunicação, rotas de distribuição de produtos ou serviços e estruturas químicas de uma molécula, podem ser expressos através de grafos.
Apesar de ser um tópico muitas vezes não contemplado nos currículos da formação dos profissionais de Matemática, a teoria dos grafos aborda conceitos da teoria de grupos, de matrizes, da análise numérica e da probabilidade, possibilitando a modelagem de problemas com enunciado simples mas que escondem, muitas vezes, uma sofisticada estrutura matemática.
De modo geral, o estudo sobre grafos vem crescendo nas últimas décadas, devido a sua aplicabilidade em diversos problemas práticos em diferentes áreas como na Matemática, nas Engenharias, na Indústria e no Comércio.
Dentre as classes de problemas abordados por esta teoria, pode-se destacar a utilização do modelo conhecido como o problema de coloração, que busca colorir os vértices de um grafo, de modo que vértices adjacentes apresentem cores distintas, utilizando para isto o menor número possível de cores. Através do problema de coloração, consegue-se modelar um grande número de situações, pois ele consiste em particionar os vértices de um grafo em conjuntos, onde seus elementos apresentam características comuns, que pode ser a cor, a numeração, ou outras. Para exemplificar suas aplicações, podem ser citados os problemas de elaboração de horários, sinalização de trânsito, alocação de tarefas e transporte de bens.
Assim, o trabalho proposto está baseado na exposição de aspectos históricos e conceitos acerca da teoria dos grafos, bem como apresentação de alguns problemas concretos que possam ser modelados e resolvidos através do problema de coloração, com intuito de divulgar esta teoria enquanto assunto abordado pela Matemática Discreta.