Atividade: Matriz de Adjacência

Nesta atividade, nós vamos praticar a utilizar uma matriz para representar a adjacência em um grafo como uma aplicação de matrizes para a teoria dos grafos.

Q1:

Escreva a matriz adjacente da rede dada.

  • A 2 0 0 0 0 1 0 1 1
  • B 0 0 0 0 1 1 2 1 0
  • C 0 0 0 1 0 1 0 1 1
  • D 0 0 0 2 0 1 0 1 1
  • E 1 0 0 0 0 1 0 1 1

Q2:

Quando uma conexão em uma rede não tem uma seta, diz-se que ela é "não direcionada". Uma conexão não direcionada entre nós 𝑎 e 𝑏 é equivalente a uma conexão direta de 𝑎 para 𝑏 junto com uma conexão direta de 𝑏 para 𝑎 . Determine a matriz adjacente da rede dada.

  • A 0 1 2 1 0 0 2 0 0
  • B 1 1 1 1 0 0 1 0 0
  • C 0 1 1 1 0 0 1 0 0
  • D 1 1 2 1 0 0 2 0 0
  • E 0 0 2 0 1 1 2 1 1

Q3:

Em baixo mostra-se a rede cuja matriz de adjacência é

Uma sequência de conexões com início num nodo e fim noutro é designado por caminho. O comprimento de um caminho é o número de conexões utilizadas. Por exemplo, "2e1” é um caminho de comprimento 1 do nodo 2 ao nodo 1, “ 2 𝑒 𝑏 3 ” é um caminho de comprimento 2 do nodo 2 ao nodo 3 e “ 2 𝑒 𝑒 𝑒 1 ” é um caminho de comprimento 3 do nodo 2 ao nodo 1.

Realize a lista de todos os caminhos de comprimento 2 do nodo 1 ao nodo 1.

  • A 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 1 , 1 𝑑 𝑑 1 , 1 𝑒 𝑑 1 , 1 𝑒 𝑒 1
  • B 1 𝑎 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 𝑐 1 , 1 𝑑 𝑒 1 , 1 𝑑 𝑑 𝑑 1 , 1 𝑒 𝑑 1 , 1 𝑒 𝑒 𝑒 1
  • C 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 2 , 1 𝑑 𝑑 2 , 1 𝑒 𝑑 2 , 1 𝑒 𝑒 2
  • D 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 1 , 1 𝑑 𝑑 1 , 1 𝑒 𝑑 1 , 1 𝑒 𝑒 1
  • E 1 𝑎 𝑎 1 , 1 𝑏 𝑏 1 , 1 𝑏 𝑐 1 , 1 𝑐 𝑏 1 , 1 𝑐 𝑐 1 , 1 𝑑 𝑒 2 , 1 𝑑 𝑑 2 , 1 𝑒 𝑑 1 , 1 𝑒 𝑑 2 , 1 𝑒 𝑒 2

O número de caminhos de comprimento 𝑛 do nodo 𝑖 ao nodo 𝑗 é dado por ( 𝐴 ) 𝑛 𝑖 , 𝑗 , a entrada ( 𝑖 , 𝑗 ) da matriz 𝐴 𝑛 . Quantos caminhos de comprimento 3 existem do nodo 1 ao nodo 2?

  • A 18 caminhos
  • B 22 caminhos
  • C 26 caminhos
  • D 23 caminhos
  • E 16 caminhos

A Nagwa usa cookies para garantir que você tenha a melhor experiência em nosso site. Saiba mais sobre nossa Política de privacidade.