There's a special class of sparse graphs called expander graphs. These graphs, while being sparse, still have a number of strong connectivity properties.
The goal of this problem is to create a function which constructs an example of an expander graph. There are a few strategies used to do this; we'll follow an "algebraic" approach due to Margulis, Gabber and Galil. The construction goes like this:
We'll construct a graph on $n^2$ nodes, where the nodes, call them $(i,j)$ correspond to points in $Z_n \times Z_n$. Each node $(i,j)$ will have eight neighbors given by:
$$ (i \pm 2j, j) \\ (i \pm (2j+1), j) \\ (i, j \pm 2i) \\ (i, j \pm (2i+1)) $$Try using this description to implement a function which constructs an expander graph on $n^2$ nodes. (Careful to make sure the neighbor computations are taken "mod n" or in $Z_n \times Z_n$.)
Suppose that the company "All-Star Sporting Goods" opens a new store. Shortly after opening, the store has hired 50 employees. After some times, management decides to check on how things are going and wants ensure that "team spirit" is alive amoung the employees.
In particular, they want to get a sense of how many employees know each other and whether or not anyone is feeling isolated.
After doing a careful survey of the employees, management has made a log of the employees "employees.txt" and a log of people who a friends with each other "friends.txt".
Using this data, construct a graph with nodes representing the employees and the edges representing friends. (You can assume that the employees are "good, honest people" and that there are no one-sided friendships.)
Now, the company wants to do some analysis on the connections between people. For each employee, use the shortest_path_length function to compute their connection length to everyone else. Then, find how many people are at most distance 3 away. (That is, a friend, a friend of a friend or a friend of a friend of a friend.)
Suppose a hosptial has a list of willing kidney donors and people who are need of transplants. Due to genetic constraints, not every donor is compatible with every receiver. In particular, suppose a specific attribute, not unlike blood type, has been singled out to determine compatibility. This attribute comes in 4 types with the following property:
Donor type A can give to receiver type A, B, C, or D.
Donor type B can give to receiver type B or D.
Donor type C can give to receiver type C or D
Donor type D can only give to receiver type D.
A list of people marked donor or receiver along with their type is provided in "donor-receiver.txt".
Use this data to construct a graph of donors and receivers. Notice that this is a bipartite graph!
Now, we'd like to compute the maximum number of donor-receiver pairs which exist. In more formal terms, we'd like to compute a maximum bipartite matching.
In order to do this, we'll provide an interesting solution via max-cut as follows:
The result from the last step turns out to provide a maximum bipartite matching.