Reachability

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)

Dominance

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.