Looks at the ways that are possible to go from one vertex to another in a directed graph.

*Essential Further Mathematics 4ed 2012 (p.642)*

In the above directed graph, C is reachable from A however, D is NOT reachable from A.

When we look at reachability, we can focus on a one-step pathway or two-step pathway etc…

A one step pathway only involves one edge. E.g. from A to C. However a two step pathway involves two edges. E.g. from A to B to C.

This can be represented in adjacency matrices as shown below:

*Essential Further Mathematics 4ed 2012 (p.642)*

= one step pathway. Looking at Row A, there are two one step pathways. From A to B and from A to C.

= two step pathway

= three step pathway. Looking at row D there is one three step pathway to C – D to A to B to C.

If you add all three adjacency matrices together you will get a matrix that gives you the total reachability of reach vertices. It will tell you how many ways to get to each vertex.

*Essential Further Mathematics 4ed 2012 (p.643)*

Therefore, looking at the adjacency matrix R, there are six different ways to get to vertex C from the other vertices. **(Focus on the columns of the matrix)**

If there is an edge in a directed graph from A to B, then it is possible to say that A is **dominant** over B.

*Essential Further Mathematics 4ed 2012 (p.644)*

In this directed graph, B is dominant over A, C and E.

It is possible to represent dominance in an adjacency matrix:

*Essential Further Mathematics 4ed 2012 (p.645)*

*To check if you constructed your **one-step dominance** matrix correctly you could add the column and rows to see if they match with the arrows within graph.

Adding up the **columns** will give you the **indegree** – the number of edges moving INTO the vertex.

Adding up the **rows** will give you the **outdegree** – the number of edges moving AWAY FROM the vertex.

A two step dominance matrix takes into account the other players as well. For example:

*Essential Further Mathematics 4ed 2012 (p.645)*

B defeated C who defeated D. (It is easier to visualise this on the graph)

To find the two step dominance all you need to do is ** square** the one step dominance matrix, using a calculator.

Adding the one step and two-step dominance matrices together takes into account both dominances. It eliminates any ties that may occur such as between C and D in (Not always the case).

*Essential Further Mathematics 4ed 2012 (p.645)*

In the above matrix the order of dominance is: B, E, A, D, and C.

Want to suggest an edit? Have some questions? General comments? Let us know how we can make this resource more useful to you.