**
**

**Biconnectivity**
A graph is biconnected, if there are no vertices whose removal
will disconnect the graph.

We can remove any vertex and the rest of the graph will still be connected.

The next graph is not biconnected:

If we remove **C**, the graph will become disconnected.
Such vertices are called **articulation points** or cut-vertices.

There is a related concept for edges:

An edge in a graph is called a **bridge**, if its removal disconnects the graph.

Any edge in a graph, that does not lie on a cycle, is a bridge.
Obviously, a bridge has at least one articulation point at its end,
however an articulation point is not necessarily linked in a bridge.
For example, none of the edges ending in **C** in the above graph, is a bridge

**Example of bridges:**

Here (C,D) and (D,E) are bridges, C and D are articulation points,
while E is not an articulation point.

We can compute articulation points using depth-first search and a special
numbering of the vertices in the order of their visiting.

Here are some more examples of articulation points, bridges, and biconnected graphs:

**Example 1:** C is an articulation point, there are no bridges

**Example 2:** C is an articulation point, CB is a bridge

**Example 3:** B and C are articulation points, BC is a bridge

**Example 4:** B and C are articulation points. All edges are bridges

**Example 5:** Biconnected graph - no articulation points and no bridges

**
**

**Connectivity in directed graphs**
**Definition:** A directed graph is said to be **strongly connected** if for
any pair of nodes there is a path from each one to the other.

**Definition:** A directed graph is said to be **unilaterally
connected** if for any pair of nodes at least one of the nodes is reachable
from the other.

**Definition:** A directed graph is said to be **weakly connected**
if the underlying undirected graph is connected.

**Examples:**

Strongly connected graph:

Unilaterally connected graph:

Weakly connected graph: