Directed network connectivity matrices and orientation; Powers count n-step walks; Weighted sums, connectivity efficiency and dominance models; Limits of matrix path counts/model weightings
Example 1
A directed network has arcs A→B,B→C and A→C. With vertices ordered A,B,C and rows as departure vertices, what is adjacency entry (A,C)?
Show worked answer
Answer: 1
- There is one direct arc from A to C.
Example 2
A network has arcs A→B,A→C,B→D and C→D. How many length-two walks go from A to D?
Show worked answer
Answer: 2
- The two walks are A→B→D and A→C→D. Powers of an adjacency matrix count walks, which may revisit vertices in other networks.
Example 3
A cost matrix is [[0,6,12],[6,0,4],[12,4,0]]. Find the least cost from vertex 1 to 3 using at most two edges.
Show worked answer
Answer: 10
- Compare direct cost a+b+2 with the route via vertex 2, costing a+b.