Graph Algorithm

Graph-Algorithm

[!info]+ Def: Graph A graph is a pair of $G=(V, E)$ V is the collection of vertices E is the collection of edges

[!info]+ Def: Directed Graph (u, v) and (v, u) are distinct for some edges (u, v) $\in E$.

[!info]+ Def: Undirected Graph (u, v) and (v, u) are identical for all edges (u, v) $\in E$.

Graph Representation

Adjacency list Representation

  • $adj[u]$ is a linked list of all v that (u, v) $\in E$.
    • $adj[0] = {1, 3, 9}$ , $adj[1]= {0, 9, 2}, …$
    • In directed graphs, $dev^{+(v)} = adj[v] $ is the out degree of v

Adjacency matrix Representation

  • $A=[a_{ij}]$ is a $n \times n$ matrix such that $a_{ij} = 1$ if $(v_{i,}v_{j}) \in E$.

DFS Algorithm

[!question]+ What does DFS do?

  • Traverse all vertices in graph, and thereby
  • Reveal properties of the graph.

Four array s are used to keep information gathered during traversal.

[!abstract]+ Four Arrays

  1. $color[u]$ : the color of each vertex visited
    • white: undiscovered
    • gray : discovered but not finished processing
    • black: finished processing
  2. $pred[u]$ : the predecessor pointer pointing back to the vertex from which u was discovered
  3. $d[u]$ : the discovery time
    • a counter indicating when vertex u is discovered
  4. $f[u]$: the finishing time
    • a counter indicating when the processing of vertex $u$ ( and all its descendants ) is finished
\begin{algorithm}
\caption{DFS(G)}
\begin{algorithmic}
\State \textbf{Input}: Graph $G$
\State \textbf{Output}: Vertex traversal of graph $G$
\ForAll{vertex $u \in V(G)$}
    \State $color[u] \gets \text{white}$ \Comment{Initialize}
    \State $pred[u] \gets \text{NULL}$
\EndFor
\State $time \gets 0$
\ForAll{vertex $u \in V(G)$} \Comment{Start a new tree}
    \If{$color[u] == \text{white}$}
        \State \Call{DFSVisit}{$u$}
    \EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{DFSVisit}
\begin{algorithmic}
    \State $color[u] \gets \text{gray}$ \Comment{u is discovered}
    \State $d[u] \gets ++$time \Comment{u's discovery time}
    \ForAll{$v \in \text{adj}[u]$} \Comment{Visit undiscovered vertex}
        \If{$color[v] == \text{white}$}
            \State $pred[v] \gets u$
            \State \Call{DFSVisit}{$v$}
        \EndIf
    \EndFor
    \State $color[u] \gets \text{black}$ \Comment{u has finished}
    \State $f[u] \gets ++$time \Comment{u finish time}

\end{algorithmic}
\end{algorithm}

[!tip]+ The output of DFS

  1. The time stamp arrays: d[v], f[v]
  2. The predecessor array: pred[v]

[!info]+ Def: DFS Forest Use $pred[v]$ to define a graph $F = (V, E_f)$ as follows: $E_{f}= {(pred[v],v)| v \in V,\ pred[v] \neq NULL}$ It is a graph with no cycles, and a collection of trees.

[!abstract]+ HandShaking Theorem If G=(V, E) is an undirected graph \(2|E| = \sum_{u\in V}(deg(v))\) If G=(V, E) is an directed graph \(|E| = \sum_{u\in V} (deg^{-}(v))= \sum_{u\in V} (deg^{+}(v))\)

DFS Time Analysisi

\(T_{DFS}(G)=O(n)+O(1)+T_v(G)\) \(= O(n) + \sum_{u \in V} (2deg^{+}(u)+ O(1))\) \(= O(n) + \sum_{u \in V} (2deg^{+}(u)\) \(= O(n + e)\)

DFS Properties

Time Time-Stamp Structure

[!abstract]+ DFS Properties

  • u is a descendant ( in DFS trees ) of v, if and only if $[d[u], f[u]]$ is a subinterval of $[d[v], f[v]]$.
  • u is an ancestor of v, if and only if $[d[u], f[u]]$ contains $[d[v], f[v]]$ .
  • u is unrelated to v, if and only if $[d[u], f[u]]$ and $[d[v], f[v]]$ are disjoint intervals.

Time-Stamp-1

[!abstract]+ Proof The idea is to consider every case. Assume $d[v] < d[u]$ wlog.

  1. If $f[v] > d[u]$ , then
    • u is discovered when v is still not finished y et ( marked gray) $\Rightarrow$ u is a descendant of v ;
    • u is discovered later than v $\Rightarrow$ u should finish before v;
    • hence we have $[d[u], f[u]]$ is a subinterval of $[d[v] , f[v]]$.
  2. If $f[v] < d[u]$, then
    • Obviously $[d[u], f[u]]$ and $[d[v] , f[v]] are disjoint;
    • Which means that when u or v is discovered, the others are not marked gray;
    • And hence neither vertex is a descendant of the other

Tree Structure

[!abstract]+ Theorem An edge in an undirected graph is either a tree edge or a back edge.

[!abstract]+ Proof Assume $d[u] < d[v]$. Then, v is be discovered while u is gray. Hence v is in the DFS subtree rooted at u.

  • If $pred [v] = u$, $(u, v)$ is a tree edge.
  • If $pred [v] \neq u$, $(u, v)$ is a back edge.

Application

Articulation

[!info]+ Def: Articulation Let G=(V, E) be a connected undirected graph. An articulation point (cut vertex) of G is a vertex whose removal disconnects G Articulation

[!question]+ Given a connected graph G, how to find all articulation points?

  • Brute Force Solution

Brute Force Solution

  1. Remove a vertex and its corresponding edges one by one one from G.
  2. Test whether the resulting graph is still connected or not say by DFS.

The running time is O (n ∗(n + e)) .

Observations

  1. The root of the DFS tree is an articulation point if it has two or more children.
  2. A leaf of the DFS tree is not an articulation point.
  3. And for other internal vertex v in the DFS tree, v is an articulation point if if there is one subtree rooted at a child of v that does not have a back edge which climbs higher than v.
Tackle Observation 3

[!info]+ Def: Low and high Using the discovery time in the DFS tree to define low and high.

If there is a subtree rooted at a children of v which does not have a back edge connecting to a vertex with discovery time smaller than d[v] , then v is an articulation point.

  • Let Low (w) be the smallest value that a descendant of w can climb up by a back edge.
  • We use d[v] to express the “hight” of v.
  • v is “higher” than u if v and u are on the same branch of the DFS tree and d[v] < d[u] .
  • If v and u are on different branches, d[v] and d[u] are not compatible by the time-stamp structure.

BackLink