Zhancun Mu

I am a student at PKU and here is my blog.

1 minute read

VIdeo Link

Graphs

Diagraph $G=(V,E)$.

  • Set of $V$ of vertices.
  • Set $E \subseteq V\times V$ of edges.

Undirected graph: $E$ contains unordered pairs.

$ E =O(V^2)$. $G$ connected $\implies E > V \implies\lg E =\Theta (\lg V)$.

Graph representations:

Adjacency matrix of graph $G=(V,E)$,where $V=\{ 1,2,\dots,n \}$,is the $n\times n$ matrix given by

\[A[i,j]=\begin{cases} 1, &\text{if }(i,j) \in E \newline 0, &\text{else} \end{cases}\]

$\Theta(V^2)$ storage $\implies$ dense representation.

Adjacency list of $v\in A$ is the list $Adj[v]$ of vertices adjacent to $v$. $|Adj[v]|=\deg(v)$ for undirected and out deg for directed.

Handshaking lemma(undirected graph):

\[\sum_{v\in V}\deg (v)=2|E|\]

For undirected graphs $\implies \Theta(V+E)$ storage.

Sparse representation: often better than adj. matrix.

Minimum spanning trees

Input: Connected, undir graph $G=(V,E)$ weight function $w: E \to \mathbb R$.

  • For simplicity, assume all edge weights are distinct.

Output: A spanning tree $T$ (connects all vertices) of minimum weight

\[w(T)=\sum_{(u,v)\in T}w(u,v)\]

Optimal substructure: MST $T$. Remove $(u,v)\in T$. Then $T$ is partitioned into two subtrees $T_{1}$ and $T_{2}$.

Theorem $T_{1}$ is MST for $G_{1}=(V_{1},E_{1})$, the subgraph of $G$ induced by vertices in $T_{1}$.

Proof: Cut & Paste:

\[w(T)=w(u,v)+w(T_{1})+w(T_{2})\]

If $T_{1}’$ better than $T_{1}$ for $G_{1}$, then $T’=\{ (u,v) \}\cup T_{1}’ \cup T_{2}$ is better than $T$.

Overlapping subproblems? Yes. Dynamic programming? But MST exhibits more powerful property.

Greedy algorithm

Hallmark: greedy choice property. A locally opt. choice is globally opt.

Theorem: Let $T$ be MST of $G=(V,E)$ and let $A\subseteq V$, sup. $(u,v) \in E$ is least weight edge $e$ connecting $A$ to $V-A$. Then, $(u,v)\in T$.

Proof: Sup. $(u,v) \notin T$. Cut & paste.

Consider a unique simple path from $u$ to $v$ in $T$. Swap $(u,v)$ with the first edge on this path that connects a vertex in $A$ to a vertex in $V-A$. So a lower weight spanning tree than $T$ results.

Prim’s Alg

Idea. Maintain $V-A$ as a priority queue $Q$.Key each vertex in $Q$ with weight of the least-weight edge connecting it to a vertex in $A$.

Q<-V
key[v]<-INF forall v im V
key[s]<-0 for arb. s in V
while Q is not empty
  do u<- Extract-Min(Q)
    for each v in Adj[u]
      do if v in Q and w(u,v)<key[v]
         then key[v]<-w(u,v)
	      T[v]<-u
	      DECREASE-KEY(Q,v,w(u,v))

Analysis: Handshaking $\implies$ $\Theta(E)$ decrease-keys.Time$=\Theta(V\cdot T_{extract}+E \cdot T_{decrease})$.

  • array: $\Theta(V^2)$.
  • binary heap: $\Theta( E \lg V)$
  • Fibonacci heap: $O( E + V \lg V )$

Comments

You May Also Enjoy