PESQUISA OPERACIONAL

Disciplina: Teoria dos Grafos

Matriz de Adjascência

Matriz de Adjascência

Uma Matriz de Adjacência é uma das formas de se representar um grafo.

Dado um Grafo G com n Vértices, podemos representá-lo em uma Matriz n x n A(G)=[aij] (ou simplesmente A). A definição precisa das ENTRADAS da matriz que varia de acordo com as propriedades do grafo que se deseja representar, porém de forma geral o valor aij guarda informações sobre como os vértices vi e vj estão relacionados (isto é, informações sobre a adjacência de vi e vj).

Para representar um Grafo Não-Direcionado, Simples e Sem Pesos nas Arestas, basta que as entradas aij da Matriz A contenham 1 se vi e vj são adjacentes e 0 caso contrário. Se as arestas do grafo tiverem pesos, aij pode conter, ao invés de 1 quando houver uma aresta entre vi e vj, o peso dessa mesma aresta.

 

Por exemplo, a matriz de adjacência do grafo ao lado é

Em Grafos Não-Direcionados, as Matrizes de Adjacência são Simétricas ao longo da Diagonal Principal - isto é, a entrada aij é igual à entrada aji. Matrizes de Adjacência de Grafos Direcionados, no entanto, não são assim. Num Digrafo Sem Pesos, a entrada aij da matriz é 1 se há um Arco de vi para vj e 0 caso contrário.

Um resultado interessante ocorre quando consideramos a Potência k da Matriz de Adjacência, ou seja, o Produto                          .

Antes de apresentar o resultado, vamos definir um Percurso em um grafo G. Um percurso corresponde a uma Sequência, Finita e Não-Vazia, de vértices do grafo, na qual (v0, v1, ..., vi, ..., vk-1, vk) é tal que, para todo 0 ≤ i ≤ k-1, vi e vi+1 são vértices adjacentes. Os vértices v0 e vk são chamados, respectivamente, de Origem e Fim do Percurso, enquanto v1, v2, ..., vk-1 são os Vértices Internos ao Caminho. O Inteiro k é o Comprimento do Percurso. Um Caminho em um Digrafo é um Percurso no qual todos os Arcos estão Orientados no Sentido Origem do Percurso-Fim do Percurso.

Se A é a matriz de adjacência de um grafo G com conjunto de vértices dado por V(G) = {v1, v2, ..., vn}, então a entrada (i,j) de     , com k ≥ 1, corresponde ao número de percursos (distintos) de comprimento k existentes entre os vértices vvj.

Pode-se mostrar esse resultado por Indução Matemática. Quando k = 1, o resultado segue de modo natural da definição de matriz de adjacência, uma vez que existe um percurso de comprimento 1 entre o vértice vi e o vértice vj se e só se {vi, vj} é uma aresta de G. Seja

O elemento (4,6) de A² indica que não há nenhum caminho de comprimento 2 ligando os vértices 4 e 6 do grafo acima. Por outro lado, o elemento (4,6) de A³ indica que existem 3 caminhos de comprimento 3 ligando os vértices 4 e 6. São eles: (4,3,4,6), (4,5,4,6) e (4,6,4,6).

 

 

Bibliografia

  • CHARTRAND, G., LESNIAK, L. Graphs & Digraphs. Editora CRC Press, 2004.

 

 

Ver também

  A partir de 11 Set de 2020

Você é o Visitante de Número

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos