\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\frametitle{Lecture 31: Articulation Points and Biconnected Components }
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi 12.5

\vspace{1cm}
An application of the depth-first search spanning tree.

\vspace{4cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Articulation Points}
\vspace{5cm}
\begin{definition}[ Articulation Point ] 
Let $G = (V,E)$ be a graph.
A vertex $v$ in $G$ is an {\bf articulation point} (AP) if
removing $v$ from $G$ increases the number of connected components of $G$.
\end{definition}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{lemma}[12.3] 
Let $G=(V,E)$ be a graph.  A vertex $v\in V$ is an articulation 
point of $G$ if and only if there
are two vertices $x$ and $y$ in $V$ such that $x \ne y \ne v$ and
every path between $x$ and $y$ includes $v$.
\end{lemma}

\vspace{8cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ Biconnected Component ]
Let $G=(V,E)$ be a graph.
A subgraph of $G$ is {\bf biconnected} if it is connected and
has no articulation points.
A maximal biconnected subgraph of $G$ is
called a {\bf biconnected component} of $G$.
\end{definition}


\begin{lemma}
Let $G=(V,E)$ be a graph.  If $G$ has a Hamiltonian cycle
then $G$ must have no APs, equivalently, $G$ must be biconnected.
\end{lemma}

\vspace{4cm} 

Exercise: Find a biconnected graph which does not have a Hamiltonian cycle.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
How can we find the Articulation points in a {\bf connected} graph $G$?

\bigskip
Algorithm 1.

\begin{itemize}
\item[]
{\bf set} AP = $\phi$. \\
{\bf for} each $v \in V$ do \\
\quad {\bf if} removing $v$ from $G$ disconnects $G$ {\bf then} \\
\quad \quad {\bf set} AP = AP $\cup \{v\}$. \\
\quad {\bf end if} \\
{\bf end for} \\
{\bf output} AP.
\end{itemize}

\vspace{3cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Algorithm 2

\bigskip
{\bf Step 1:} Construct a DFS spanning tree $T$ for $G$ and  \\
 \quad number the edges in $T$ in the order visited during the DFS.

\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\bf Step 2:} Traverse $T$ in pre-order.  If a vertex $v$ has a backedge $e_n$ from $u$ to $v$,
  \ number all edges on the walk \  
 $\color{blue} v \, e_1 \, x_1 \, e_2 \dots x_{n-2} \, e_{n-1} \, u \, e_n \, v$
 \ from $v$ down to $u$ and back to $v$ with the edge number on $e_1$.


\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
What are the articulation points? 
% The are the vertices in $T$ whose incident edges are not numbered the same.
\vspace{2cm}

What are the biconnected components?
% They  are the subgraphs of $G$ with equal edge numbers in $T$.
\vspace{3cm}

Why is this algorithm better than Algorithm 1? \\ 
If implemented carefully, can be done in time proportional to $|V|+|E|$.
\vspace{2cm}
\end{frame}

