Home » 國際課程 » IB課程 » Details

IB DP Maths: AI HL復(fù)習(xí)筆記3.10.2 Walks & Adjacency Matrices

Category: IB課程, 教材筆記, 福利干貨 Date: 2022年7月20日下午6:08

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

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

Let?G?be the graph below.

3-10-2-ib-hl-ai-walks--adjacency-matrices-we-1

Write down the adjacency matrix for?G.

3-10-2-ib-hl-ai-walks--adjacency-matrices-we-1-solution

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

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²^?+…+…Mⁿ
- If all of the entries in a single row of?Sⁿ?are non-zero values then the graph is?connected

Read the question carefully to determine if you need to choose a specific power for the adjacency matrix or if you need to play around with different powers!

3-10-2-ib-hl-ai-walks--adjacency-matrices-we-2a-solution

b)Find the number of walks of length 4 from vertex B to Vertex E.

3-10-2-ib-hl-ai-walks--adjacency-matrices-we-2b-solution

c)Find the number of walks of 3 or less from vertex A to vertex C.

3-10-2-ib-hl-ai-walks--adjacency-matrices-we-2c-solution

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

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