Page 304 # 2

The bridges and land masses of a certain city can be modeled with graph G in Figure 8.7.

  1. Is G Eulerian? Why or why not?

Graph G is not Eulerian. We se that every vertex does not have an even degree. In other words the degree of G, deg(G), is 9. By definition, and Eulerian graph must have an even degree. Specifically, vertices 2 and 5 have odd degrees.

  1. 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 grph G? If so, how? If not, why not?

Yes, this type of walk is possible by traveling the path given by 2-1-3-2-4-3-5-4-6-5.

Page 307: #1

Consider the graph in Figure 8.11.

  1. Write down the set of edges \(E(g)\)

\(E(g) = \big\{ab, af, ae, bd, bc, cd, df, de, ef\big\}\)

  1. Which edges are incident with vertex \(b\)?

Edges incident with vertex \(b\): ab, bc, bd

  1. Which vertices are adjacent with vertex \(c\)?

Vertices adjacent with vertex \(c\): b and d

  1. Compute \(deg(a)\)

The degree of vertex \(a\) is the number of incidences between \(a\) and an edge.

\(deg(a) = 3 = \big\{af, ab, ae\big\}\)

  1. \(|E(G)|\)

The edge set \(E(G) = 9 = \big\{ab, af, ae, bd, bc, cd, df, de, ef\big\}\)

Page 320: #10

A basketball coach needs to finnd a starting lineup for her team. There are five positions that must be filled: point guard (1), shooting guard (2), swing (3), power forward (4), and center (5). Given the data in Table 8.7, create a graph model and use it to find a feasible starting lineup. What changes if the coach decides she can’t play Hermione in position 3?

Create the edge list:

df <- data.frame(player = c("Alice", "Alice", "Bonnie", "Courtney", "Courtney", "Deb", "Deb", "Deb",
                            "Ellen", "Fay", "Gladys", "Gladys", "Hermione", "Hermione"),
                 position = c(1, 2, 1, 1, 2, 3, 4, 5, 2, 1, 2, 4, 2, 3), stringsAsFactors = F)
            
df
##      player position
## 1     Alice        1
## 2     Alice        2
## 3    Bonnie        1
## 4  Courtney        1
## 5  Courtney        2
## 6       Deb        3
## 7       Deb        4
## 8       Deb        5
## 9     Ellen        2
## 10      Fay        1
## 11   Gladys        2
## 12   Gladys        4
## 13 Hermione        2
## 14 Hermione        3
g <- graph.data.frame(df, directed=F)
g
## IGRAPH UN-- 13 14 -- 
## + attr: name (v/c)
## + edges (vertex names):
##  [1] Alice   --1 Alice   --2 Bonnie  --1 Courtney--1 Courtney--2
##  [6] Deb     --3 Deb     --4 Deb     --5 Ellen   --2 Fay     --1
## [11] Gladys  --2 Gladys  --4 Hermione--2 Hermione--3
plot(g)

Using the the resulting graph above, there are several possible team configurations, specifically around the position 1 and 2 spots. We can see that Deb has to play position 5 since there is no other player to play that position. Consequently, Hermione has to play position 3 and Gladys must play position 4.

Some example lineups:

If Hermione cannot play position 3, Deb would have play position 3 and there would be no player who can cover position 5. This would result in an incomplete lineup.

Page 330: #1

Find a shortest path from node \(a\) to node \(j\) in the graph in Figure 8.33 with edge weights shown on the graph.

Create the edge list from a data frame.

from <- c("f", "f", "c", "c", "a",  "i", "i", "e", "e", "e", "d", "h", "j", "b")
to  <-  c("i", "c", "a",  "e", "b",  "e", "j", "h", "b", "g", "g", "j", "g", "d")
weight <- c(6, 2, 4, 4, 2, 3, 2, 2, 7, 1, 2, 4, 8, 2)

df <- data.frame(from  = from, to = to, weight = weight)

df <- arrange(df, from)

g <- graph.data.frame(df, directed=F)
g
## IGRAPH UNW- 10 14 -- 
## + attr: name (v/c), weight (e/n)
## + edges (vertex names):
##  [1] a--b b--d a--c c--e d--g e--h b--e e--g f--i c--f h--j e--i i--j j--g
plot(g, edge.label=E(g)$weight, edge.width=E(g)$weight ) 

