Introduction
This third game in the Colorful Mathematics series
also deals with graphs, but presents a variation on the
concept of the previous game.
To review, a graph is a group of circles
("vertices") some of them connected by lines
("edges"). This time, the edges must be colored in
such a way that those connected to a common vertex receive
different colors. The smallest number of colors that can be
used is now called the edge chromatic number of a graph. The
goal of this game is for you to devise ingenious methods to
try to get as close as possible to this number both with the
sample graphs provided and any graph created by the player.
The concept of a graph is very important in mathematics and
industries. For a simple example, imagine that in a hockey
league, a few games remain to be played until the end of the
season, each team playing at most once each day and at most
once against any other team. Now think of teams as vertices
and connect two of them by an edge if they have a game
remaining to play against each other. Then we get a graph and
the smallest number of days required to complete the season is
nothing else but the edge chromatic number of the graph, the
number of days left corresponding to the number of colors
used, right?
Introduction
This game is another variation on the concept of a graph and
its chromatic number, but you will now play against the
computer! If you draw a bunch of circles, called vertices, and
if you join some of them with lines, called edges, you get
what is called a graph. You are now ready for the game.
First, you must choose the number of colors allowed; then,
you can color the vertices alternately with the computer in
such a way that two vertices connected by an edge receive
different colors. You win the game if you succeed to color the
entire graph with the number of colors fixed at the beginning,
otherwise the computer wins. It is certainly easy to win by
choosing a large number of colors at the beginning, but the
goal of the game is for you to devise ingenious methods to
find the smallest possible number of colors for which you can
always win, regardless of the opponent. This number is called
the two-player chromatic number of the graph.
The concept of a graph is very important in mathematics and
industries. Imagine, for example, that in a pet shop you buy
several fish, that we represent as vertices, and join two of
them by an edge, if one fish might eat the other. You want to
buy enough aquariums to hold them all without some fish eating
others. The clerk is helping you put the fish in the aquariums
but is actually trying to force you to buy as many aquariums
as possible. This will happen, for example, if the clerk put a
big fish in each of the aquariums, and a small fish remains to
be placed. The smallest number of aquariums required so that
the clerk is unable to force you to buy another one,
regardless of his strategy, is the two-player chromatic number
of the graph; the number of aquariums corresponding to the
fixed number of colors.
Introduction
This fifth game in the Colorful Mathematics series
introduces another important property of graphs, that of a
dominating set.
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? |
