can anyone do this question/
Hello, srk619!
I can get you started . . .
Draw the graph with adjacency matrix: .$\displaystyle \begin{bmatrix}0&1&1&0&0&0 \\ 1&0&1&0&0&0 \\ 1&1&0&1&0&0 \\ 0&0&1&0&1&1 \\ 0&0&0&1&0&1 \\ 0&0&0&1&1&0 \end{bmatrix}$
. . . . $\displaystyle \begin{array}{ccccc} & & \boxed{2} \\ & ^{\nearrow}_{\swarrow} & & ^{\searrow}_{\nwarrow} \\ \boxed{1} & \leftrightarrow & \leftrightarrow & \leftrightarrow & \boxed{3} \\ & & & & \uparrow\downarrow \\ \boxed{6} & \leftrightarrow & \leftrightarrow & \leftrightarrow & \boxed{4} \\ & ^{\nwarrow}_{\searrow} & & ^{\swarrow}_{\nearrow} \\ & & \boxed{5} \end{array}$
Hello srk619,
(a)
In an adjacency matrix, the rows and columns of the matrix represent the nodes of the graph
, and the value of the matrix element at row i and column j represents the edges. If it's 1 means there is an edge from node i to node j.
Now, there could be two possibilities, the graph could be directed ( the edges have arrows on them to represent direction) or undirected (edges have no arrows).
Let's assume the nodes are numbered starting from 1
i.e. row 1 of matrix represents node 1
row 2 of matrix represents node 2, and so on till,
row 6 of matrix represents node 6
the same can be said about the columns
column 1 of matrix represents node 1
column 2 of matrix represents node 2, and so on till,
column 6 of matrix represents node 6
Thus, If the graph is directed, and according to the posted adjacency matrix,
- a Zero at row 1,column 1 means there is no edge from node 1 to itself
- a One at row 2,column 1 means there is an edge directed from node2 to node1
- a One at row 1,column 2 means there is an edge directed from node1 to node2
So, basically, the row represents the starting point(node) of the edge, and the column represents the ending point (node) of the edge, if there is a One in the matrix,
So continuing in this manner the graph will be
but what if the graph is undirected (edges have no arrows), i.e. both nodes can be considered as both starting and ending points, so to indicate this, we should put a One in both directions
for all edges.
for ex in an undirected graph, if there is an edge between node 1 and node2, we should put a One
at row1, column2 , and a One at row2, column1
So, if it happens that there was a One in a certain direction , but a Zero in the opposite direction, it means that this graph is directed.
And if it happens that for all edges, there is an edge in both directions, We can't tell Whether the graph is directed or undirected. (It depends on the assumptions of the problem) which is the case in this problem.
To check that a graph could be undirected, you can take the transpose of the matrix
Transpose is to exchange the rows and the columns,
for ex: row 1 becomes column 1, and column 1 becomes row 1
if the matrix transpose is equal to the original matrix, then the graph could be undirected
which is the case in this problem
So if the problem assumption was undirected graph, the graph will be
b)
“It is not difficult to prove by mathematical induction that the number of different paths of length k>0 from the ith verterx to the jth vertex of a graph (undirected or directed) equals the (i, j)th element of A to the power of k, where A is the adjacency matrix of the graph” Introduction to The Design and Analysis of Algoritms, 2nd Edition, Anany Levitin
So Here are the steps of the solution:
- Compute A^2,
A^2 = A.A = [ 2 1 1 1 0 0 ]
[ 1 2 1 1 0 0 ]
[ 1 1 3 0 1 1 ]
[ 1 1 0 3 1 1 ]
[ 0 0 1 1 2 1 ]
[ 0 0 1 1 1 2 ]
so the entry at row1, coumn3 is equal to 1, so there is one path
You can verify this by looking at graph, you will find this is the path 1,2,3
c)
I am not sure what is the adjacency matrix connectivity algorithm, but you can do a Depth-First Search (DFS ) or Breadth-First Search (BFS) , and after the algorithm halts, check whether all nodes will have been visited. If they have, the graph is connected; otherwise, it's not connected
Hope this helps