Part I: Adjacency Matrix and Shortest Path
First, let us construct and describe the graph based on the given adjacency matrix. To describe such graph, the analysis of the given adjacency matrix should be performed. First of all, the adjacency matrix has 5 rows and 5 columns; therefore, the graph based on it should have 5 vertices. In addition, according to the definition of an adjacency matrix, from its entries one can derive that for any two vertices i and j, vertex i is connected with vertex j with an edge of weight aij. Also, as the diagonal of the adjacency matrix contains only zero elements, in the requested graph there are no loops on vertices (i.e. no vertex is connected to itself). An example of such graph is presented by Figure 1.
{14325}: a14 + a43 + a32 + a25 = 5+4+1+3 = 13;
{1435}: a14 + a43 + a35 = 5+4+8 = 17;
{1235}: a12 + a23 + a35 = 6+1+8 = 15;
{125}: a12 + a25 = 6+3 = 9.
Total number of simple paths from 1 to 5, therefore, is 4. The shortest of these paths, as follows from the construction process described above, is 1-2-5, which has the weight of 9.
Part II: Trees
Based on the described structure of subordination relations, the following tree that describes the structure of the college hierarchy can be constructed (see Figure 2).
In this graph, each vertex corresponds to a person mentioned (e.g. college president, vice president, provost, administrative assistant, head of finance, head of alumni relations, dean, department chair, faculty members – marked for simplicity as “faculty”), while edges represent direct correspondence (subordination) between two respective persons (e.g. deans directly report to provost).
If a relation (edge) is additionally imposed between the college president and the head of alumni relations, the graph is no longer a tree, because by definition, a connected graph is considered a tree when it has no closed loops (cycles), or, in other words, when any two vertices are connected exactly by one simple path. However, when establishing a link between the college president and the head of alumni relations, the cycle consisting of college president (CP), vice president (VP), and the head of alumni relations (HAR) is formed, as the vertices CP and HAR are now connected by two simple paths: CP-HAR and CP-VP-HAR.
References
Johnsonbaugh, R. (2007). Discrete Mathematics (7th ed.). Upper Saddle River, NJ: Pearson Prentice Hall.
Weisstein, E. W. Tree. MathWorld – A Wolfram Web Resource. Retrieved from http://mathworld.wolfram.com/Tree.html
