Date: 07/22/97 at 14:09:34 From: kim Parsons Subject: Graph theory Television transmitters in a region are to be assigned a channel over which to operate. If two transmitters are within 150 kilometers of each other, they must be assigned different channels. The chart below represents 6 transmitters and their distance from each other. N.Y.A N.Y.B Harris. Allen. Phila. Balt. N.Y.A 0km 20km 280km 100km 160km 315km N.Y.B 0km 260km 80km 140km 305km Harrisburg 0km 175km 165km 145km Allentown 0km 80km 240km Philadelphia 0km 155km Baltimore 0km Construct a graph that represents this problem and use it to determine the number of channels needed for the region.
Date: 07/28/97 at 12:44:56 From: Doctor Rob Subject: Re: Graph theory Make a vertex for each transmitter. For each pair of transmitters with a distance less than 150km, draw an edge. Channels must be different at each end of each edge. All three channels must be different at each corner of a triangle. All four channels must be different at each vertex in a complete graph on four vertices, and so on. (This last rule doesn't apply to this example. The problem is reduced to coloring the vertices of this graph with a minimum number of colors. It looks to me as though three channels will be required for NYA, NYB, and Allentown. Philadelphia can be the same as NYA. Baltimore and Harrisburg can be anything but unequal to each other, since they are connected only to each other and not to the rest. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.