Wed, Jun 24, 2015
Cut-vertices (articulation points) in Graph Theory
A vertex $v$ in a connected graph $G$ is called a **cut-vertex** if $G - v$ results in a disconnected graph. Note that $G - v$ is an induced subgraph of $G$ (meaning that $G - v$ contains all the vertices of $G$ except $v$ and a set of edges $G - E_v$, where $E_v$ consists of all the edges incident to $v$). In this article, I implement an algorithm to find the articulation points in an undirected graph. I also explain biconnected components in an undirected graph and concepts such as edge connectivity and vertex connectivity.
Wed, Jun 24, 2015
Cut-edges (bridges) in Graph Theory
An edge $e = uv$ of a connected graph $G$ is called a bridge if $G - e$ is disconnected (it increases the number of components). In this article, I implement an algorithm to find the bridges of an undirected graph using DFS. Next, I describe an algorithm to find strong bridges in directed graphs.