Evolution of Connected Components Animation
What happens when you start with an empty graph and add random edges between vertices? As you add more and more edges, the number of connected components in the graph can be expected to drop, until finally the graph is connected. An important result from the theory of random graphs states that such graphs very quickly develop a single ``giant'' component which eventually absorbs all the vertices.

In this animation, we watch the evolution of the giant component under random edge insertions. The component formed by merging two different component takes the color of the larger of the two parts, so we can see how orange happens to come to dominate the graph as the components merge.

Download:

  connect.gif - The Animation.
  connect.nb - Notebook file.

These animations were produced using Combinatorica -- see www.combinatorica.com and our book Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica for more information.

Check out our dfs/bfs, connected components, Hamiltonian cycle, Eulerian cycle, shortest path, transitive closure, and minimum spanning tree animations!