Associated Topics || Dr. Math Home || Search Dr. Math

### TV Transmitters

```
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
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/
```
Associated Topics:
High School Equations, Graphs, Translations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search