Universidade regional de blumenau



Baixar 1,07 Mb.
Página2/12
Encontro01.07.2018
Tamanho1,07 Mb.
1   2   3   4   5   6   7   8   9   ...   12

Introdução


Grafo é um tipo de estrutura de dados utilizada para representar relacionamentos entre pares de objetos. Basicamente é formado por um conjunto de vértices e uma coleção de conexões entre pares de vértices, chamadas de arestas (GOODRICH; TAMASSIA, 2007, p. 508). Ao longo do tempo a teoria dos grafos evoluiu muito e diversos problemas práticos e teóricos podem ser reduzidos a um modelo de grafos, que, com o auxílio de teoremas e algoritmos, podem levar a conclusões e soluções acerca destas questões. Segundo Skiena e Revilla (2003, p. 237), a chave para solucionar problemas consiste em identificar o grafo fundamental oculto àquela situação e utilizar algoritmos clássicos para resolver a questão resultante.

Porém, há uma enorme gama de propriedades e algoritmos de grafos a serem estudados e implementados. Muitas implementações são simples, outras são mais complexas e podem demandar horas de pesquisa, especificação e desenvolvimento. Em termos de desenvolvimento de aplicações isso pode desviar o objetivo do desenvolvedor, que não é de realizar tais implementações, mas sim, por meio de um conhecimento prévio, apenas utilizar chamadas de funções de bibliotecas já prontas. Sendo assim, alguém que eventualmente sabe a aplicabilidade de determinado algoritmo envolvendo grafos pode não querer implementá-lo, mas sim apenas modelar o grafo, chamar a execução do algoritmo e trabalhar com a resposta fornecida. Hoje isto é possível graças a orientação a objetos, que tem como uma de suas características a reusabilidade de código, permitindo a integração de classes desenvolvidas por terceiros em uma aplicação.

Nesse momento aparece um outro desafio: a criação de casos de teste utilizando instâncias de grafos contendo muitos vértices e arestas, ou um tipo específico com base em algumas restrições. Muitas vezes é necessário gerar tais grafos a fim de testar mais profundamente a aplicação e avaliar seu desempenho e bom funcionamento.

Diante da falta de uma ferramenta que contemple todos estes requisitos, surge a ideia de desenvolver um framework1 de grafos, que permita gerar grafos mediante critérios, editar os existentes e que seja capaz de extrair diversas propriedades importantes e executar algoritmos clássicos. Além disso, faz-se necessário ter uma boa documentação, bem como uma aplicação exemplo para demonstrar a utilização dos recursos oferecidos pelo framework.


    1. OBJETIVOS DO TRABALHO


O objetivo deste trabalho é construir um framework para auxiliar no desenvolvimento de softwares baseados em teoria dos grafos.

Os objetivos específicos do trabalho são:



  1. disponibilizar um conjunto de algoritmos clássicos de grafos, entre os quais citam-se: Dijkstra, Floyd-Warshall, Bellman-Ford, Prim, Kruskal, Ford-Fulkerson, Hopcroft-Tarjan, ordenação topológica, busca em largura e busca em profundidade;

  2. permitir extrair algumas importantes propriedades do grafo, tais como: completo, regular, trivial, nulo, bipartido, bipartido completo, conexo ou desconexo, fortemente conexo, denso ou esparso e simples ou multigrafo;

  3. permitir gerar instâncias de grafos com base em restrições, como grafos completos com n vértices, grafos regulares de n vértices e grau k, grafos densos, esparsos, conexos ou desconexos e simples ou multigrafos;

  4. persistir os grafos;

  5. documentar o framework;

  6. disponibilizar uma aplicação exemplo para demonstrar a utilização das funções do framework.
    1. estrutura do trabalho


O trabalho está estruturado em quatro capítulos. No segundo capítulo é apresentada a fundamentação teórica necessária para o entendimento do trabalho. Nele são expostos os principais conceitos relacionados a teoria dos grafos, as propriedades de grafos e também os algoritmos clássicos utilizados na teoria dos grafos para resolver diversos problemas práticos e teóricos. Além disso, neste capítulo, na seção de trabalhos correlatos, são mencionadas ferramentas existentes no mercado e desenvolvidas em trabalhos de conclusão de curso com funcionalidades semelhantes às do framework. No terceiro capítulo é mostrado o desenvolvimento do sistema. Nesse capítulo pode ser encontrado os requisitos e especificação do trabalho, como também a descrição dos algoritmos implementados e os resultados obtidos. Por fim, no quarto capítulo são descritas as conclusões encontradas e as extensões sugeridas para trabalhos futuros.
  1. FUNDAMENTAÇÃO TEÓRICA


