# Jan 26. Graphs, connected components

Graphs

An undirected graph $G$ is given by vertices $V$ and edges $E \subseteq V \times V$ where $(x,y)=(y,x)$ for every pair $x,y \in V$. This is usually expressed as $G = (V, E)$. A directed graph $D$ is given by vertices $V$ and arcs $A \subseteq V \times V$. This is expressed as $D = (V, A)$.

Some questions on graphs:

• Given $s, t \in V$, does there exist a path between $s,t$.
• Shortest path between $s,t$.
• Find largest clique in $G$.
• Does $G$ have a Hamiltonian cycle?
• Find chromatic number of $G$.

Connected components of a graph

Given a graph $G$ in either the adjacency matrix or adjacency list representation, find the connected components of $G$. A subset $U\subseteq V$ is a connected component of $G$ if for every $x,y \in U$ there is a path in $G$ from $x$ to $y$ and for every $z \not\in U$ there is no path from any $x \in U$ to $z$.

One possible way to do it is using Depth First Search (DFS). We can write this recursively as:

$DFS(G, s)$:

• Initialize $Visited = \{s\}$
• For every $j$ such that $\{s, j\} \in E$ and $j \not\in Visted$, include $j$ in $Visited$ and call $DFS(G, j)$.

The output of $DFS(G, s)$ would give us the connected component $U$ of $G$ that contains $s$. To obtain a list of connected components one can pick a vertex $t$ such that $t \not\in U$, run $DFS(G, t)$ and iterate till such a $t$ cannot be found.

Advertisements