CODEWITHSUNDEEP
rgraph
Fernando
Fernando

Reputation: 7905

Random geometric graph connectivity

Given N random points uniformly distributed in the unit square, and a distance d, i can generate a matrix in the following format:

             E V1 V2
[1,] 0.5564821  1  2  
[2,] 0.3373116  1  3
[3,] 0.3973278  1  4
[4,] 0.6066518  1  5
[5,] 0.9603731  1  6
[6,] 0.3612895  1  7
# more rows...

Where E is the edge between vertex V1 and V2. I've just started learning graph-theory, so i ask:

How can i determine if this random geometric graph is connected? Thanks!

Upvotes: 0

Views: 275

Answers (2)

lawyeR
lawyeR

Reputation: 7684

Your graph is connected.

Here is a portion of the net work graph you describe (using mtx as the matrix object). 

dput(mtx)
structure(list(E = c(0.5564821, 0.3373116, 0.3973278, 0.6066518, 
0.9603731, 0.3612895), V1 = c(1L, 1L, 1L, 1L, 1L, 1L), V2 = 2:7), .Names = c("E", 
"V1", "V2"), class = "data.frame", row.names = c("[1,]", "[2,]", 
"[3,]", "[4,]", "[5,]", "[6,]"))

Then to use the igraph package to plot the graph:

library(igraph)
onagraph <- graph.data.frame(mtx, directed=F) 

set.seed(19)
plot(onagraph)

enter image description here

A "connected graph" is a graph where "it's possible to walk from any vertex to any other vertex of [the graph] along the edges of [the graph]", according to Benjamin, Chartrand, and Zhang, The Fascinating World of Graph Theory (Princeton Univ. Press, 2015) at 46.

Upvotes: 1

IRTFM
IRTFM

Reputation: 263499

Unlike @user1317221_G, I get a not-found message with ?igraph. The igraph package can be installed with:

install.packages("igraph")  # then load
library("igraph")
help( package="igraph" )

Upvotes: 1

Related Questions