Adjacency Matrices for Directed Graphs

Directed Graph

Definition

A directed graph (or digraph) is a set of vertices and a set of directed edges between some of the pairs of vertices. We may move from one vertex in the directed graph to another vertex if there is a directed edge pointing in the direction we wish to move.

Example

Consider the directed graph:

The graph has:

4 vertices, , , , and
Directed edges are arrows
- An edge may be directed to itself ()
- An edge may be directed in both directions ()
- There may be more than one directed edge from 1 vertex to another ()

Consider the number of ways to get from do travelling exactly 3 edges

Unfortunately, this method doesn't scale.
We can use Matrices! Consider the matrix whose th entry is the number of directed edges from

Then, using matrix multiplication, we compute

See how the th entry of is , which is the number of distinct 3-edged paths from .

Adjacency Matrix

Definition

The adjacency matrix of a directed graph is the matrix whose th entry is the number of directed edges to

Theorem

Consider the directed graph with vertices .
For all positive integers , the number of distinct -edged paths from is given by the th entry of

Proof

We will prove this by induction on

Let be the open sentence: the number of distinct -edged paths from is given by the entry of

Base case: The result is true for P(1), since the entry of is by definition the number of distinct 1-edged paths from .

Inductive Step
Assume the inductive hypothesis
We wish to prove
Denote the entry of by , so that the number of distinct -edged paths from to is
Consider the entry of , denoted by

Note that every edged path from is of the form

for some
By the inductive hypothesis, there are distinct -edged paths from to .
Since there are distinct 1-edged paths from , there are distinct - edged of the form given by (1).
Thus, the total number of -edged paths from is given by

which is , the th entry of .

Therefore the statement is true for , and is true for all integers by POMI

Example Problem

An airline company offers flights between the cities of Toronto, Beijing, Paris and Sydney. You can fly between these cities as you like, except that there is no flight from Beijing to Sydney, and there is no flight between Toronto and Sydney in either direction.

We label Toronto as , Beijing as , Paris at , and Sydney as

We construct the adjacency matrix as

Since we can take at most 5 flights, we will compute the matrices like permutations:

a) If you depart from Toronto, how many distinct sequences of flights can you take if you plan to arrive in Beijing after no more than 5 flights? (You may arrive at Beijing in less than 5 flights and then leave, provided you end up back in Beijing after no later than the 5th flight).

We can take the nd entry of each matrix, since we can also take less than 5 flights

Thus there are 32 distinct permutations of ways to get from Toronto to Beijing in 5 or less flights.

b) Suppose you wish to depart from Sydney and arrive in Beijing after the 5th flight. In how many ways can this be done so that your second flight takes you to Toronto?

We compute the number of ways to fly from Sydney to Toronto in 2 flights, and Toronto to Beijing in 3 flights, and multiply them:

c) Suppose you wish to depart from Sydney and arrive in Beijing after the 5th flight. In how many ways can this be done so that you visit Toronto at least once?

We can try counting the number of flight to Toronto after the first flight, and add the second, third, etc. But this leads to the issue where, if Toronto shows up twice, it is double counted.

As such, we will find the complementary event instead. That is, we find all the possibilities that do not visit Toronto, and subtract by the number of flight that go from Sydney to Beijing.

We can accomplish this by removing Toronto from the directed graph.

After some calculations, we find

The entry of shows that there are 5 distinct ways to fly from Sydney to Beijing in 5 flights without stopping in Toronto. Since the entry of shows that there are 19 ways to fly from Sydney to Beijing in 5 flights, there must be distinct ways to fly from Sydney to Beijing in 5 flights while visiting Toronto at least once.