0

inserir a descrição da imagem aqui Essa é a matriz de adjacencia, como descobrir(implementar um algoritmo) se os vertices 2 e 3 são adjacentes utilizando o R?

7
  • Tem algum problema na digitação da sua "matriz". Você precisa editar a questão. Outro ponto é que o problema que você está querendo resolver não está muito claro. Elabore melhor. 18/04/2019 às 2:30
  • (1,2) (1,3) (2,3) (3,4) (3,5). Apos importar como matriz de adjacencia, pretendo criar um algoritmo para descobrir se os vertices 2 e 3 sao adjacentes.
    – Tiago
    18/04/2019 às 2:38
  • Qual é a dimensão dessa matriz? 18/04/2019 às 2:44
  • 5x5. So para reforçar, ela é formada por 0 e 1. E os vertices são: 1, 2, 3, 4 e 5
    – Tiago
    18/04/2019 às 2:49
  • do jeito que você apresentou a matriz, como uma sequência de números, não dá para saber quem são os elementos. Por exemplo: quais são os elementos da linha 3 coluna 5 e ou linha 2 coluna 3? 18/04/2019 às 2:59

1 Resposta 1

5

Bom, sua pergunta está um pouco melhor mas para seu exemplo ser realmente reprodutível você deveria fornecer a matriz em um formato pronto para o R, tal que quem fosse responder só precisaria copiar e colar. De qualquer forma segue a resposta.

Conjunto Mínimo

Aqui vou recriar sua matriz no R:

g <- matrix(c(0,1,1,0,0,1,0,1,0,0,1,1,0,1,1,0,0,1,0,0,0,0,1,0,0), nrow = 5)

o que resulta na seguinte matriz

      [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    1    0    0
[2,]    1    0    1    0    0
[3,]    1    1    0    1    1
[4,]    0    0    1    0    0
[5,]    0    0    1    0    0

Usando o igraph

O R conta com igraph que lhe permite fazer praticamente tudo com grafos, inclusive os plots de grafos a partir das matrizes de adjacência:

library(igraph)

## Cria o grafo a partir da matriz de adjacências g
G <- as.undirected(graph.adjacency(g, weighted = T))

## Plot do grafo
plot(G)

o que resulta no seguinte grafo:

inserir a descrição da imagem aqui

E por fim você pode utilizar a função as_adj_list():

al <- as_adj_list(G, mode="out")

[[1]]
+ 2/5 vertices, from 7a41c18:
[1] 2 3

[[2]]
+ 2/5 vertices, from 7a41c18:
[1] 1 3

[[3]]
+ 4/5 vertices, from 7a41c18:
[1] 1 2 4 5

[[4]]
+ 1/5 vertex, from 7a41c18:
[1] 3

[[5]]
+ 1/5 vertex, from 7a41c18:
[1] 3

Veja que cada elemento da lista é relacionado a um dos vértices e dentro da lista estão os vértices vizinhos. No caso da sua pergunta, para saber se os vértices 2 e 3 são vizinhos basta procurar os vizinhos do vértice 2, na posição dois da lista:

> al[[2]]
+ 2/5 vertices, from 7a41c18:
[1] 1 3

portanto os vértice 1 e 3.

Construindo um teste de adjacência

De posse do grafo e da lista de adjacências é possível criar uma função que testa a adjacência de dois vértices quaisquer:

sao_adj <- function(x,y,al) {

  ## Testa se x e y são adjacentes
  return(y %in% al[[x]])

}

E vamos testar para um caso onde ocorre a adjacência e um caso onde não ocorre:

> sao_adj(x = 1, y = 2, al = al)
[1] TRUE
> sao_adj(x = 5, y = 2, al = al)
[1] FALSE
> sao_adj(x = 1, y = 4, al = al)
[1] FALSE
> sao_adj(x = 3, y = 1, al = al)
[1] TRUE
2
  • Obrigado! Sou novo por aqui, estou ajustando...Ajudou bastante, porem a ideia é encontrar ou elaborar um algoritmo que busque identificar se dois vertices quais quer sao adjacentes...
    – Tiago
    18/04/2019 às 4:56
  • @Tiago veja que inicialmente a minha resposta já respondeu sua pergunta. De qualquer forma agora você tem uma função que testa adjacência entre dois vértices quaisquer. 18/04/2019 às 5:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .