Solutions to Three Graph Theory Problems

Consider a set of four-letter words. Two four-letter words are said to be adjacent if they differ in only one position. So, for example, lame is adjacent to same, lime, late and lamb among others.

(a)Consider the following small set of four-letter words: {gate, game, rate, rats, star, part, pant, path, ants, bath, cats, stab}

• Draw the graph on this set.
• Write down the adjacency list representation.
• How many edges are there?
• How big is the largest connected component?

(b) (This part needs coding) You are provided with a list of 1024 common four-letter words (on the website).  Build the adjacency list representation of the graph and then answer the following questions based on it.

• How many edges are there?
• What are all the neighbors of word?

(c) There’s a type of word puzzle where you have to transition from one word to another changing only one letter at a time. (Naturally it is cutest when the start and end words are related!) For example: cats --> mats --> mate --> mace --> mice

Which algorithm from class is useful in finding the best solution to such a word puzzle?

Implement the algorithm and use your graph from part (b) to solve the following word puzzles. Submit the solutions in your write-up (Word-puzzle lovers, beware: your solu- tions must use only words that are in the given word list.)

• Transform root into tree
• Transform frog into toad
• Transform foal into pony

Given is an undirected graph G that represents a map of a town: each vertex corresponds to an intersection and each edge corresponds to a (two-way) road between two intersections. After living happily in this town for years, its inhabitants suddenly realized that they cannot get to all the places in their town! Help them to find the smallest number of roads they need to build to be able to go from any intersection to any other intersection in this town. In other words, find the smallest k such that, after adding k edges to the graph, it becomes connected. Design an O(m + n) algorithm for this problem. (Recall that n is the number of vertices and m the number of edges in G.)

Given is an a b matrix where every cell corresponds to either an empty space or an obstacle. This matrix represents a maze and in it are also two things: things One and thing Two. The things start at different empty spaces. And, somehow, they got synchronized: They do exactly the same movements—when thing One goes west, so does thing Two; when thing One goes east, so does thing Two; and the same happens when they go south or north. They move at the same time: For example, if thing One is east of thing Two and they move east, both things move. The things cannot go to a location where there is an obstacle (or the other thing, unless it is moving away). For example, if there is an obstacle east of thing One but not of thing Two, if they go east only thing Two moves. Or, if east of thing One there is an obstacle and west of it there is thing Two, if they try to move east, they will stay in their current locations as thing One is blocked by the obstacle and thing Two by thing One.

Things One and Two want to get out of the house, and they want to do so at the very same time (that is, they want to leave the house with the same move). The things get out of the house if they move north in row 1, south in row a, west in column 1, or east in column

This is proving to be very tricky. Please help them by designing an O((ab)2) algorithm that will tell them how to get out in the smallest number of moves (or it will tell them that the task is impossible).