Page 304, Question 2

The bridges and land masses of a certain city can be modeled with graph G in figure 8.7. a. Is G Eulerian? Why or why not? b. Suppose we relax the requirement of the walk so that the walker need not start and end at the same land mass but still must traverse every bridge exactly once. Is this type of walk possible in a city modeled by the graph in figure 8.7? If so, how? If not, why not?

Page 304, Answer 2

library(igraph)
## 
## Attaching package: 'igraph'
## 
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## 
## The following object is masked from 'package:base':
## 
##     union
relations <- data.frame(from=c(1,1,2,2,3,3,4,4,5),
                        to = c(2,3,3,4,5,4,5,6,6),
                        weight = c(1,1,1,1,1,1,1,1,1))


g <- graph.data.frame(relations, directed=FALSE)
plot(g)

degree(g)
## 1 2 3 4 5 6 
## 2 3 4 4 3 2

  1. Is G Eulerian? Why or why not?
    G is not Eulerian because both vertices 2 and 5 have odd degree 3.

  2. Suppose we relax the requirement of the walk so that the walker need not start and end at the same land mass but still must traverse every bridge exactly once. Is this type of walk possible in a city modeled by the graph in figure 8.7? If so, how? If not, why not?

Since we have two vertices with odd degrees, we can start on of the odd degree vertex and end in the other odd degree vertex to make traverse each edge once.

Please note that to Eulerize the graph we can add duplicate edges to the odd degree vertices. However, in this case adding duplicate edges to odd degree vertices will change other vertices from even to odd degrees.

Page 307, Question 1

Consider the graph in Figure 8.11

  1. Write down the set of edges E(G)
  2. Which edges are incident with vertex b?
  3. Which vertices are adjacent to vertex c?
  4. Compute deg(a)
  5. compute |E(G)|

Page 307, Answer 1

relations <- data.frame(from=c('a','a','a', 'b', 'b', 'c',  'd',  'e', 'f'),
                        to = c('b','e','f', 'c', 'd', 'd',  'e',  'f', 'd'),
                        weight = c(1,1,1,1,1,1,1,1,1 ))
g <- graph.data.frame(relations, directed=FALSE)
plot(g)

  1. Write down the set of edges E(G)

E(G) = {ab, ae, af, bc, bd, cd, de, ef, fd}

  1. Which edges are incident with vertex b?

Edges ab, bc, and bd are incident with vertex b. To double check, we wil run the below command:

incident(g, 'b')
## + 3/9 edges (vertex names):
## [1] a--b b--c b--d
  1. Which vertices are adjacent to vertex c?

Vertices b and d are adjacent to vertex c. To double check, we wil run the below command:

adjacent_vertices(g, 'c')
## $c
## + 2/6 vertices, named:
## [1] b d
  1. Compute deg(a) deg(a) = 3.
    To double check, we wil run the below command:
degree(g, "a")
## a 
## 3
  1. Compute |E(G)| |E(G)| = 9 To double check, we wil run the below command:
gsize(g)
## [1] 9

Page 331, Problem 1  

Find out the shortest path from a to node j in the graph in figure 8.33 with edge weights shown in the graph

Page 331, Answer 1  

alt text

Therefore, form the above matrix, the path is:
{ a, b, d, g, e, i, j}  

Adding the green cell we get: 2+2+2+1+3+2 = 12

Again,let’s validate our results:

relations <- data.frame(from=c('a','a','b','b','c','c','d','e','g','f','i','e','h', 'e'),
                        to = c('b','c','e','d','e','f','g','g','i','i','j','h','j','i'),
                        weight = c(2,4,7,2,4,2,2,1,8,6,2,2,4,3))
g3 <- graph.data.frame(relations, directed=FALSE)
plot(g3)

lets create our shortest path matrix:

shortest.paths(g3)
##    a  b c d e g f  i h  j
## a  0  2 4 4 7 6 6 10 9 12
## b  2  0 6 2 5 4 8  8 7 10
## c  4  6 0 7 4 5 2  7 6  9
## d  4  2 7 0 3 2 9  6 5  8
## e  7  5 4 3 0 1 6  3 2  5
## g  6  4 5 2 1 0 7  4 3  6
## f  6  8 2 9 6 7 0  6 8  8
## i 10  8 7 6 3 4 6  0 5  2
## h  9  7 6 5 2 3 8  5 0  4
## j 12 10 9 8 5 6 8  2 4  0

lets find our the shortest path from node a to j

shortPathname_aToj<- get.shortest.paths(g3, 'a', 'j')
shortPathname_aToj$vpath
## [[1]]
## + 7/10 vertices, named:
## [1] a b d g e i j

Page 331, Problem 3

Use our maximum-flow algorithm to find the maximum flow from s to t in the graph of figure 8.31

Page 331, Answer 3

library(igraph)

relations <- data.frame(from=c('s','s','s','s','x1','x1','x1','x1','x2','x2','x3','x3','x4','x4','y1','y2','y3','y4','y5','y6'),
                        to = c('x1','x2','x3','x4','y1','y2','y4','y5','y3','y6','y1','y3','y1','y3','t','t','t','t','t','t'),
                        weight = c(1,1,1,1,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,Inf,1,1,1,1,1,1))


g4 <- graph.data.frame(relations, directed=TRUE)
plot(g4)

maxFlow<- graph.maxflow(g4, source=V(g4)["s"], target=V(g4)["t"])

# The value of flow:
maxFlow$value
## [1] 4
# All Flow stats
maxFlow
## $value
## [1] 4
## 
## $flow
##  [1] 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1
## 
## $cut
## [1]  1 15 17 20
## 
## $partition1
## + 7/12 vertices, named:
## [1] s  x2 x3 x4 y1 y3 y6
## 
## $partition2
## + 5/12 vertices, named:
## [1] x1 y2 y4 y5 t 
## 
## $stats
## $stats$nopush
## [1] 10
## 
## $stats$norelabel
## [1] 1
## 
## $stats$nogap
## [1] 0
## 
## $stats$nogapnodes
## [1] 0
## 
## $stats$nobfs
## [1] 1