Grafos podem ser definidos como modelos matemático que representam relações entre objetos, isto é, um conjunto de vértices e arestas interconectados ou não. Normalmente um Grafo é definido por G = (V, A), onde V é o conjunto de vértices (Não vazio) e A é o conjunto de arestas (Pode ser vazio).
Através dos Grafos podemos representar várias estruturas sistemáticas, tais como de redes sociais, encanamentos, redes elétricas, entre outras. Na computação os grafos servem de apoio para o desenvolvimento de algoritmos de busca.
Com os algoritmos de busca é possível explorar um conjunto de dados estruturados (listas, tuplas, vetores, matrizes…), percorrendo cada vértice através um processo que usa conceitos de busca em árvore.
Uma operação de busca pode visitar todos os vértices ou apenas um subconjunto de vértices de um Grafo. Aplicações que utilizam a tecnologia GPS fazem bom uso destes conceitos.
Principais tipos de busca em Grafos
Busca em profundidade: partindo de um vértice inicial, explora todo grafo antes de retroceder.
Busca em largura: partindo de um vértice inicial, explora todos os vértices vizinhos, em seguida, repete o processo para cada vértice vizinho.
Busca pelo menor caminho: partindo de um vértice inicial, calcula a menor distância desse vértice a todos os demais.
Propriedades de um Grafo
Grafo direcionado ou dígrafo
São Grafos que possuem uma orientação quanto ao sentido da aresta, isto é, se uma aresta liga A a B, pode-se ir de A para B, mas não de B para A.
Grafo não direcionado
São Grafos que não possuem orientação quanto ao sentido da aresta, isto é, pode-se ir de A para B e de B para A.
Grau do vértice
O Grau é o número de arestas que chegam ou partem. No caso dos dígrafos, temos:
- Grau de entrada (GE): arestas que chegam ao vértice;
- Grau de saída (GS): arestas que partem do vértice.
Na imagem acima, o vértice A possui GE = 0 e GS = 1. O vértice B possui GE = 2 e GS = 0. O vértice C possui GE = 0 e GS = 1.
Laço
Uma aresta é chamada de laço se seu vértice de partida for o mesmo que o vértice de chegada.
Cadeia
Uma cadeia é uma sequência qualquer de arestas adjacentes que ligam dois vértices. O conceito de cadeia vale também para Grafos orientados (dígrafos), bastando que se ignore o sentido da orientação dos arcos.
Na imagem acima existe a cadeia E, C, B, A.
Caminho
Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a Grafos orientados, podendo variar de comprimento dependendo o número de vértices.
Na imagem acima existe o caminho A -> B -> C -> E -> B.
Ciclo
É uma cadeia simples e fechada, isto é, um caminho que começa, passa por todos vértices e termina no vértice inicial.
Na imagem acima existe o ciclo A -> B -> C -> E -> B -> D -> A.
Tipos de Grafos
Nulo: é o Grafo cujo conjunto de vértices é vazio.
Trivial: é o Grafo que possui apenas um vértice e nenhuma aresta.
Vazio: é o Grafo cujo conjunto de arestas é vazio.
Regular: é um Grafo em que todo o vértice tem o mesmo grau.
Multigrafo: é um grafo que permite múltiplas arestas ligando os mesmos vértices, como por exemplo, o Grafo das Pontes de Königsberg, representado mais abaixo.
Simples: é um grafo que não contém nem laços nem arestas multiplas.
Completo: é um Grafo simples onde cada vértice se conecta a todos os outros vértices.
Conexo: é um Grafo que possui um caminho entre qualquer par de vértices, caso contrário, o Grafo é desconexo.
Bipartido: é um Grafo cujos vértices podem ser divididos em dois conjuntos.
Árvore de um Grafo
Para um Grafo ser uma árvore é preciso atender as seguintes condições:
- Possuir Vertices-1 arestas e nenhum ciclo;
- Possuir Vertices-1 arestas e ser ligado;
- Possuir apenas um caminho simples a unir quaisquer dois vértices;
- Deixar de ser ligado caso retirado uma só aresta.
Isto é, um Grafo conexo que não contém ciclos é chamado de árvore.
Arborescência e Floresta
As árvores de Grafos também podem ser representadas como Arborescência ou Floresta. Uma Arborescência é uma árvore que possui uma raiz (Aplicado somente a Grafos orientados). Já uma Floresta é um Grafo cujos componentes conexos são árvores.
Grafo Euleriano
É um Grafo que possui um caminho que visita cada aresta apenas uma vez, formando um Ciclo Euleriano.
Grafo Hamiltoniano
É um Grafo que possui um ciclo que contenha todos os seus vértices, sendo que cada vértice só aparece uma vez no ciclo. Este ciclo é chamado de Ciclo Hamiltonoano.
Problema das Pontes de Königsberg
No século 18 havia na cidade de Königsberg um conjunto de sete pontes (identificadas pelas letras de A até F na figura) que cruzavam o rio Pregel. Elas conectavam duas ilhas (A e D) entre si e as ilhas com as margens (B e C).
Por muito tempo os habitantes daquela cidade perguntavam-se se era possível cruzar as sete pontes numa caminhada contínua sem que se passasse duas vezes por qualquer uma delas.
Solução do problema das Pontes de Königsberg
É impossível fazer o caminho passando apenas uma vez por cada ponte, pois o que se nota é que o número de arestas partindo de cada vértice é ímpar, e para que o trajeto seja possível, é preciso partir um número par de arestas de cada um dos vértices. Pode-se resolver este problema mudando uma das pontes de lugar.
Problema do Caixeiro Viajante
Suponha que um caixeiro viajante tenha de visitar N cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.
Solução do problema do Caixeiro Viajante
Uma rota que o caixeiro viajante pode considerar é:
- Sair de A e ir para B;
- De B ir para C;
- De C ir para D;
- De D voltar para A.
Quais são as outras possibilidades? É muito fácil ver que existem seis rotas possíveis:
ABCDA – ABDCA – ACBDA – ACDBA – ADBCA – ADCBA
Conclusão
Os Grafos tem grande importância na área da informática, sendo úteis na representação de problemas sistemáticos ou abstratos. Com eles podemos representar um algoritmo ou uma sequência de processos, reescrevendo suas estruturas em um formato visual. Exemplos como os desafios da Ponte de Königsberg e do Caixeiro viajante se tornam mais entendíveis com a representação em Grafos, conforme visto no decorrer do texto.
Referência
Fundamentos da teoria dos grafos para computação.
