Graph Theory: Using iGraph Exercises (Part-2)
Following on from last time, this tutorial will focus on more advanced graph techniques and existing algorithms such as Dijkstra’s algorithm that can be used to draw real meaning from graphs.
This is part 2 in the series of iGraph tutorials, for part 1, click here.
When completing these tutorials be sure to read up on the algorithms you are implementing; Wikipedia is usually a good place to start. In practice, when the graphs are much larger in size, complete solutions to these problems are not possible and instead, we seek the closest approximation.
Solutions are available here.
Copy the following code into your R script to generate data for a bipartite graph.
matches <- data.frame(name = rep(c(“Jerry”, “Lilly”, “Karl”, “Jenny”), each = 4),
subject = rep(c(“Maths”, “English”, “Biology”, “French”), 4),
weight = c(81, 78, 24, 58, 76, 60, 62, 83, 35, 59, 50, 56, 72, 90, 88, 86))
g <- graph_from_data_frame(matches, directed = FALSE)
From this, assign each set of nodes a unique type, 1 or 2
Now plot your graph, clearly showing the two sides to the bipartite graph.
Determine the minimum colouring needed so that no two adjacent vertices are the same colour
Algorithmically, find the best matching between student and subject based upon their respective mark in each subject.
Add three additional nodes to your graph for Becky, Ben and Mark. Connect these up to Maths, French and Biology respectively.
Calculate a spectrum or adjacency matrix for your new graph.
Plot your eigenvalues and visually determine the rank of your adjacency matrix.
Find the size of independent vertex set. What does number mean?
Calculate the k, such that the graph is k-vertex connected
Calculate the k, such that the graph is k-edge connected