A Teoria dos Grafos

Grafos

Muitas, talvez várias vezes, está palavra, “grafo”, talvez você já tenha ouvido essa palavra, mas, e sua definição, você conhece? Sabe seus métodos e atributos que pode definir essa palavra? É o que temos a lhe mostrar nesta edição os seus deveres e atribuições.

Grafo é um conjunto cujos elementos são unidos por arcos, no ramo da tecnologia da informação, o grafo é um conteúdo magnífico de estrutura de dados, pois através dele, pode-se chegar a um arquivo, variável, objeto, endereço etc... Outras aplicações em que são utilizadas são nos circuitos elétricos, processos industriais, processo de negócio, telecomunicações, mapeamentos, entre muitos outros. Um grafo só é considerado um se tiver pelo menos um vértice, se houver apenas uma aresta sozinha, não é considerado um grafo.

Um grafo dirigido é formado por um conjunto finito de vértices e um conjunto finito de arestas, sendo que, uma aresta liga uma aresta a seu próprio vértice ou liga dois vértices. O conceito de um grafo não dirigido é um grafo na qual as arestas são pares não ordenados.

Um exemplo de um grafo, que contém os vértices representados na figura abaixo pelos círculos azuis, e as arestas pelas linhas de cada um.

[pic 1]

Figura 01 – Grafo direcionado

Como na imagem, o grafo representa que é dirigido, como saber disto? Simples, se parar para ver, as arestas contidas na figura contém algumas setas que apontam para um determinado vértice, por exemplo o vértice v5 está ligado com uma aresta dirigida ao v6 pois há uma seta avisando que está indo somente naquela direção, ou como o v1 apontando para o v4 seu sentido de direção, ora, imagine agora, como se cada aresta dirigida fosse uma pista de rua com sentido único, sim, é possível comparar com esse critério, imagine como se os vértices fossem pontos ou bairros de uma cidade, e que as arestas fossem os caminhos de direção única para esses bairros, então o bairro v9 tem caminho e direção para o bairro v4 e para o caminho v7, v4 não tem setas de saída mas tem caminhos de recebimento de v1, v5 e v9, e o v3 que tem caminho para v2 e v5, e é recebido pelo caminho que sai do bairro  v7.

Da imagem anterior, o grafo que iremos mostrar na imagem a seguir, mostraremos uma estrutura um pouco diferente, veja a imagem a seguir:

                                    [pic 2]

Figura 02 – Grafo não direcionado

Note que diferentemente da estrutura da imagem anterior, esta imagem não tem arestas de direcionamento, possui as arestas, mas não tem nenhuma delas apontando direção.

Ora, então se não há direcionamento, significa que mesmo assim estes vértices podem ser considerados interligados? Afirmativo, diferentemente do grafo da figura 01, na figura 02, vemos que não possui arestas direcionadas então o 2 pode estar interligado com o 5 quanto o 5 interligado ao 2.

Voltando ao exemplo dos bairros que são interligados por estradas, só que agora utilizando a figura 02, imaginem agora como se cada aresta representasse uma via de mão dupla (duplo sentido de direção), então, observando-se a imagem, vemos que o bairro 2 tem mão dupla para 1 e 5, o 6, tem caminho de mão dupla para os bairros 3, 4 e 5, e assim cada um sucessivamente.

Matrizes e listas de adjacência

Ambos, matrizes e listas tem algo em comum, estes servem para guardar ou ser informado sobre todas as possibilidades possíveis que um grafo tem, como, quantos vértices possui o                                                                       grafo, no grafo, quantas arestas tem? E quais vértices podem estarem ligadas uma com as outras?

Isto pode ser representado utilizando esses dois métodos, e iremos começar falando a respeito da matriz.

Matrizes de adjacência

Este é representado por uma matriz quadrada onde a matriz é possuída por quadrados tanto na vertical quanto na horizontal, parecendo aquela planilha do Excel por exemplo lembra?

Iremos utilizar o exemplo da figura 02 e mostrar os resultados na figura 03.

[pic 3]

                                        Figura 03 – matriz

Na figura 03 podemos ver claramente uma matriz que representa o grafo da figura 02, se perceber-nos, onde na matriz estiver com o número 1 em vermelho, representa um valor entre os números associados a esquerda e acima do quadro. No caso do número vermelho, ele representa um sinal positivo, que sim, há uma aresta interligando os valores fora do quadro. No caso do primeiro um vermelho, este diz que realmente há uma ligação entre o vértice 1 e o vértice 2, que se irmos para a figura 02, podemos ver que é verdade. Outro padrão não podemos deixar de notar que é a quantidade de valores contidos dentro da matriz, na quantidade podemos notar que há 16 elementos (16 caminhos diferentes), e se olharmos para notar, a quantidade de elementos na matriz, é o dobro do número de arestas de um grafo não direcionado.

[pic 4]

Figura 04 – Grafo dirigido

Se o grafo fosse um grafo dirigido como por exemplo na figura 04, a matriz iria se suceder desta forma:

[pic 5]

Como podemos notar, na matriz anterior se sucede que como mostra na figura 04, tem suas arestas dirigidas, ou seja, direcionadas de um vértice a outro. Como todas as arestas no grafo contém direcionamento, na matriz permanece a quantidade de resultados a mesma quantidade de arestas. No caso, poderia conter um grafo misto de arestas direcionadas e não direcionadas, porém altera-se os seus valores na matriz dependendo das informações.

...