Grafos E Suas Aplicaçoes

Grafos e Suas aplicações

INTRODUÇÃO

A teoria de grafos surgiu no século XVIII e, comparada com a história da Matemática, ela é bastante recente. Destacam-se L. Euler, G. Kirchhoff e A. Cayley como os primeiros cientistas a trabalharem nesta linha de pesquisa.

A teoria de grafos tem extensa aplicabilidade na área de Matemática,

principalmente na modelagem matemática, que permite interpretar e analisar

várias situações reais em Física, Química, Biologia, Engenharia, Pesquisa Operacional, Psicologia e Teoria da Computação.

Nestes textos, encontram-se todos os resultados e propriedades importantes da teoria bem como um grande número de aplicações em várias áreas do conhecimento.

Com o desenvolvimento da ciência da computação, a teoria sobre grafos tem permitido obter resultados importantes de modelos matemáticos que representam várias situações reais e auxiliam na solução de diversos problemas.

Um grafo é um conjunto de pontos no plano ligados por segmentos de reta ou flechas. Um grafo G = (N,A) é constituído por um conjunto (finito e não-vazio) N de nós e um conjunto A de arcos. Cada arco é um par nãoordenado de nós (ou vértices) distintos.

Para desenhar um grafo, representa-se cada nó por um círculo e os

arcos por linhas ligando estes círculos.

Um arco é incidente nos nós aos quais está associado. Nó isolado é

aquele que não está ligado a nenhum outro, ou seja, não existe nenhum arco, no grafo, incidente neste nó.

Multigrafos são grafos nos quais são permitidos dois ou mais arcos

associados a um mesmo par de nós. O exemplo na figura 4 representa um

multigrafo porque os arcos b e c conectam os mesmos pontos finais.

Pode-se representar (multi)grafos por meio de matrizes. Tem-se então a matriz de incidência nó-arco, cujas linhas estão associadas aos nós e as colunas aos arcos. Um elemento na linha i e coluna j será igual a 1 se o nó i for incidente no arco j e 0 se não for. Outra forma de representação é a

matriz de adjacência, que tem linhas e colunas associadas aos nós. O elemento na linha i e coluna j é o número de arcos que tem i e j como extremidades.

Um circuito de Euler do grafo G é um circuito que contém todos os

nós e todas as arestas de G. Isto é, o circuito euleriano é uma seqüência de

nós adjacentes a qual começa e termina no mesmo nó, usando cada nó pelo

menos uma vez e cada aresta também uma única vez. Sendo N um nó do

circuito euleriano de G, se uma aresta chega em N, então deverá haver outra

que sai. Um dos resultados estabelecidos por Euler diz que um multigrafo

conexo é euleriano se, e somente se, cada nó tiver grau par.

O conceito de planaridade de um grafo está ligado ao traçado de mapas

de cidades. Considerando-se o mapa de uma cidade, a ele pode estar

associado a cada esquina um nó e a cada trecho de rua entre duas esquinas

um arco. Entretanto, se o objetivo for traçar possíveis rotas para linhas de

ônibus, verifica-se que a simples indicação de um trecho de rua entre dois

pontos não é suficiente, porque nem todas as ruas possuem mão-dupla. É

necessário também acrescentar essa informação na definição do grafo. Então

surge o conceito de arco direcionado e dígrafo. Cada arco corresponde a

um par ordenado de nós. Agora, o arco correspondente ao par (i, j) é incidente

do nó i e incidente para o nó j. O grau de entrada de um nó é o número de

arcos que entram no nó, isto é, são incidentes para o nó e o grau de saída é

definido de maneira análoga.

Seguindo a teoria de grafos, da mesma forma, a definição de dígrafos

não prevê a existência de laços (um arco associado a um par (i, i)) e arcos

repetidos, ou seja, dois arcos associados ao mesmo par ordenado de nós.

Outra informação adicional que pode ser representada no arco, é informar

sua direção, e esta é indicada por meio de uma seta no nó.

PROBLEMAS E APLICAÇÕES

O mais famoso problema que utiliza teoria de grafos foi resolvido por Euler em 1736. Euler ficou curioso devido a uma charada popular sobre o lugarejo de Königsberg (uma antiga cidade da Prússia, mais tarde chamada de Kaliniingrado, na Rússia). O problema é o seguinte: sete pontes cruzam o

rio Pregel estabelecendo ligações entre duas ilhas e entre as ilhas e as margens opostas do rio, como mostra a figura. A charada era determinar se uma pessoa poderia passear pela cidade passando apenas uma vez por cada ponte.

É viável responder essa pergunta listando todos os caminhos possíveis, de

forma que algum dedicado morador de Königsberg deve ter resolvido este

problema em particular. A idéia de Euler foi representar esta situação utilizando grafos.

Este problema consiste

em achar um circuito que percorra cada arco exatamente uma vez. Pode-se

observar que os nós têm grau ímpar, então o multigrafo em questão não é

euleriano. A resposta à pergunta é que não é possível cruzar uma ponte

somente uma vez.

A resposta a este problema pode também ser encontrada na construção

de um algoritmo computacional. A essência do algoritmo é contar o