3.15 Adjacency matrices and walks 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 of an adjacency matrix show?
- The number of edges from vertex to vertex .
- 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 entry of give?
- The number of walks of length from vertex to vertex .
- How do you count walks of length at most from to ?
- Read the entry of .
- 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 the probability of moving from to .
- What do the columns of a transition matrix add up to?
- 1
- How do you build 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 steps found?
- What equation gives the steady state?
- with the entries of 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.