        \problemdata       % Takes 5 *mandatory* arguments
        {station-channels}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {Rosen \S 7.8, Exercise 16 (Station Channels)}               
                                % Source (if known)
        {S02 PS4-4} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).


\begin{problem}
%Rosen \S 7.8, Exercise 16 (Station Channels)
How many different channels are needed for six stations located at the
distances shown in Table~\ref{stationchannels}, if two stations cannot
use the same channel when they are within 150 miles of each other?

\begin{table}[htbp]


\begin{center}
\begin{tabular}{|c|*{6}{|c}|}
\hline
&1&2&3&4&5&6\\
\hline
\hline
1&--&85&175&200&50&100\\
\hline
2&85&--&125&175&100&160\\
\hline
3&175&125&--&100&200&250\\
\hline
4&200&175&100&--&210&220\\
\hline
5&50&100&200&210&--&100\\
\hline
6&100&160&250&220&100&--\\
\hline
\end{tabular}
\end{center}
\caption{Station distances}\label{stationchannels}
\end{table}


\solution{
We draw a graph (see Figure~\ref{stationgraph}) in which any two
vertices are connected iff the 
locations they represent are within 150 miles of each other.
\begin{figure}[htbp]
\centerline{
\begin{picture}(240, 70)
\multiput(0, 10)(60, 0){5}{\circle*{5}}
\multiput(0, 10)(60, 0){4}{\line(1, 0){60}}
\put(180, 70){\circle*{5}}
\put(120, 10){\line(1, 1){60}}
\put(180, 70){\line(1, -1){60}}
\put(180, 10){\line(0, 1){60}}
\put(-5, -5){\makebox(10, 10){4}}
\put(55, -5){\makebox(10, 10){3}}
\put(115, -5){\makebox(10, 10){2}}
\put(175, -5){\makebox(10, 10){1}}
\put(235, -5){\makebox(10, 10){6}}
\put(185, 65){\makebox(10, 10){5}}
\end{picture}
}
\caption{Graph representing station locations}\label{stationgraph}
\end{figure}
Three colors are necessary and sufficient to color this graph: say
red for vertices 2, 4, 6; blue for 3 and 5; yellow for 1.  Thus three
channels are necessary and sufficient for the stations.
}
\end{problem}
