O Centro Multidisciplinar de Angicos

[pic 1]

Teoria do Grafos

Ciro Emanuel Almeida Silva

Jarlyson Andre dos Santos

Luan Diego da Silva Nunes

Luiz Felipe da Cunha Silva

Mauricio Ricardo Barreto Nicácio

Wesley dos Santos Silva

Universidade Federal Rural do Semi-Árido (UFERSA)

Centro Multidisciplinar de Angicos

Bacharelado em Sistema de Informação

Interdisciplinar em Ciência e Tecnologia

{[e-mail]}

{[e-mail]}

{[e-mail]}

{[e-mail]}

{[e-mail]}

{[e-mail]}

Resumo. O presente trabalho tem como objetivo a realização de uma pesquisa bibliográfica a respeito do tema Teoria dos Grafos. Nesse contexto, o trabalho aborda uma pequena retomada histórica a respeito do tema, bem como, a descrição de alguns dos principais conceitos básicos referentes à temática. Além disso, foi realizada a implementação de uma lista de adjacências e uma matriz de adjacências, com o intuito de melhorar o entendimento dos principais conceitos envolvidos no estudo de Grafos. Também é importante mencionar, que foi abordado alguns dos problemas que foram importantes no desenvolvimento da teoria, além de mostrar algumas das principais aplicações da teoria dos grafos na área da computação. Desse modo, foi possível observar a importância da teoria dos grafos no âmbito matemático e, principalmente, no estudo da computação.

1. Introdução

        A teoria dos grafos tem como conceito, basicamente, o estudo da relação entre os objetos de um determinado conjunto. Com base nisso, o seu surgimento é tido como relativamente recente (século XVIII), teve o seu devido desenvolvimento no período do século XX, desse modo, a sua importância se deve ao grande número de aplicações que esse campo permite sendo bastante utilizado na área da computação.

        Nesse contexto, pode-se salientar que a teoria dos grafos foi desenvolvida na cidade de Koenigsegg, pelo matemático Leonhard Euler o qual seu objetivo era resolver um problema relacionado a algumas pontes que existiam nesta cidade, problema que ficou conhecido como Problema das quatro pontes de Koenigsegg e teve fundamental importância no desenvolvimento da teoria.

        Matematicamente é possível representarmos um grafo da seguinte forma:

[pic 2]

Tal que, V são os vértices e E são as arestas.

        Desse modo, o objetivo deste trabalho é entendermos um pouco sobre os conceitos referentes à teoria dos grafos, bem como estudar sobre as suas representações, aplicações e etc. Assim, deixando claro a utilidade desta teoria na área da computação e suas ramificações.

2. Conceitos básicos

Para que possamos entender melhor do que se trata a teoria dos grafos é importante estudarmos um pouco dos seus conceitos mais básicos, de modo que posteriormente estes conceitos nos serviram de base para a compreensão de termos mais complexos dentro dessa área.

2.1. O que é um grafo?

        Pode-se dizer que um grafo é um conjunto de pontos chamados vértices ligados por arestas, de modo que cada aresta liga uma extremidade. Com base nisso, podemos observar a imagem abaixo:

[pic 3]

Figura 1: Exemplo de grafo composto por vértices e arestas.

        Como vemos na imagem acima, as arestas (linhas que ligam cada ponto) são ligadas ao vértice (pontos as quais as linhas estão ligadas), de modo que é construída uma figura que chamamos de grafo.

2.2. Grafos simples

        Podemos dizer que um grafo é simples quando este não possui arestas paralelas, além disso, um grafo simples não possui arestas com pontas coincidentes, como podemos observar na figura abaixo:

[pic 4]

Figura 2: Grafo simples.

2.3. Grafos direcionados

        Um grafo direcionado é um grafo o qual suas arestas indicam uma determinada direção, como podemos observar na figura abaixo:

[pic 5]

Figura 3: Grafo direcionado.

Como observamos na figura acima, cada aresta do grafo representa uma determinada direção em relação ao vértice, o grafo da figura pode ser representado da seguinte forma:

[pic 6]

[pic 7]

[pic 8].

Observa-se, que a indicação das arestas é feita relacionando-as com os respectivos pares de vértices fazendo a ligação através da direção determinada.

2.4. Grafos não direcionados

        Basicamente, os grafos não direcionados são o inverso dos grafos direcionados de modo que sua representação não faz a indicação da direção da aresta, como podemos ver na imagem abaixo:

[pic 9]

Figura 4: Grafo não direcionado comparado com grafo direcionado.

2.5. Multigrafos

        De maneira geral um multigrafo é quando temos múltiplas arestas entre pares de vértices em um determinado grafo, como podemos observar na figura:

[pic 10]

Figura 5: Multigrafo com 4 vértices.

No exemplo da Figura 5, há duas arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o como um multigrafo.

2.6. Grafos com pesos

        Os grafos com pesos podem ser definidos como grafos que possuem pesos em suas arestas, este peso é representado por um determinado valor numérico dado aquela aquela aresta de modo que indique alguma grandeza referente a representação do grafo. Nesse contexto, a imagem abaixo representa um grafo com peso:

[pic 11]

Figura 6: Representação de grafo com pesos.

        Este tipo de grafo é utilizado quando se quer chegar em uma solução econômica, ou seja, será usado o caminho com a menor soma de preço. No grafo da Figura 6, por exemplo, o menor caminho de 0 a 3 não é a aresta 0–3, mas sim a aresta 0–2 e depois a aresta 2–3.

2.7. Grafos cíclicos

        Pode-se dizer que um grafo cíclico ou circular é quando o grafo consiste em um único círculo ou um número de vértices que são conectados em uma rede fechada. Conforme a figura abaixo: