TEORIA DE GRAFOS APLICADA A MANIPULAÇÃO DE ESTRUTURAS COM CARACTERÍSTICAS DE LIGAÇÕES ENTRE PONTOS

Resumo

Este trabalho tem como objetivo apresentar um pouco sobre a teoria de grafos, muitas vezes estudada como estrutura de dados ou algoritmos, onde por meio de estudo matemático são aplicadas relações entre os objetos de  determinados conjuntos variados. Por exemplo, imaginemos o seguinte problema: um cliente de uma loja quer saber que rota seguir do ponto ''X'', sua casa, ao ponto ''Y'', que é a loja mais próxima, sendo que quer pegar a rota mais curta o possível. A teoria de grafos é bem mais ampla, porém se aplica a problemas de gêneros parecidos ao deste exemplo. Grafos são modelos de dados que armazenam e facilitam a manipulação de estruturas com características de ligações entre pontos, podendo utilizar duas estruturas de dados: vetores e listas encadeadas. As listas encadeadas podem ser mais rápidas em questão de acesso, mas na maioria dos casos é mais fácil usar os vetores, quando na maioria dos artigos com algoritmos usa-se exemplos com vetores. O grafo possui dois vértices (ponto ''A'' e ponto ''B''), ligados por uma aresta (ligação entre A e B). O número de arestas incidentes num vértice traduz o grau desse vértice. O subconjunto de arestas e vértices a elas associados diz-se um sub-grafo do grafo original. Existem inúmeros exemplos de conjuntos com um número finito de elementos nos quais existe uma relação entre os elementos do conjunto. Por exemplo, o conjunto poderia consistir de uma coleção de pessoas, animais, países, companhias, equipes esportivas ou cidades; a relação entre dois elementos ''A'' e ''B'' de um tal conjunto poderia ser que: o animal ''A'' alimenta-se do animal ''B'', o país ''A'' apóia militarmente o país ''B'', a companhia ''A'' vende seus produtos para a companhia ''B'' ou a cidade ''A'' possui vôo sem escala para a cidade ''B''. A forma mais prática de trabalhar com um grafo é “traduzindo” as suas estruturas em matrizes. Tendo em vista o grande número de informações que um grafo pode conter e a necessidade de se extrair dados de suas propriedades, um estudo que relacione uma matriz e um grafo é o campo mais proveitoso. A teoria de grafos é classificada como um ramo fortemente ligado a álgebra e a teoria de matrizes, também tem sido aplicada a muitas áreas como informática, investigação operacional, economia, sociologia, genética, etc., pois um grafo constitui o modelo matemático ideal para o estudo das relações entre objetos discretos de qualquer tipo.