Tuesday, November 20, 2012

[bglpqszm] Word graph

Consider a fairly large graph where nodes are all words, and an edge connects two words if they differ by one letter, either by adding or subtracting one letter (EAT - EAST) or changing one letter (LUCK - LOCK).  What is the diameter of the largest connected component?  What is the most needed new word or words to connect the two largest connected components?  Any other interesting questions?

The size of the graph should cause many questions to be computationally challenging.  For a greater challenge, also add all pairs of words, allowing edges like FASTER - FASTPER (fast per).

No comments :