Starting with any graph, one color is available to select some of the vertices so that every vertex is either colored or connected by an edge to a colored one; this then, is a dominating set.The goal is to find the smallest number of vertices required to accomplish this, or in other words, the smallest size of a dominating set. This number is called the dominating number of the graph and you will have to create ingenious methods to get as close as possible to this number.
This property of a graph is important in mathematics and industries. As a simple example, think of street corners as vertices, and join two of them by an edge if there is a road between them. On how many street corners should ice cream stands be placed so that nobody should have to go further than one block to get an ice cream? The smallest such number is nothing else but the dominating number of the graph, where ice cream stands should be placed on the street corners from the dominating set, right?
To play the game, you select the vertices by painting them blue, the only color available. The computer will provide feedback as soon as a dominating set is achieved. A simple algorithm has been programmed and is used by the computer to check if it can do better, providing appropriate feedback adapted to the difficulty level.
|INFO:||A quick explanation of the game and other commands.|
|DRAW:||The mode "VERTICES" will clear the drawing board to draw vertices on a new graph.|
|The mode "EDGES" will let you add the edges to your graph, and you can come back to this mode at any time to add or remove edges on your graph.|
|PAINT:||In the mode "COLORS", one color is available to select a dominating set.|
|The mode "CLEAR" will remove all colors of the graph.|
|UNDO:||You can successively undo the last operations performed; for example, while selecting your dominating set, "UNDO" will remove the colors one by one in reverse order.|
|GRAPHS:||A set of six sample graphs are available for each of ten pages, presented in increasing levels of difficulty.|
|SAVE:||One graph, completed or in progress, can be saved for each sample graph provided. Use the keyboard to type a title.|
|QUIT:||Quit the game to return to the main menu.|