Connected Components and the Birthday Sign

A connected component in an undirected graph is a set of nodes such that any node in the component can reach any other node in the component via a path of edges. Two sets of nodes are not in a single connected component if there is not path between them.

When many people think about connected components in graphs, they think about: abstract circles and lines, island bridges, computer networks, or the power grid. These are classic examples of graphs and the importance of connected components. Power cannot flow from one end of the city to the other unless there is an edge (i.e. power line) linking the two sides. Similarly, two computers cannot communicate without a network link between them.

In contrast, when I envision connected components, I often go back to a story from childhood: the tragedy of the large, paper, birthday sign. Granted, birthday signs are not the typical example of a graph. And as far as graphs go, they are relatively boring. A single party-sized birthday sign might include 13 nodes (the letters H-A-P-P-Y-B-I-R-T-H-D-A-Y) joined by 11 edges (metal fasteners or small lengths of string). Each node is connected to at most two other nodes -- the letters on either side. And together, they form a single connected component. Except when the sign is broken.

The tragedy of the broken birthday sign is that, as two separate components, the sign does not hang correctly. Instead, the two sides, each containing part of the original message, hang awkwardly down. It is a disheartening sight that has forced more than one party-goer to run from the room and compose themselves.

To break a new birthday sign all that you need is a small rip in the paper -- a single fastener losing its hold. This can happen in a variety of ways. The most popular disasters tend to be: the young kid that believes the sign can support his or her weight, the uncle that was not paying attention while walking, the rogue piñata stick, and the arrival of hungry giraffes.

But despair not. The good news is that, in almost all of these cases, the graph can be restored to a single connected component with a small amount of tape.

----------------

For more about graphs, read about Ann's trip to the City of G'Raph.

NEW at Computation Fairy Tales: A list of stories index by level of CS background. Feedback welcome.

Remember for all the updates, follow CompFairyTales on twitter.