Práctica 3
Grafos
Universidad Rey Juan Carlos
Matemática Discreta 1
Prácticas
Práctica 1:
Dibujar un grafo.
Sea G(V,E) el grafo: Con matriz de adyacencia
0 2 2 2
𝐴=
2
2
2
( 0
1
1
1
0
1
1
1
0
)
Matemática Discreta 2
Prácticas
Instalamos en R las librerías necesarias:
Código 1:
library(igraph)
Matemática Discreta 3
Prácticas
Definimos el grafo a partir de la matriz de adyacencia y lo
dibujamos:
Código 1:
# Matriz de adyacencia
adjm <- matrix(c(0,2,2,2,2,0,1,1,2,1,0,1,2,1,1,0),nrow=4,ncol=4,
byrow=TRUE)
Matemática Discreta 4
Prácticas
# Create iGraph object
#graph.adjacency(adjmatrix, mode = c("directed", "undirected",
# "max", "min", "upper", "lower", "plus"), weighted = NULL,
# diag = TRUE, add.colnames = NULL, add.rownames = NA)
graph <- graph.adjacency(adjm, mode="undirected")
plot(graph)
Matemática Discreta 5
Prácticas
El objeto igraph contiene atributos del grafo:
Código 1:
# Calculate various network properties, adding them as
# attributes to each node/vertex
V(graph)$degree <- degree(graph)
V(graph)$degree
#nodos que inciden en el vértie 1
incident(graph, 1, mode = c("all"))
Matemática Discreta 6
Prácticas
Practica 2: Crear un gafo con forma de anillo, estrella,
árbol
Código 2:
# Ring Graph
graph2 <- make_ring(10)
plot(graph2)
Matemática Discreta 7
Prácticas
# Star Graph
Star <- make_star(10, mode = "out")
plot(Star, vertex.color="green")
# Tree Graph
Tree1<-make_tree(10, 2)
plot(Tree1)
Tree2<- make_tree(10, 3, mode = "undirected")
plot(Tree2)
Matemática Discreta 8
Prácticas
Práctica 3:
Dibujar un grafo.
Sea G(V,E) el grafo: Con lista de aristas
(1,2) (2,1) (3,5) (4,3)
(1,4) (2,3) (4,2) (4,5)
2 3
1
4 5
Matemática Discreta 9
Prácticas
Definimos el grafo a partir de una lista de aristas y lo
dibujamos:
Código 4:
el <- matrix( c("1","2","1","4","2","1","2","3","3",
"5","4","2","4","3","4","5"), ncol=2, byrow = TRUE)
graph3 <-graph_from_edgelist(el)
plot(graph3)
Matemática Discreta 10
Prácticas
Estudiamos isomorfismos entre grafos:
Código 5:
# Dividimos la pantalla en dos partes para dibujar los grafos
par(mfrow=c(1,2))
Matemática Discreta 11
Prácticas
# Definimos el primer grafo
adjm2 <-
matrix(c(1,3,2,0,3,0,1,2,2,1,0,1,0,2,1,0),nrow=4,ncol=4,byrow=TR
UE)
colnames(adjm2) <- c("a","b","c","d")
rownames(adjm2) <- c("a","b","c","d")
graph2 <- graph.adjacency(adjm2,mode="undirected")
plot(graph2)
Matemática Discreta 12
Prácticas
# Definimos el segundo grafo
adjm3 <-
matrix(c(0,1,2,2,1,0,0,1,1,1,3,0,0,1,1,0,0,1,0,1,0,1,1,1,0),nrow=5,nc
ol=5,byrow=TRUE)
colnames(adjm3) <- c("a","b","c","d","e")
rownames(adjm3) <- c("a","b","c","d","e")
graph3 <- graph.adjacency(adjm3,mode="undirected")
plot(graph3)
Matemática Discreta 13
Prácticas
# Estudiamos si son isomorfos
isomorphic(graph2, graph3)
# colored graph isomorphism
g1 <- make_ring(10)
g2 <- make_ring(10)
isomorphic(g1, g2)
V(g1)$color <- rep(1:2, length = vcount(g1))
V(g2)$color <- rep(2:1, length = vcount(g2))
plot(g1)
plot(g2)
Matemática Discreta 14
Prácticas
Práctica 4:
Definir y dibujar con R los siguientes grafos:
a b A
c d B D
C
e
Matemática Discreta 15
Prácticas
Practica 5: Diseñar una función en R que a partir de una
matriz de adyacencias de un grafo conexo no dirigido
devuelva como resultado si el grafo contiene o no un
camino euleriano
Solución: Se calculan todos los grados de cada vértice y
se comprueba si son pares o no. Si hay exactamente dos
vértices de grado impar, entonces tiene un camino
euleriano. En otro caso, no lo tiene.
Matemática Discreta 16
Prácticas
comprobar_camino_euleriano <- function(adjacency_matrix){
graph <- graph_from_adjacency_matrix(adjmatrix =
adjacency_matrix,mode="undirected")
grados_vertices=degree(graph)
grados_impar=grados_vertices%%2
numero_vertices_grado_impar=sum(grados_impar)
camino_euleriano=F
if (numero_vertices_grado_impar==2){
camino_euleriano=T
}
return(camino_euleriano)
}
Matemática Discreta 17
Prácticas
EJERCICIO
Completar la práctica 4 de este pdf.
Matemática Discreta 18
Prácticas
Práctica 4:
Definir y dibujar con R los siguientes grafos:
a b A
c d B D
C
e
Matemática Discreta 19
