Cut Vertices

There's a total of 1 notes tagged with "Cut Vertices".

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.