adj=get.adjacency(g,attr='weight',sparse=FALSE) 
adj
##   a b c d e f h i j g
## a 0 2 4 0 0 0 0 0 0 0
## b 2 0 0 2 7 0 0 0 0 0
## c 4 0 0 0 4 2 0 0 0 0
## d 0 2 0 0 0 0 0 0 0 2
## e 0 7 4 0 0 0 2 3 0 1
## f 0 0 2 0 0 0 0 6 0 0
## h 0 0 0 0 2 0 0 0 4 0
## i 0 0 0 0 3 6 0 0 2 0
## j 0 0 0 0 0 0 4 2 0 8
## g 0 0 0 2 1 0 0 0 8 0
# create a matrix with shortest path (cost) for each node in the matrix
distMatrix <- shortest.paths(g, v=V(g), to=V(g), weights=E(g)$weight)

# if we want to specifically look at shortest path from node a to every other
# node
distMatrixA <- shortest.paths(g, v='a', to=V(g), weights=E(g)$weight)

# the cost minimum cost from node a to j is 12 #

distMatrix["a","j"]
## [1] 12
# an alternate method
# distances(g, v='a', to='j', weights=E(g)$weight)


# Find which nodes are traversed in the shortest path from a to j              
r <- all_shortest_paths(g, 'a', 'j', weights=E(g)$weight)

r$res[[1]]
## + 7/10 vertices, named:
## [1] a b d g e i j
# Or an alternate method
# get.shortest.paths(g, 'a', 'j', weights = E(g)$weight)[[1]]

The shortes path from node \(a\) to node \(j\) is given by:

a - b - d - g - e - i - j Cost = 12

Page 331: #3

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

Create the graph:

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,NA,NA,NA,NA,NA,NA,NA,NA,NA,NA,1,1,1,1,1,1)

df <- data.frame(from = from, to = to, weight = weight, stringsAsFactors = F)

df
##    from to weight
## 1     s x1      1
## 2     s x2      1
## 3     s x3      1
## 4     s x4      1
## 5    x1 y1     NA
## 6    x1 y2     NA
## 7    x1 y4     NA
## 8    x1 y5     NA
## 9    x2 y3     NA
## 10   x2 y6     NA
## 11   x3 y1     NA
## 12   x3 y3     NA
## 13   x4 y1     NA
## 14   x4 y3     NA
## 15   y1  t      1
## 16   y2  t      1
## 17   y3  t      1
## 18   y4  t      1
## 19   y5  t      1
## 20   y6  t      1
g <- graph.data.frame(df, directed = T)

g <- simplify(g)

plot(g, edge.label=E(g)$weight)

Calculate the maximum flow. Reference link: http://igraph.org/r/doc/max_flow.html

# calculate max flow from source = s to target = t  
mflow <- max_flow(g, source=V(g)["s"], target=V(g)["t"])

mflow
## $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

The maximum flow of \(s\) - \(t\) is given by mflow$value which is 4.

To determine the flow in terms of edges:

flow = A numeric vector, the flow itself, one entry for each edge.

Create the edge list and create a column for the numeric vector flow:

elist_flow <- cbind(data.frame(get.edgelist(g)), mflow$flow)

names(elist_flow) <- c( "From", "To", "Flow")

elist_flow
##    From To Flow
## 1     s x1    1
## 2     s x2    1
## 3     s x3    1
## 4     s x4    1
## 5    x1 y1    0
## 6    x1 y2    0
## 7    x1 y4    0
## 8    x1 y5    1
## 9    x2 y3    0
## 10   x2 y6    1
## 11   x3 y1    0
## 12   x3 y3    1
## 13   x4 y1    1
## 14   x4 y3    0
## 15   y1  t    1
## 16   y2  t    0
## 17   y3  t    1
## 18   y4  t    0
## 19   y5  t    1
## 20   y6  t    1
flow <- filter(elist_flow, Flow == 1) %>% 
        select(From, To) %>% 
        mutate(edges = paste(From, To, sep="-")) %>%
        select(edges)

flow 
##    edges
## 1   s-x1
## 2   s-x2
## 3   s-x3
## 4   s-x4
## 5  x1-y5
## 6  x2-y6
## 7  x3-y3
## 8  x4-y1
## 9   y1-t
## 10  y3-t
## 11  y5-t
## 12  y6-t

Which gives:

s-x1 -> x1-y5 -> y5-t
s-x2 -> x2-y6 -> y6-t
s-x3 -> x3-y3 -> y3-t
s-x4 -> x4-y1 -> y1-t

Reference links:
http://kateto.net/network-visualization
http://www.di.fc.ul.pt/~jpn/r/graphs/graphs.html
http://www.shizukalab.com/toolkits
http://www.shizukalab.com/toolkits/sna/bipartite