An undirected graph is given by vertices and edges where for every pair . This is usually expressed as . A directed graph is given by vertices and arcs . This is expressed as .
Some questions on graphs:
- Given , does there exist a path between .
- Shortest path between .
- Find largest clique in .
- Does have a Hamiltonian cycle?
- Find chromatic number of .
Connected components of a graph
Given a graph in either the adjacency matrix or adjacency list representation, find the connected components of . A subset is a connected component of if for every there is a path in from to and for every there is no path from any to .
One possible way to do it is using Depth First Search (DFS). We can write this recursively as:
- For every such that and , include in and call .
The output of would give us the connected component of that contains . To obtain a list of connected components one can pick a vertex such that , run and iterate till such a cannot be found.