A graph is a finite set of objects called nodes together wit

A graph is a finite set of objects called nodes, together with some paths between some of the nodes, as illustrated below. A path of length one is a path that directly connects one node to another. A path of length k is a path made up of k consecutive paths of length one. The same length one path can appear more than once in a longer path; for example, 1-2-1 is a path of length two from node 1 to itself in the example below When the nodes have been numbered from 1 to n, the adjacency matrix A of the graph is defined by letting a-1 if there is a path of length one between vertices i and j and a 0 otherwise Example: verify that the graph below has the matrix A shown as its adjacency matrix. 010 0 0 0 1010 0 1 0101 0 0 | 001011 000 1 0 1 01 01 1 0 4 2 Theorem (Interpretation of the powers of an adjacency matrix): If A is the adjacency matrix of a graph, then the (ij) entry of A* is a nonnegative integer which is the number of paths of lengthk from node i to nodej in the graph

Solution

Answer for Question1.

The (6,3) entry of A² indicated that there are two paths of length two from node 6 to node 3. The expression for (6,3) justifies this as follows.

i.e., a₆₁a₁₃ + a₆₂a₂₃ + a₆₃a₃₃ + a₆₄a₄₃ + a₆₅a₅₃ + a₆₆a₆₃

= (0)(0) + (1)(1) + (0)(0) + (1)(1) + (1)(0) + (0)(0) = 2.

Here, {a₆₁a₁₃ , a₆₃a_{33 ,} a₆₆a₆₃ } = (0)(0) means there is no path (intermediate node 1, 3, 6 respectively) from node 6 to node 3.

Here, a₆₂a₂₃ = (1)(1) means there is a path from node 6 to node 2 and node 2 to node 3.

Here, a₆₄a₄₃ = (1)(1) means there is a path from node 6 to node 4 and node 4 to node 3.

Here, a₆₅a₅₃ = (1)(0) means there is a path from node 6 to node 5 and but no path from node 5 to node 3.

Answer for Question2.

The adjacency matrix A is as follows.

The A² matrix can be calculated by multiplying matrix A with matrix A. The A² matrix is as follows in the table.

In this A² matrix, the value of each field represents the number of path in between a pair of nodes with one intermediate node.

The A³ matrix can be calculated by multiplying matrix A with matrix A². The resulted A³ matrix is as follows in the table.

In this A³ matrix, the value of each field represents the number of path in between a pair of nodes with two intermediate nodes.

0	1	0	0	0	0
1	0	1	0	0	1
0	1	0	1	0	0
0	0	1	0	1	1
0	0	0	1	0	1
0	1	0	1	1	0