A seguir são explanados os principais conceitos relacionados à estrutura básica de um grafo. Na sequência são expostas as principais propriedades de grafos, com exemplos em figuras para melhor compreensão. Logo em seguida são detalhados os principais algoritmos clássicos de grafos, bem como suas aplicações. Por fim, em trabalhos correlatos, são mencionadas ferramentas existentes no mercado e desenvolvidas em trabalhos de conclusão de curso com funcionalidades semelhantes às do FGA.
    1. conceitos básicos da teoria DOS grafos


Um grafo pode ser definido como um par ordenado G = (V, E), sendo V um conjunto finito e não vazio e E uma relação binária sobre V. Os elementos que pertencem a V são chamados de vértices ou nós, enquanto que os pares não-ordenados de E são denominados de arestas ou arcos (RABUSKE, 1992, p. 5).

Um grafo dirigido G = (V, E) é definido por um conjunto não vazio V de vértices e um conjunto E de arestas, onde cada aresta e  E é definida por um par ordenado de vértices (u, v), sendo ambos u e v  V . O vértice u é o vértice origem, e v é o vértice destino da aresta e (RABUSKE, 1992, p. 7). Um exemplo de grafo dirigido e outro de um grafo não dirigido podem ser vistos na Figura 1.

A representação gráfica padrão de um grafo é um desenho formado por pontos, que representam os vértices, e por retas ou arcos conectando os pontos, que são as arestas (GROSS; YELLEN, 2006, p. 2).

Vértices que pertencem a uma mesma aresta são denominados vizinhos ou adjacentes. Uma aresta que conecta somente um vértice é chamada de laço e duas arestas diferentes que possuem os mesmos vértices, tanto de origem como de destino, são chamadas de paralelas (FEOFILOFF; KOHAYAKAWA; WAKABAYASHI, 2009).

Uma aresta também pode possuir atributos. Um atributo pode ser um valor numérico que, para Rabuske (1992, p. 12) é chamado de peso, distância ou custo. Tais atributos representam alguma quantidade física em problemas envolvendo transportes, redes de transmissão de dados, entre outros.

Outra definição importante é o grau de um vértice, que segundo Feofiloff, Kohayakawa e Wakabayashi (2009), é o número de arestas que incidem em um vértice. Scheinerman (2003, p. 423) classifica um vértice como isolado se o seu grau é igual a zero. Para Rabuske (1992, p. 10), um vértice pode ser chamado de pendente se o seu grau for um.



Em grafos dirigidos o grau de um vértice pode ser classificado em grau de saída, que representa a quantidade de arestas que partem de um vértice, e grau de entrada, que é a quantidade de arestas que atingem o vértice (RABUSKE, 1992, p. 32).

Fonte: adaptado de Gross e Yellen (2006, p. 2).

Figura 1 – Exemplo de um grafo dirigido (a) e um grafo não dirigido (b)

Um caminho é uma sequência alternada de vértices e arestas sendo que o vértice final de uma aresta é o vértice inicial da aresta seguinte no caminho. Um caminho inicia em um vértice e pode terminar tanto no mesmo vértice de partida como em outro qualquer. Quando os vértices de início e fim são os mesmos o caminho é chamado de ciclo ou de caminho fechado. Um grafo que não possui ciclo e é conexo, pode ser chamado de árvore e um conjunto de árvores é uma floresta (GOODRICH; TAMASSIA, 2004, p. 296).

Outra informação importante a respeito de grafos dirigidos é a base e a antibase (Figura 2). Base é o conjunto de vértices que não podem ser alcançados partindo-se de qualquer outro vértice do grafo, ou seja, os vértices de grau de entrada igual a zero. Já, a antibase é o conjunto de vértices que não alcançam nenhum outro vértice, isto é, os vértices de grau de saída igual a zero (RABUSKE, 1992, p. 32).

Estes dados têm utilidade em problemas organizacionais, onde é possível encontrar, por exemplo, as pessoas que teriam alguma autoridade sobre outras pessoas, e também encontrar as pessoas que estão submetidas a outras, conforme ilustrado na Figura 2 (RABUSKE, 1992, p. 33).



Fonte: adaptado da definição de Rabuske (1992, p. 32).

Figura 2 – Exemplo de base (A e B) e antibase (F, G, H e I)

Pontes e nós de articulação (Figura 3) também fornecem outras propriedades interessantes. Uma ponte é uma aresta, que, no caso de ser removida torna o grafo desconexo, e, por sua vez, um nó de articulação é um vértice, que, caso removido do grafo também torna o grafo desconexo (CORMEN et al., 2001, p. 558).



Estas informações têm aplicações úteis em, por exemplo, redes de distribuição elétrica, onde os postes podem representar os nós de articulação e os cabos de energia podem representar as pontes (CORMEN et al., 2001, p. 558).

Fonte: adaptado de Cormen et al. (2001, p. 559).

Figura 3 – Exemplo de uma ponte (a) e três nós de articulação (b)



1   2   3   4   5   6   7   8   9   ...   12


©livred.info 2017
enviar mensagem

    Página principal