3.15 Adjacency matrices and walks

3.15 Adjacency matrices and walks Flashcards

IB Maths: Applications and Interpretation HL: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

14 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 14 cards
What does entry (i,j)(i,j) of an adjacency matrix show?
The number of edges from vertex ii to vertex jj.
Features of the adjacency matrix of a simple undirected graph?
Entries 0 or 1, zeros on the leading diagonal, and symmetric.
What is a walk?
A sequence of edges where each starts at the end of the previous one; repeats are allowed.
What does the (i,j)(i,j) entry of Ak\mathbf{A}^k give?
The number of walks of length kk from vertex ii to vertex jj.
How do you count walks of length at most kk from ii to jj?
Read the (i,j)(i,j) entry of A+A2+⋯+Ak\mathbf{A}+\mathbf{A}^2+\cdots+\mathbf{A}^k.
What does a row sum of the adjacency matrix of a directed graph give?
The out-degree of that vertex.
What does a column sum of the adjacency matrix of a directed graph give?
The in-degree of that vertex.
What is a weighted adjacency table?
A table whose entries are the weights (cost, distance, time) of the edges between vertices.
What is a transition matrix?
A matrix of probabilities of moving between states, with entry (i,j)(i,j) the probability of moving from jj to ii.
What do the columns of a transition matrix add up to?
1
How do you build T\mathbf{T} from a graph where each link is equally likely?
Divide each link from a vertex by the number of links leaving it, and put these down that vertex's column.
How is the state after nn steps found?
sn=Tns0\mathbf{s}_n=\mathbf{T}^n\mathbf{s}_0
What equation gives the steady state?
Ts=s\mathbf{T}\mathbf{s}=\mathbf{s} with the entries of s\mathbf{s} summing to 1.
What does PageRank measure?
The long-run probability that a random surfer is on a page; a higher value means a more important page.

Flashcards