Grafos:Grafos:Matriz de adjacência e Matriz de incidênciaMatriz de adjacência e Matriz de incidência

Prof. Alex Camargoalexcamargoweb@gmail.com

UNIVERSIDADE FEDERAL DO PAMPACAMPUS BAGÉ

LABORATÓRIO DE PROGRAMAÇÃO II

Introdução

Uma noção simples, abstrata e intuitiva.

Representa a ideia de alguma espécie de relação entre “objetos”.

Graficamente representado por uma figura:

- com nós ou vértices, significando os objetos;

- unidos por um traço denominado aresta, configurando uma relação.

Laboratório de Programação II – Grafos

Representação matemática

Um Grafo é representado matematicamente por: G=(V,A)

V: os vértices ou nodos do grafo;

A: as arestas do grafo.

Laboratório de Programação II – Grafos

V = { Maria, Pedro, Joana, Luiz }A = { {Maria, Pedro} , {Joana, Maria} , {Pedro, Luiz} , {Joana, Pedro} }

O grafo G(V,A) dado por:

V = { p | p é uma pessoa } A = { (v,w) | < v é amigo de w > }

Dígrafo – grafo orientado

Laboratório de Programação II – Grafos

V = { Emerson, Isadora, Renata, Antonio, Cecília, Alfredo }A = {{Isadora, Emerson}, {Antonio, Renata}, {Alfredo, Emerson},{Cecília, Antonio}, {Alfredo, Antonio}}

G(V, A) definido por:

V = { p | p é uma pessoa da família Silva } A = { (v,w) | < v é pai/mãe de w > }

Arestas direcionadas

Ordem de um grafo

Laboratório de Programação II – Grafos

É o número de vértices de G.

ordem(G1) = 4 ordem(G2) = 6

Representação de grafos

Laboratório de Programação II – Grafos

Matriz de adjacência:

Uma linha para cada vérticeUma coluna para cada vértice

Formas de representação e matrizes associadas a um grafo:

Representação de grafos

Laboratório de Programação II – Grafos

Matriz de incidência:

Uma linha para cada vérticeUma coluna para cada aresta

Formas de representação e matrizes associadas a um grafo:

Exercícios

1. Faça um programa que peça o total de vértices e os elementos (0 ou 1) de um grafo e exiba sua matriz de adjacência.

Laboratório de Programação II – Grafos

Exercícios

2. Escrever em C o algoritmo que converte uma representação de um grafo orientado sob forma de matriz de adjacência em matriz de incidência.

Laboratório de Programação II – Grafos

Referências

Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. Algoritmos – teoria e prática. Rio de Janeiro: Campus, 2002.

http://www.dimap.ufrn.br/~dario/arquivos/Cap2_Grafos-2001.pdf

http://www.inf.ufsc.br/grafos/definicoes/definicao.html

Laboratório de Programação II – Grafos