Pop Quiz. Graphs Matrices

Discrete Mathematics at ORU

Author

E. Valderrama-Araya, Ph.D. 

# libraries to plot graphs
# when more than one loop, will make a weighted one
library(igraph)

Matrix multiplication

Problem 1

A <- matrix(data=c(2,3,3,1),nrow = 2)
A
     [,1] [,2]
[1,]    2    3
[2,]    3    1
A %*% A
     [,1] [,2]
[1,]   13    9
[2,]    9   10
(A %*% A) %*% A
     [,1] [,2]
[1,]   53   48
[2,]   48   37
g <- graph_from_adjacency_matrix(A, mode = "undirected")
plot(g, vertex.label = c("A", "B"))

Problem 2

A <- matrix(data=c(0,2,1,
                   2,0,2,
                   1,2,0),nrow = 3)
A
     [,1] [,2] [,3]
[1,]    0    2    1
[2,]    2    0    2
[3,]    1    2    0
A %*% A
     [,1] [,2] [,3]
[1,]    5    2    4
[2,]    2    8    2
[3,]    4    2    5
(A %*% A) %*% A
     [,1] [,2] [,3]
[1,]    8   18    9
[2,]   18    8   18
[3,]    9   18    8
g <- graph_from_adjacency_matrix(A, mode = "undirected")
plot(g, vertex.label = c("A", "B", "C"))

Problem 3

A <- matrix(data=c(0,1,0,1,
                   1,0,1,0,
                   0,1,0,0,
                   1,0,0,0),nrow = 4)
A
     [,1] [,2] [,3] [,4]
[1,]    0    1    0    1
[2,]    1    0    1    0
[3,]    0    1    0    0
[4,]    1    0    0    0
A %*% A
     [,1] [,2] [,3] [,4]
[1,]    2    0    1    0
[2,]    0    2    0    1
[3,]    1    0    1    0
[4,]    0    1    0    1
(A %*% A) %*% A
     [,1] [,2] [,3] [,4]
[1,]    0    3    0    2
[2,]    3    0    2    0
[3,]    0    2    0    1
[4,]    2    0    1    0
g <- graph_from_adjacency_matrix(A, mode = "undirected")
plot(g, vertex.label = c("A", "B", "C", "D"))

Note: None Euler circuits can be found, because at least one vertex have odd degree in each graph.