(4) Introdução à Teoria dos Grafos: Representação de um grafo

Prévia do material em texto

Introdução à Teoria dos Grafos 
 
Representação de um grafo 
 
Há 2 maneiras principais de representar grafos: matriz de adjacência (ou de vértices) e lista de 
adjacência (ou de vértices). Cada uma tem seus benefícios e situações em que são mais vantajosas. 
Nosso foco será na forma matricial. 
 
• A Matriz de Adjacência (ou Matriz de Vértices) consiste em uma matriz N x N onde N é o 
número de vértices do grafo e as linhas representam de onde a aresta sai e as colunas para 
onde as arestas vão. 
 
• O valor 1 em uma certa linha ou coluna representa que existe uma aresta da linha para a 
coluna, e o valor 0 a ausência dessa aresta. 
 
(1) Exemplo de grafo e sua representação matricial: 
 
 
 
(2) Exemplo de grafo e sua representação matricial: 
 
 
 
 
Referências bibliográficas: 
 
ANTON, Howard; RORRES, Chris. Álgebra linear com aplicações. 10ª ed. Porto Alegre: Bookman, 
2012. XV, 768 p. ISBN 9788540701694. 
 
BOLDRINI, José Luiz, Álgebra Linear, 3ª edição, São Paulo: Harper & Row do Brasil, 1980.