Alberi di supporto

g4 = read.graph(file="graph4.gml", format="gml")
coords4 = layout.fruchterman.reingold(g4)
plot(g4, layout=coords4, vertex.size=10, edge.label=E(g4)$weight) 

Verifichiamo che il grafo sia connesso:

is.connected(g4)

Calcoliamo un albero di supporto di costo minimo (l'identificazione degli archi ci servirà successivamente):

E(g4)$id = 1:ecount(g4)
mst = minimum.spanning.tree(g4, weights = E(g4)$weight)

Calcoliamo il costo dell'albero:

sum(E(mst)$weight)

Visualizziamo l'albero (notate il cambio di metodo di visualizzazione):

plot(mst, layout = layout.reingold.tilford(mst), vertex.size=10)

Coloriamo l'albero di rosso nel grafo originale:

E(g4)$color = "black"
E(g4)$width = 1
E(g4)[E(mst)$id]$color = "red"
E(g4)[E(mst)$id]$width = 3
plot(g4, layout=coords4, vertex.size=10, edge.label=E(g4)$weight)