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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s