An undirected graph is a set G=V×E where
E⊂{{v,w}:v,w∈V}Assume V={1,…,n}
aij={10if there’s an edge from itojotherwiseIf k is small, P(Xk=i) depends too much on X0. A good way to measure the popularity of page i would be
pi=defk→+∞limP(Xk=i)The PageRank vector satisfies
p(∞)=Tp(∞)What's the issue with the above graphs? How would you fix it?
Approximate p(∞)≈p(k) for some large k via
p(k+1)=Tp(k)Implement it on this dataset
Show the ten highest ranked pages.
From a given set of nodes, which vertices can I reach?
How much space does that representation required?
Θ(V+E)
Write an algorithm that perform breadth-first search from a given source node s.
Change the BFS algorithm so that you can keep track of a shortest path from s to any node.
Implement DFS, when you're given the set of vertices and an adjacency list.
The Running time of DFS is Θ(V+E)
Sudoku is a puzzle where you're given a 9 by 9 grid partially filled with digits. The objective is to fill the grid subject to the constraint that every row, column, and box (3 by 3 subgrid) must contain all of the digits from 1 to 9.
How can we know what type of edge (u,v) is?
In an undirected graph, every edge is either a tree or a backedge.
An undirected graph is acyclic if and only if there are no back edges
A directed graph is acyclic if and only if there are no back edges.
Given a directed acyclic graph, "sort" the vertices in such a way that the edges are always pointing to the right.
Applications include:
If (u,v)∈E, then
u.f≥v.fModify DFS to implement topological sort
Let G=(V,E) be a directed graph. A subset C⊂V is a strongly connected component if for every pair u,v∈C, there is a path from u to v and from v to u.
Let G=(V,E) be a directed graph with connected connected C1,…,Cn. The component graph is the graph
{Ci:1≤i≤n}×{(Ci,Cj):1≤i,j≤n and there’s a path between Ci and Cj}Given a directed graph G, find its connected components
Let G=(V,E) be a graph. Its transpose graph is the graph
V×{(v,u):(u,v)∈E}Why is it called the transpose graph? What happens to the adjacency matrix when we transpose the graph?
Write a Python code that transforms a graph (given via an adjacency list) to its transpose.
Implement it
Assume that S1,…,Sn are the strongly connected components of a graph G=(V,E) in the order given by the SCC algorithm.
If s∈Si, then DFS-Visit will only reach the vertices in S1,…,Si in the transpose of G.
The SSC algorithm is correct.
A graph G=(V,E) is weighted if it's given with a function w:E→R.
Given an undirected weighted and connected graph ((V,E),w), find a spanning subtree T⊂E with smallest total weight.
G/e: Remove edge and merge the vertices it previously joined
What did we do about common neighbours?
We will remove the guessing part by proving that the greedy choice is optimal
What's the time complexity?
Assume e belongs to some MST T∗ of G. If T′ is a MST of G/e, then T′∪{e} is a MST of G
Sketch proof
w(T′∪{e})=w(T′)+w(e)≤w(T∗∖{e})+w(e)=w(T∗)The greedy choice works.
Assume A⊂E is a subset of some MST.
If S is a cut respecting A and (u,v) is a light edge crossing (S,V∖S), then (u,v) is also part of some MST.
We've reduced guessing an edge to using a particular cut respecting A.
A = {} while A is not spanning: find safe edge e A.add(e) return A
We'll see: Prims, Kruskal
Find the MST of the following graph
How would we get the tree itself?
The time complexity of this algorithm is O((V+E)logV)
Keep track of connected components
We'll need two operations to apply Kruskal
Kruskal's algorithm returns an MST.
What is the time complexity?