Essa é a matriz de adjacencia, como descobrir(implementar um algoritmo) se os vertices 2 e 3 são adjacentes utilizando o R?
-
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.– Flavio Barros18/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.– Tiago18/04/2019 às 2:38
-
Qual é a dimensão dessa matriz?– Flavio Barros18/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– Tiago18/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?– Flavio Barros18/04/2019 às 2:59
1 Resposta
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:
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
-
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...– Tiago18/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