Grafos

Sávio Rodrigues

Introdução

A proposta do trabalho de Algoritmo e Estrutura de Dados II foi a representação de uma estrutura mínima de um grafo, a paritr dos conceitos apresentados na aula 7, sendo eles Lista de Adjacencia, Matriz de Adjacencia e Matriz de Incidência.

Apresentação

A teoria dos grafos ( ramo da matemática que estuda as relações entre os objetos de um determinado conjunto) é um assunto antigo, porém com várias aplicações no nosso dia-a-dia. No século XVIII o matématico suiço Leonard Euler utilizou os grafos para resolver o problemas que conhecemos como As Sete pontes de königsberg.

A imagem a seguir possui uma representação de grafo, onde os números representam os vértices (V = {0, 1, 2}) e as letras representam as arestas (A = {a, b ,c}).

Código

A seguir, têm-se o o código com as structs das três estruturas propostas com a inclusão da biblioteca Lista.h , a qual foi produzida em Algoritmo e Estrutura de Dados I.

#ifndef _GRAFOS_
#define _GRAFOS_
#include "Lista.h"


//LISTA DE ADIJACÊNCIA
typedef struct grafoLA {
  int V;       //Vértices 
  Lista *L;    //Lista de adjacencia
}*GrafoLA;

//MATRIZ DE INCIDÊNCIA
typedef struct grafoMI{
   int V;   //Vertices
   int A;   //Arestas
   int **mat;
}*GrafoMI;

//MATRIZ DE ADJACÊNCIA
typedef struct grafoMA{ 
   int V;      //Vertices
   int A;      //Arestas
   int **mat; 
}*GrafoMA;


#endif

Lista de Adjacência

Em literatura a lista de adjacência é uma representação, com todas as arestas ou arcos de um grafo em uma lista. Portanto possui os seguintes atributos:

• int V = Número de vértices
• Lista *L = Número de Arestas

O tipo Lista foi importado da biblioteca Lista.h simplesmente encadeada a qual possui funções de inserção,remoção e impressão de elementos.
A seguir tem-se a representação visual da lista de adjacência:

Matriz de Adjacência

A Matriz de Adjacêcia possui sua representação de grafo através de uma matriz bidimencional n x n.Portanto possui os seguintes atributos:

• int V = Número de vértices
• int A = Número de Arestas
• int **mat = Matriz de incidencia.

A seguir tem-se a representação visual dessa matriz:

Matriz de Incidência

Semelhante à matriz de adjacência, a de incidência possui uma representação de grafo através de uma matriz bidimencional. Porém uma das dimensões são arestas a outra são os vértices, ou seja uma matriz n x m. Portanto possui os seguintes atributos:

• int V = Número de vértices
• int A = Número de Arestas
• int **mat = Matriz de incidencia.

A seguir tem-se a representação visual dessa matriz:

Pode-se analisar que a matriz de incidencia possui o número -1, significando que o grafo é orientado e que o arco está chegando no vértice em questão.

Referencias

https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphdatastructs.html https://pt.wikipedia.org/wiki/Matriz_de_incid%C3%AAncia https://pt.wikipedia.org/wiki/Matriz_de_adjac%C3%AAncia