MAT 331: Homework 2

Problem 2.1

In this problem we will explore some of the basic definitions and Mathematica functions for graphs. A walk in a graph consists of an alternating sequence of vertices and edges (Subscript[x, 0]), (Subscript[e, 1]), (Subscript[x, 1]),.., (Subscript[e, n]), (Subscript[x, n]) such that (Subscript[e, i])=(Subscript[x, i-1])->(Subscript[x, i]) is an edge between vertex (Subscript[x, i-1])and vertex (Subscript[x, i]). A walk is closed if (Subscript[x, 0])=(Subscript[x, n]) and open otherwise. The number of edges is the length of a walk. The vertices and edges may be repeated in a walk. A path is (usually defined as) an open walk with no repeated vertices. A cycle is a closed walk with no repeated vertices, other than the first and last vertex. The problem of finding the shortest path between two vertices is very relevant to practical problems, such as finding the way out of a maze or navigating a road network. Cycles are also very important if traversing the whole graph in some way and coming back to the same place is desired instead. 
Another relevant feature of graphs representing real systems is community structure, or clustering, i. e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e. g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs.

Consider the directed graph G depicted below (you may need to click on Enable Dynamics first, to view the graph):

Use the function Graph[...] to generate the graph G. The option GraphStyle->”SmallNetwork” will give the same display style as above, but you are free to explore additional attributes as well.

Find the strongly connected components of G. Use HighlightGraph[...] to color the vertices of the graph according to the component they belong to.

Use the function FindGraphCommunities[...] to find a list of communities in the graph G. This function returns a list of communities, where each community is a list of vertices. The communities are ordered by their length, with the largest community first. Use the command HighlightGraph[...] to color the vertices of the graph according to the community they belong to.

ShortestPath[G, v1, v2] returns a list of vertices representing the shortest path between nodes v1 and v2. Use this function to find the shortest path between node 6 and node 9 and then use HighlightGraph[...] to highlight the shortest path between these nodes. First highlight only the vertices, then highlight the edges of the shortest path. Use GraphicsRow[...] to print the two highlighted graphs on the same row.

GraphDiameter[G] gives the greatest distance between any pair of vertices in the graph G. What is the diameter of G? Explain.

Problem 2.2

Consider the graph G from problem 2.1. The command FindCycle[G,{n}] returns a cycle of length n in graph G. Use this function to find a cycle of length 3 in G. Suppose next that we want to find all cycles of length 3 in G. There are several ways to do that, but we will choose to work with the adjacency matrix of G for this task. Use your preferred loop structures in Mathematica (Do, While, For) to find how many cycles of length exactly 3 are in the graph G and to print all of these cycles. A cycle should be displayed as a list of edges of the form {a->b, b->c, c->a}. Do not print the same cycle three times! For example, {a->b, b->c, c->a}, {b->c, c->a, a->b}, {c->a, a->b, b->c} are different ways of writing the same cycle, which should be counted only once.

Problem 2.3

Write a function transition[...] that takes as input a directed graph H with any number of nodes, represented as a list of directed edges, and returns the transition matrix of H. Recall that the (i,j) entry of the transition matrix reflects the probability of transition from node i to node j. A preliminary version of the algorithm for computing the transition matrix of a graph is done is the lecture notes. There are some special cases which were not covered in the lecture (like the case of nodes with no outgoing edges). Test your function on the graph from problem 1, as well as on a randomly generated directed graph with 10 nodes and 20 edges.

Problem 2.4

Let H be any undirected graph. If H is a connected, acyclic graph (acyclic means that it contains no cycles) then we say that H is a tree. Trees are very useful for storing, sorting and querying information that has a natural hierarchical structure. For instance, the file system (folders, subfolders, documents, etc.) in a computer uses a tree architecture.

To build some intuition about trees, use TreePlot[H, VertexLabeling->True, DirectedEdges->False] to plot any graph which has the properties listed above. GraphPlot[...] can also be used for plotting trees, however the  layout is slightly different.  Then give short mathematical arguments for the following claims:

Show that if H is a tree then the Adjacency Matrix of H has one eigenvalue equal to 0.

Show that a graph H is a tree if and only if any one of the following properties is satisfied:

Every pair of distinct vertices of H is connected by a unique path.

The graph H is connected, but deleting any edge disconnects H.

The graph H is acyclic, but adding any edge to H forms a cycle.

The graph H is connected and has n-1 edges, where n is the number of vertices of H.

Problem 2.5

In this problem, we want to use the command Manipulate[...] to create nice interactive models. We can wrap Manipulate[...] around any Wolfram command. The output you get from evaluating a Manipulate command is an interactive object containing one or more controls (sliders, etc.) that you can use to vary the value of one or more parameters.

Let’s go back to part 4 of problem 1 and turn it into an interactive model. We do not want to change the graph G from problem 1, but we would like to build an interactive model such that for any given choice of nodes v and u in G, we display the graph G with the shortest path between u and v highlighted. Use the command Manipulate[...] to create a nice interactive model with controls for the parameters u and v.

RandomGraph[{m,n},k] generates k random undirected graphs with m vertices and n edges; if we want to generate directed graphs, we need to set the attribute DirectedEdges to True, as shown in the lecture notes. Your first task is to create a nice interactive model that can generate k (directed or undirected!) graphs with m vertices and ((m(m-1))/2) edges. The possible values for k should be 1 and 4. The parameter m can be any positive integer between 4 and 10, with default value 6. You should have one extra parameter, called Directed, that can take the values True or False.

Build an interactive model with two controls, n and u, that generates a random graph called K with n vertices and 2n edges and highlights vertex u of graph K. When the user selects a different vertex u of K, you display graph K with vertex u shown with a different color and with a different size.