Adjacency matrices?are another way to represent graphs and connections between the different vertices.

What is an adjacency matrix?

• An adjacency matrix can be used to show the?number of direct connections?between two vertices
• An entry of?0?in the matrix means that there is?no direct connection?between that pair of vertices
• In a?simple?graph the only entries are either 0 or 1
• A?loop?is indicated in an adjacency matrix with a value in the?leading diagonal?(the line from top left to bottom right)
  • In an?undirected matrix?the value in the leading diagonal will be?2?because you can use the loop to travel out of and into the vertex in two different directions
  • In a?directed matrix, if the loop has been given a direction, the value in the leading diagonal will be?1?as you can only travel along the loop out of and back into the vertex in one direction
  • For a graph with?no loops?every entry in the leading diagonal will be?0
• An?undirected graph?will be?symmetrical?in the leading diagonal
• The sum of the entries in a?row?is the?in degree?of that vertex
• The sum of the entries in a?column?is the?out degree?of that vertex

What is a walk?

• A?walk?is a?sequence of vertices?that are visited when moving through a graph along its?edges
• Both?edges?and?vertices?can be revisited in a walk
• The?length of a walk?is the?total number of edges?that are traversed in the walk

How do you find the number of walks in a graph?

• Let?M?denote the adjacency matrix of a graph. The (i,?j) entry in the matrix?M^k?will give the number of walks of length?k?from vertex?i?to vertex?j
• If there is an entry of?2?in the leading diagonal of the matrix, this should be changed to a?1?before?the matrix is raised to a power
• The number of walks, between vertex?i?and vertex?j, of length?n?or less can be given by the matrix?Sⁿ, where?Sⁿ?=?M¹?+?M^2?+…+…Mⁿ
  • If all of the entries in a single row of?Sⁿ?are non-zero values then the graph is?connected

A?weighted adjacency table?gives more detailed information about the connection between different vertices in a?weighted graph.

What is a weighted adjacency table?

• A weighted adjacency table is different to an adjacency matrix as the?value?in each cell is the?weight?of the edge connecting that pair of vertices
  • Weight could be cost, distance, time etc.
• An?empty cell?can be used to indicate that there is?no connection?between a pair of vertices
• A directed graph is?not?symmetrical along the leading diagonal (the line from top left to bottom right)
• When drawing a graph from its adjacency table be careful when labelling the edges
  • For an?un-directed graph?the two cells between a specific pair of vertices will be the same so connect the vertices with?one edge?labelled with the relevant weight
  • For a?directed graph?if the two cells between a specific pair of vertices have different values draw?two lines?between the vertices and label each with the correct weight and direction
• A weighted adjacency table can be used to work out the weight of different?walks?in the graph