A simple algorithm for finding the one-link and two-link (one-hop and two-hop) paths between any two nodes is based on the properties of the incidence matrix. (a) If a one-hop path (one-link tie set)...

A simple algorithm for finding the one-link and two-link (one-hop and two-hop) paths between any two nodes is based on the properties of the incidence matrix.

(a) If a one-hop path (one-link tie set) exists between any two nodes, n₁
and n₂, there will be ones in the n₁
and n₂
rows for the column corresponding to the one-link tie set.

(b) If a two-hop tie set exists between any two nodes, it can be found by taking the sum of the matrix entries for the two columns. The numeral 1 appears in the column for the connected nodes and 2 for the intermediate node.

(c) Write a “pseudocode” algorithm for this approach to finding oneand two-hop tie sets.

(d) Does this generalize to n hops? Explain the difficulties.