Reputation: 7905
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
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)
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
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