THE DOMINATING NUMBER OF A GRAPH -------------------------------- PART 3 ------ OF -- `COLOURFUL MATHEMATICS' --------------------- This is the third of a series of educational mathematical games for curious people of all ages, introducing serious mathematical concepts in the form of colourful games. Draw a bunch of circles, which we call vertices, and join them by lines, which we call edges; you get what is called a graph. Now colour some of the vertices in such a way that each vertex is either coloured or joined by an edge to a coloured one and you get what is called a dominating set. The smallest number of vertices required to accomplish this, or if you wish the smallest size of a dominating set, is called the dominating number of the graph. The goal of this game is to experience with graphs and try to get as close as possible to this dominating number, not an easy matter at all as you will see. There is a simple algorithm programmed in the game and when you are done colouring your graph, the computer will check if it can do better. To tie the computer is a great achievement, but it is also possible to beat it! Indeed finding the dominating number of a graph is a very difficult problem, even for today's most powerful computers; even on a tie with the computer, try to see if you cannot do better, or try to show that you really have the ultimate solution. Some sample graphs are provided, but you can and should draw your own. This process of experiencing a problem and understanding its difficulties is, we believe, at the root of mathematical and scientific reasoning. The goal of this software is to help develop this skill. The concept of a graph is very important in mathematics and industries. Think of an airline company tracing routes; cities are thought of as vertices and routes as edges. Or think of telephones as vertices and edges being the local connections between them. As a simpler example, think of ice cream stores as circles and join two of them by an edge if they offer the same flavours. How many ice cream parlours should you visit if you wish to taste all flavours? The smallest such number is nothing else but the dominating number of the graph. Hardware requirement: -------------------- A colour monitor is required as this is a colouring program; for technical reasons, an EGA/VGA monitor is actually necessary. A mouse is also essential; once the program is started, the mouse (with the left button) is used through "clicking" command boxes, drawing and colouring. The keyboard is used in the GRAPH/SAVE menu to type a title for your graph if you wish one. The computer will check your graph after each colouring and will let you know if you already have a dominating set. Then the computer checks the size of your dominating set and uses its own simple algorithm to test if it can do better. Installation: ------------- Insert the disk in drive A: and type A:INSTALL; the program will install itself on your hard drive C. To start the game, type "DEMODMT". You can also run the program from a floppy but this will be much slower as the computer must sometimes read some data. The Commands: ------------- 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 on 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 "COLOURS", you have 1 colour available to select your dominating set. The mode "CLEAR" will remove all colours of the graph. UNDO: You can successively undo the last operations performed; for example while colouring a graph, UNDO will successively remove the colours one by one. MAPS: A set of 6 sample graphs are available for each of the four pages, and you can save one graph for each one provided for a total of 48. You can thus save completed graphs or just work in progress. SAVE: You can save 6 graphs on each page, using the keyboard to type a title if you wish. QUIT: Quit the game. `Colourful Mathematics': ------------------------ This is a series of educational mathematical games dealing with serious mathematical concepts. It took over a hundred years for mathematicians to prove that four colours were sufficient to colour any map in such a way that neighbouring regions receive diferent colours. This is the topic of the first game, `The Four Colour Map Problem'; you can use maps provided or draw your own, and try to use the fewest possible number of colours. Think of methods and tricks to save colours; it is in general not easy at all to use only four colours but the point is that there must be a way to do it. Sometimes you will notice that three colours is enough but more often four is necessary. The second game deals with the more general concept of graph and its chromatic number. A graph consists of circles, which we call vertices, some of them joined by lines, which we call edges. Now you must colour the vertices in such a way that two vertices joined by an edge receive different colours. The smallest possible number of colours that can be used for a graph is called the chromatic number of the graph. The goal of this game, apropriately called `The Chromatic Number of Graphs', is to get a close as possible to this number. This is a very difficult problem in general and is related to many important problems in computer science and industries. There is a simple algorithm programmed in the game and the computer will tell you, first if you make a mistake, but also if it can do better than you. To tie the computer is a great achievement and it is even possible to beat it. Indeed, there are no perfect algorithm to compute this chromatic number that uses a reasonable amount of time. Have fun! The third game introduces another important property of graphs, that of a dominating set. Starting with any graph, you have one colour to select some of the vertices so that each vertex is either coloured or is connected to a coloured one, this is what is called a dominating set. The goal is to achieve this using the smallest number of coloured vertices, or if you prefer you must find a dominating set with the fewest possible number of vertices. This problem is again very difficult even for today's computers and in some sense has the same degree of difficulty as the previous problem. The basic idea is as follows: if you were in charge of a telephone company, you would not really want to install telephone booths at every street corner because of the cost involved, but you would rather have just enough so that people could walk to one say in a reasonable amount of time. These prime locations would then roughly form a dominating set; and the smaller that set the more economical it will be for the company. Author: ------- Comments and suggestions are most welcomed! Please write to: Claude Laflamme 5904 Silver Ridge Dr. N.W. Calgary, Alberta Canada T3B 3R9 or use electronic mail to: laflamme@acs.ucalgary.ca