\documentclass[11pt]{article}
\usepackage{dimacsmodules}
\usepackage{graphics}  %%invoke this if graphics won't work otherwise
\usepackage{theorem}
\input amssym.def

\setlength{\topmargin}{0in}     % top of paper to head (less one inch)
\setlength{\headheight}{0in}    % height of the head
\setlength{\headsep}{0in}       % head to the top of the body
\setlength{\textheight}{9.00in} % height of the body
\setlength{\oddsidemargin}{0mm} % left edge of paper to body (less one inch)
\setlength{\evensidemargin}{0mm} % ditto, even pages
\setlength{\textwidth}{6.5in}   % width of body
\setlength{\topskip}{0in}       % top of body to bottom of first line of text
%\setlength{\footheight}{0.25in} % height of footer
%\setlength{\footskip}{0.50in}   % bottom of text to bottom of foot

%--------------from the book style file----------------------

\newcommand{\bC}{{\bf C}}
%\textwidth 16.2cm
%\evensidemargin 2mm
%\oddsidemargin 2mm
\newcommand{\sk}{\medskip}
\newcommand{\bsk}{\bigskip}
%\special{papersize=8.5in,11in}
%\newtheorem{thm}{Theorem}[chapter]
\newtheorem{thm}{Theorem}[section]
\newtheorem{thrm}{Theorem}%[chapter]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{coro}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}

%\theoremstyle{definition}
\theorembodyfont{\rmfamily}
\newtheorem{defn}[thm]{Definition}
\newtheorem{examp}[thm]{Example}
\newtheorem{xca}[thrm]{Exercise}

%\theoremstyle{remark}
\newtheorem{rmk}[thm]{Remark}

%\numberwithin{section}{chapter}
%\numberwithin{equation}{chapter}
%%\numberwithin{thm}{section}
%\numberwithin{table}{section}
%%\numberwithin{figure}{section}

%\renewcommand{\include}{\input}

\parindent2em
\newcommand{\nsk}{\addvspace{-5ex}}
\newcommand{\bt}{\begin{thm}}
\newcommand{\et}{\end{thm}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\el}{\end{lemma}}
\newcommand{\br}{\begin{rmk}}
\newcommand{\er}{\end{rmk}}
\newcommand{\bc}{\begin{coro}}
\newcommand{\ec}{\end{coro}}
\newcommand{\bd}{\begin{defn}}
\newcommand{\ed}{\end{defn}}
\newcommand{\bex}{\begin{examp}}
\newcommand{\eex}{\end{examp}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bp}{\begin{prop}}
\newcommand{\ep}{\end{prop}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bxc}{\begin{xca}}
\newcommand{\exc}{\end{xca}}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\ink}{\rule{.8ex}{1.5ex}}   %end of proof marker
\newcommand{\Llr}{\Longleftrightarrow}
\newcommand{\Lr}{\Leftrightarrow}
\newcommand{\imp}{\Longrightarrow}
\newcommand{\sm}{\setminus}
\newcommand{\seq}{\subseteq}
%\newcommand{\C}{\mathfrak c}
\newcommand{\C}{\frak c}
%\renewcommand{\chaptername}{SECTION}
%\renewcommand{\appendixname}{APPENDIX}
%\renewcommand{\bibname}{REFERENCES}
\renewcommand{\contentsname}{TABLE OF CONTENTS}

\renewcommand{\thefigure}{\thesection.\arabic{figure}}
\renewcommand{\thetable}{\thesection.\arabic{table}}

%--------------from the book format----------------------

%\newcommand{\pinch}{\vspace{-9pt}}
\pagenumbering{roman}

\begin{document}
\begin{publicity}%{}


\begin{center}
\vspace{.4in}
{\Large \bf DIMACS EDUCATIONAL MODULE SERIES}

\vspace{1.0in}

{\Large \bf MODULE 03-2}\\[2mm]
{\Large \bf Facility Location Problems}\\
{\large \bf Date prepared:} March 27, 2003 

\vspace{.5in}

{\bf R. S. (Chuck) Tiberio\footnote{Written under the auspices 
of DREI98, supported by NSF Grant DMS 9412914}}\\
{\bf Wellesley High School}\\
{\bf Wellesley, MA 02481}\\
{\bf email: tiberio@tiac.net}\\

\end{center}
\vfill

\end{publicity}

\setcounter{page}{0}
\newpage

\begin{center}
{\large \bf Module Description Information}
\end{center}

\begin{itemize}
\item {\bf Title:}

 \textbf{Facility Location Problems}


\item {\bf Author(s):}

R. S. (Chuck) Tiberio

\item {\bf Abstract:}

     This module investigates the placement of emergency and service
facilities in a network of towns connected by roads.  Criteria for placement and algorithms for implementation are
also discussed.

\item {\bf Informal Description:}

    Sometimes commonly used public facilities (like a fire station or a
shopping mall) are built where there is available land.  Perhaps it would be better to build them in places which
would maximize their use by the general public or facilitate their use by emergency personel.  This module will
address such questions and discuss possible methods of solution.

\item {\bf Target Audience:}

     The intended target audience is high school seniors of average
mathematical ability who are taking a course in discrete mathematics. However the module would certainly be
appropriate for college students in a similar course.



\item {\bf Prerequisites:}

  Students should be comfortable with the concept of graph and using a
graph to model a physical situation.  They should be familiar with basic matrix operations.  Ability to use a
TI-83 calculator would also be helpful.

\item {\bf Mathematical Field:}

 Graph Theory (including weighted graphs)\\
     Elementary Matrix Operations


\item {\bf Applications Areas:}

    The author's intended application for this module is pedagogical.  A
student with a basic  understanding of graphs and matrices can now see how these can be applied in a "real world"
setting.

\item {\bf Mathematics Subject Classification:}

 Primary Classification: 90B80, 05C85

\item {\bf Contact Information:}

R. S. Tiberio \\
     Wellesley High School \\
     50 Rice Street \\
          Wellesley, MA 02481\\
     email:  tiberio@tiac.net


\item {\bf Other DIMACS modules related to this module:}

None at this time

\end{itemize}



\newpage

\setcounter{page}{0}
\pagenumbering{arabic}
\tableofcontents
%\addcontentsline{toc}{chapter}{\hspace*{2.4ex} ABSTRACT}

\newpage
\section*{ABSTRACT}
\addcontentsline{toc}{section}{Abstract} This module investigates the
placement of emergency and service facilities in a network of towns
connected by roads.  Criteria for placement and algorithms for
implementation are also discussed.

\newpage
\setcounter{section}{-1}
\section{Introduction}

This module is primarily for the use of high school teachers of
discrete mathematics and their students.  Typical students in this
course will be seniors of average ability who have completed
pre-calculus/trigonometry but who may not have the interest or
requisite skills necessary to take an advanced placement course in
either calculus or statistics.

\sk
In this module, students will use graphs and weighted graphs to
determine which of several sites is the best location for different
types of facilities.  The key ideas are that of the ``center'' and
``median'' of a graph.  These will be found using the distance matrix
which gives the ``distance'' between any two vertices.  Different
techniques for finding ``distances'' are used for the case of graphs,
weighted graphs (with weights on edges), and general networks (with
weights on both vertices and edges).

\sk
Students should be familiar with the concept of using a graph to
model a physical situation and with basic matrix operations.  Teachers
may wish to extend this model by discussing Dijkstra's algorithm or
some other algorithm for computing distances in a general network.

\sk
Students should have a TI-82/83 calculator or equivalent.
Familiarity with the matrix menus and matrix operations would be
helpful.

\sk
\section{The Problem}

Several towns have pooled their resources and decided to build
facilities to service the area.  Where should these facilities be
located so that they will be as convenient as possible for everyone?

\sk
To help in the analysis of this problem we will use a graph.
Informally, a {\em graph} consists of points (called {\em vertices})
and line segments joining certain of these points (called {\em
edges}).  A picture of the graph resembles a map of the region with
the vertices representing the towns and the edges representing the
roads that join the various towns.

\begin{center}
\resizebox*{!}{2.5in}{\includegraphics{g1.eps}}

Figure 1
\end{center}

Figure 1 shows such a graph (called $G$) representing nine towns,
labeled $a,b,c,d,e,f,g,h,i$, and various roads connecting them.  Note
that the points where the edge joining vertices $b$ and $e$ crosses
other edges are not labeled as vertices, and are not considered as
possible locations for the facilities.  To assist in the analysis of
the problem we would also want to know the distance along these roads
from town to town (or the time it takes to get from town to town along
these roads).  This could be represented by a weight.  A {\em weight}
on an edge is a non-negative number placed on the edge to represent
distance, time, cost, or perhaps some other attribute.  For additional
realism we could also place weights on the vertices.  These
non-negative numbers placed on the vertices could represent the
populations of the towns or perhaps the demand for services in the
towns.

\sk
Although a graph with weights on both vertices and edges (called a
{\em general network}) is the most realistic model, analysis of this
model might be obscured by all the weights.  So in order to understand
the basic terms and get a feel for what is happening we will make a
simplifying assumption and start by using an unweighted graph.  You
can imagine that all the towns have roughly the same population (give
each vertex a weight of $1$) and that all roads connecting towns are
roughly the same length (give each edge a weight of $1$).

\sk
\section{Distance in Graphs}

Let's consider the various types of facilities that might be placed in
this region.  One type is an emergency facility (such as a fire
station, ambulance service, police station, hospital, etc.).  A second
type is a service facility (such as a shopping mall, post office, park
or playground, etc.).  Each of these two types of facilities has its
own set of criteria as to what constitutes optimal placement for those
people who use the facilities.  In either case, it is clear that the
distance (or time) from town to town is of great importance.

\sk
When we talk of distance between two points, we refer of course to
the shortest distance as measured in terms of the edges of the graph.
More formally we have the following:


\begin{defn} If $u$ and $v$ are two vertices in a graph, then the {\em distance} from $u$ to $v$, $d(u,v)$,
is the number of edges in a shortest path from $u$ to $v$.
\end{defn}


\begin{examp}
In graph $G$ (Figure 1), $b-d-h$ and $b-e-g-h$ are two paths from $b$
to $h$.  The distance, $d(b,h)$, from $b$ to $h$ is $2$ since there is
a path from $b$ to $h$ that has $2$ edges, but there is no path from
$b$ to $h$ that has $1$ edge.
\end{examp}

%\newpage
\begin{xca}
Given the following graph (assume all edges have weight $1$):

\begin{center}
\resizebox*{!}{2.4in}{\includegraphics{g1.5.eps}}
\end{center}

find:   a)  $d(c,b)$\quad b)  $d(b,c)$\quad c)  $d(c,c)$

\qquad\ d)  $d(b,a)$\quad e)  $d(c,a)$\quad f)  $d(c,b) + d(b,a).$

Food for thought: what is $d(b,g)$?
\end{xca}

In a disconnected graph, the distance between two vertices is not
always defined, as in the graph of Exercise 1.  In the graphs that we
will be looking at, it is possible to get from any site to any other
site, so henceforth all graphs will be connected.  (A graph is {\em
connected} if one can go from any vertex to any other vertex by moving
along edges.)  Examining your answers to Exercise 1 should remind you
of the basic properties of distance in the ``normal'' sense.  Any
function proposed as a distance function should have these properties
where $u$ and $v$ are ``points'':

\begin{quotation}
i)  $d(u,v) \geq 0$ with equality if and only if $u = v$

ii)  $d(u,v) = d(v,u)$   (the symmetric property)

iii) $d(u,v) + d(v,w) \geq d(u,w)$   (the triangle inequality).
\end{quotation}

It should be easy to see that our definition of distance between
vertices satisfies all three of these properties.

\sk
\section{Calculating Distances in Graphs}

Referring to graph $G$ (Figure 1) we see nine vertices.  The distances
can be recorded for convenience in a $9\times 9$ matrix, $D(G)$, the
distance matrix in which the entry in the $i^{\rm th}$ row and $j^{\rm
th}$ column is the distance from vertex $i$ to vertex $j$.  By
properties i) and ii) we see that this is a symmetric matrix with
zeros along the principal diagonal.

\sk
We now describe three different techniques for filling in the entries in this matrix.

\sk
\noindent{\bf Method 1}

One approach is simple brute force.  By trial and error, we can
calculate the first row of this matrix (that is, the distances from
vertex a to all other vertices):
$$0\quad 1\quad 1\quad 2\quad 2\quad 3\quad 2\quad 3\quad 4.$$
By property ii), this is also the first column of $D(G)$.

\begin{xca}
By trial and error, find:

a) the distances from vertex $c$ to all other vertices (i.e., the
third row).

b) the distances from all other vertices to vertex $e$ (i.e., the
fifth column).
\end{xca}

If the graph is reasonably small then finding all distances by trial
and error (whether the graph is weighted or not) is a relatively
simple task.  If the graph has many vertices then it becomes a bit
tedious to use this method.  So let's look for another way.

\sk
\noindent{\bf Method 2}

To generate the distances from each vertex to all other vertices we
will construct a ``tree'' of distances.  A tree is a special type of
graph defined using circuits.  A {\em circuit} is a sequence of
distinct edges such that the initial vertex of the first edge is the
same as the terminal vertex of the last edge.  For example, in the
diagram for Exercise 1, $a-d-c-a$ is a circuit of length $3$ while
$a-c-b-e-a$ is a circuit of length $4$.

\begin{defn} A {\em tree} is a connected graph with no circuits. A tree has the nice property that there is a unique
path joining any two of its vertices.
\end{defn}


To construct the tree of distances we will perform a {\em
breadth-first search (BFS)}. Given a starting (root) vertex, a BFS
will list all vertices at a distance of one from the root and then
examine the remaining vertices in turn, listing all that have a
distance of two from the root (unless they already appear in the
tree).  This process continues until all vertices in the original
graph are listed in the tree.

\sk
Refer again to Figure 1.  Starting with $b$ as a root vertex
($d(b,b) = 0$), we list all vertices adjacent to $b$ in a row.  These
vertices ($a, c, d, e$) are at a distance $1$ from $b$.

\begin{center}
\resizebox*{2.6in}{!}{\includegraphics{g2.eps}}

Figure 2
\end{center}

We then go across this row and for each vertex in the row list all
vertices adjacent to it that do not already appear in the ``tree''.
For example, in Figure 1 we have that $a$ is adjacent to both $b$ and
$c$.  However both $b$ and $c$ are already in the tree.  Therefore we
do not list them again.  Also from Figure 1, $c$ is adjacent to $a, b,
d, e,$ and $g$.  Of these, $a, b, d,$ and $e$ are already in the tree
so only $g$ is listed in a second row.  These new vertices added to
the tree are at a distance of $2$ from $b$.  Doing this for the
vertices $a, c, d,$ and $e$ at the first level of the tree gives:

\begin{center}
\resizebox*{2.6in}{!}{\includegraphics{g3.eps}}

Figure 3
\end{center}

There are now $8$ vertices in our tree.  Only vertex $i$ needs to be
placed.  It is adjacent to vertex $h$ and is therefore at a distance
$3$ from vertex $b$ and is listed in a third row or level.  Here is
our complete tree for the distances from $b$ to all other vertices:

\begin{center}
\resizebox*{2.6in}{!}{\includegraphics{g4.eps}}

Figure 4
\end{center}

Notice in Figure 4 that $h$ is adjacent to both $d$ and $g$ but, since
we want the shortest distance, we only list it once.  Therefore we
list it only at level $2$.  Once we complete the diagram we can read
off the second row (and second column) of the matrix $D(G)$ by reading
the numbers corresponding to the vertices in alphabetical order:
\begin{eqnarray*}
a\quad b\quad c\quad d\quad e\quad f\quad g\quad h\quad i\\
1\quad 0\quad 1\quad 1\quad 1\quad 2\quad 2\quad 2\quad 3
\end{eqnarray*}

\begin{xca}
Using a breadth first search, construct trees to find:

a) the distances from vertex $c$ to all other vertices (i.e., the
third row).

b) the distances from all other vertices to vertex $e$ (i.e., the
fifth column).

c)  compare your answers with those you found in Exercise 2.
\end{xca}

We can continue with either method (trial and error or breadth first
search), using the facts that the matrix is symmetric and the
principal diagonal is all zeros, and fill in the remaining entries:
$$D(G)=\left[\begin{array}{ccccccccc}
0&1&1&2&2&3&2&3&4\\
1&0&1&1&1&2&2&2&3\\
1&1&0&1&1&2&1&2&3\\
2&1&1&0&2&1&1&1&2\\
2&1&1&2&0&3&1&2&3\\
3&2&2&1&3&0&2&2&3\\
2&2&1&1&1&2&0&1&2\\
3&2&2&1&2&2&1&0&1\\
4&3&3&2&3&3&2&1&0
\end{array}\right].$$

\sk
\noindent{\bf Method 3}

A third approach for obtaining the $D(G)$ matrix uses certain
interesting properties of the adjacency matrix $A(G)$ that records
which vertices are adjacent to each other in the graph $G$.

\begin{defn}
If $G$ is a graph on $n$ vertices then the {\em adjacency matrix}
$A(G)$ is an $n\times n$ matrix with $a= 1$ if
vertex $i$ is adjacent to vertex $j$ and $a= 0$ otherwise.
\end{defn}

Again referring to Figure 1, the adjacency matrix is
$$A(G)=\left[\begin{array}{ccccccccc}
0&1&1&0&0&0&0&0&0\\
1&0&1&1&1&0&0&0&0\\
1&1&0&1&1&0&1&0&0\\
0&1&1&0&0&1&1&1&0\\
0&1&1&0&0&0&1&0&0\\
0&0&0&1&0&0&0&0&0\\
0&0&1&1&1&0&0&1&0\\
0&0&0&1&0&0&1&0&1\\
0&0&0&0&0&0&0&1&0
\end{array}\right].$$

The $i,j^{\rm th}$ entry in $A^n$, the $n^{\rm th}$ power of the
adjacency matrix, yields the number of paths of length $n$ from vertex
$i$ to vertex $j$ (including those that involve repeated edges).  To
understand this property, let's consider a much simpler example.  Look
at $K_3$, a complete graph on three vertices.  A {\em complete graph}
is a graph where any two vertices are adjacent.  Also, look at its
adjacency matrix $A$, and its square and cube, $A^2,$ and $A^3$.
\begin{center}
\resizebox*{1.8in}{!}{\includegraphics{k3.eps}}
\end{center}
$$A=\begin{array}{cc}
&\begin{array}{ccc}a&b&c\end{array}\\
\begin{array}{c}a\\b\\c\end{array}&
\left[\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\end{array}\right]
\end{array}\quad
A^2=\left[\begin{array}{ccc}2&1&1\\1&2&1\\1&1&2\end{array}\right]
\quad
A^3=\left[\begin{array}{ccc}2&3&3\\3&2&3\\3&3&2\end{array}\right].
$$

In the matrix $A^2$, notice the $1$ in the $2,3$ entry, that is, the
row for vertex $b$ and the column for vertex $c$.  This $1$ is the
result of a dot product between the $b$ row and $c$ column of $A$.
That is, it is
$$[1\quad 0 \quad 1]\cdot\left[\begin{array}{c}1\\1\\0\end{array}\right]
=1\cdot1+0\cdot1+1\cdot0=1.$$

\sk
In the term $1\cdot1$ of the expression $1\cdot1+0\cdot1+1\cdot0$,
the first $1$ comes from the fact that $b$ is connected to $a$.  The
second $1$ comes from the fact that $a$ is connected to $c$.  Thus the
product counts the fact that $b$ is connected to $c$ (through $a$) by
a path (where we are allowed to repeat edges) of length $2$.

\sk
In a similar way, look at the matrix $A^3$.  Notice the $3$ in the
$b$ row, $c$ column.  This $3$ is the result of the dot product of the
$b$ row in matrix $A$ times the $c$ column in matrix $A$.  That is
$$[1\quad 0 \quad 1]\cdot\left[\begin{array}{c}1\\1\\2\end{array}\right]
=1\cdot1+0\cdot1+1\cdot2=3.$$

\sk
Reasoning as above, we see that there are $3$ paths of length $3$
from $b$ to $c$ --- one path consists of the edge from $b$ to $a$
followed by the unique path from $a$ to $c$ of length $2$; the other
two paths consist of the edge from $b$ to $c$ followed by the two
paths from $c$ to $c$ of length $2$.  We can extend this argument to
show that the $ij$-entry of matrix $A^n$ counts the number of paths of
length $n$ from vertex $i$ to vertex $j$.
\begin{center}
\includegraphics{er4.eps}
\end{center}

\begin{xca}
Using the graph pictured above:

a) construct the adjacency matrix $A(G)$.

b) how many paths of length $4$ are there from vertex $a$ to vertex $a$?

c) how many paths of either length $2$ or length $3$ are there from
$a$ to $c$?
\end{xca}

\sk
There is another way to think about the construction of $D(G)$.
Let $D(G) = [d_{ij}]$ be the distance matrix and $A(G) = [a_{ij}]$ be
the adjacency matrix.  The distance between vertex $i$ and itself is
$0$.  For each distinct $i$ and $j$, to determine the distance
$d_{ij}$ from vertex $i$ to vertex $j$, look at the $ij$'th entry in
each of the matrices $A, A^2, A^3, A^4, \dots$ until you find one
which is non-zero.  If that happens first in $A^k$, then $d_{ij}= k$
since there is a path from vertex $i$ to vertex $j$ which has length
$k$, but there is no shorter path from vertex $i$ to vertex $j$.

\sk 
In a connected graph with $n$ vertices, this procedure for
obtaining $D(G)$ must terminate when the exponent in $A^k$ reaches $n
- 1$ since if there is a path from $i$ to $j$, then there is one that
doesn't repeat vertices, and paths which do not repeat any vertices
all have length at most $n - 1$.

\sk
This procedure for describing $D(G)$ can be realized by using the
following algorithm to develop successive approximations of $D(G)$.

\begin{quote}
\begin{enumerate}
\item Start with $d_{ij}= 0$ for all $i,j$.

\item For $i\neq j$, if $a_{ij}= 1$ in $A(G)$, let $d_{ij}= 1$ in $D(G)$.

\item For $i\neq j$, if $a_{ij}= 0$ in $A^k(G)$ for $k = 1,2,\dots,
m-1$ and $a_{ij}> 0$ in $A^m(G)$ then $d_{ij}= m$ in $D(G)$.
\end{enumerate}
\end{quote}

{\bf Exercise 4} (continued)

d) using the graph on the previous page, find $D(G)$ using powers of
the adjacency matrix.

\sk
\section{Placement of Emergency Facilities}

Now that we are able to compute the distance between vertices, we can
return to our problem and consider criteria for the placement of the
facilities.

\sk
Let's consider the emergency facility (for example, an ambulance
service).  It is reasonable to assume that an ambulance is required
(for medical reasons) to be able to reach any potential victim or
accident scene within a certain maximum amount of time (or distance);
it it takes longer than that to arrive, patients who could have been
saved might instead die.  Any town closer to the proposed site than
this maximum would be properly served by an ambulance at the proposed
site.  In order to ensure that every town is properly served by an
ambulance at the proposed site, we would have to calculate the
distance from the proposed site of the emergency facility to the town
that is farthest away.  If this distance (or time) is less than the
maximum required for medical reasons then the proposed site is now a
possible site.  If this distance is greater than the maximum then we
need to search for a better site.  For some graphs there may not be
any site which will do this.  In other words, we need to ensure that
the worst possible case is less than some predetermined bound.

\sk
What we will do instead is find those sites for which the worst
possible case is as good as possible.  To do this, we will use our
distance matrix, $D(G)$, in order to find a ``centrally located''
vertex.

\sk
For each vertex we find the ``worst case'' by looking in each row and determining which vertex is furthest away.
For each vertex this number is called its eccentricity.  Formally, we have

\begin{defn}
The {\em eccentricity} $e(v)$ of vertex $v$ is
$$e(v) = \max \{d(v,u) : u \in V\}.$$
\end{defn}

Looking at the first row of $D(G)$ we see that the vertex which is
farthest from $a$ is $i$.  Since the distance from $a$ to $i$ is $4$
then by our definition $e(a) = 4$.  Now look at the fourth row (vertex
$d$).  The maximum distance in that row is $2$ (from $d$ to either $a,
e,$ or $i$).  Therefore, $e(d) = 2$.

\begin{xca}
Use the distance matrix $D(G)$ to find the eccentricity of the other
seven vertices in Figure 1.
\end{xca}

To minimize these worst cases we take those vertices with minimum
eccentricity. This collection of vertices is called the set of central
vertices of the graph.

\begin{defn}
The {\em central vertices} $CV(G)$ of a connected graph $G$ is
$$CV(G) = \{v \in V : e(v) \mbox{ is minimum}\}.$$
\end{defn}

For our graph, $CV(G) = \{d,g\}$, since both $e(d)$ and $e(g)$ are
equal to $2$ and $e(x) > 2$ for all other vertices.  That is, an
emergency facility like a hospital or fire station should be located
at either vertex $d$ or $g$ since the distance from any other vertex
to either $d$ or $g$ is at most $2$.

\sk In the general situation, we could locate the emergency facility
at any central vertex since such a vertex has the smallest possible
eccentricity.

\sk We need however compare the outcome of this analysis with the
maximum bound $M$ mandated by medical considerations.  If the
eccentricity of the central vertices is less than or equal to $M$,
then locating the emergency facility at any central vertex would meet
the requirements.  Indeed any vertex whose eccentricity is less than
or equal to $M$ would be a reasonable site, even if it is not
central. Many factors may be used to determine which of several
acceptable sites is best.  On the other hand, if the eccentricity of
the central vertices is greater than $M$, no site is acceptable and
the situation needs to be reevaluated.

\begin{xca}
For the graph pictured on the next page:

a)  Use any method to construct the distance matrix, $D(G)$.

b)  Find the eccentricity of all vertices.

c)  Find the central vertices of the graph.

d)  At which site should an emergency facility be located?

\begin{center}
\includegraphics{er6.eps}
\end{center}
\end{xca}

Our use of the word ``central vertex'' might make you think about how
this definition compares with the usual definition of central vertex
(center is the usual term) of a circle. Imagine all points on or
inside a circle. For any point, $P$, on or inside the circle, draw a
diameter passing through that point (See Figure 5).

\begin{center}
\includegraphics{g5.eps}

Figure 5
\end{center}

Recalling our definition of eccentricity, if a point, $P$, is on the
circle then eccentricity equals the maximum distance between $P$ and
any other point on the circle (i.e. diameter).  If a point, $P$, is
inside the circle then the eccentricity equals the length of the
longer segment along that diameter (why is that the maximum distance
from $P$ to a point on the circle?).  Since, by our definition, the
center consists of those points which minimize the eccentricity, the
one and only point in a circle satisfying that property is the center
of the circle.

\sk In keeping with this idea, let's define two more terms which mimic
similar terms relating to a circle.

\begin{defn}
The {\em diameter} of a connected graph is the maximum distance
between two vertices of the graph; thus it is also the maximum
eccentricity among all vertices.
\end{defn}

For example, in graph $G$ (figure 1), the diameter $= d(a,i) = 4 = e(a) = e(i)$.

\begin{defn}
The {\em radius} of a connected graph is the minimum eccentricity
among all vertices of the graph.  For example, in graph $G$ (Figure
1), the radius $= d(d,g) = 2 = e(d) = e(g)$.
\end{defn}

\begin{xca}
(Note: These problems are difficult and may be omitted without
breaking the continuity of the document.)

1.  Verify that in any graph, diameter = 2 $\cdot$ radius.

2.  Construct an example where the diameter of a graph is less than twice
     the radius.

3.  Verify that a tree has either one central vertex or two central vertices
     which are adjacent.
\end{xca}

\sk
\section{Placement of Service Facilities}

Now consider a service facility such as a post office or shopping
mall.  Although it may be an inconvenience for a person to travel a
long distance to get to a post office or shopping mall, it is not a
matter of life or death.  Although for emergency facilities,
minimizing the maximum distance is a good criterion, a more reasonable
criteria for placement of a shopping mall might be to locate the
facility so that the average distance from the facility to all users
(towns) is minimized.  To calculate the average distance from one town
to all other towns we add up all distances and divide by the number of
remaining vertices.  As an example, refer again to Figure 1 and look
at vertex $a$.  The distance matrix $D(G)$ has all the distances
recorded so we can easily figure out the average distance from vertex
a to all others.  It is
$$\frac{1+1+2+2+3+2+3+4}{8}=  2.25.$$

\sk Since the number of vertices is fixed, minimizing the averages is
equivalent to minimizing the sum of the distances.  This sum is called
the status of a vertex.

\begin{defn}
The {\em status} $s(v)$ of vertex $v$ in graph $G$ is
$$s(v)=\sum_{u\in G}d(v,u).$$ where the sum is taken over all vertices
$u \in G$.
\end{defn}

Note that $d(v,v) = 0$ so we can ignore $d(v,v)$ whenever we calculate
this sum.  Therefore, in graph $G$ (Figure 1), the status of vertex
$a$ is $s(a) = 18$.  Looking at the fifth row (vertex $e$) of the
distance matrix $D(G)$ for graph $G$ we get $s(e) = 2 + 1 + 1 + 2 + 3
+ 1 + 2 + 3 = 15$.

\begin{xca}
Find the status of the remaining seven vertices of Figure 1.
\end{xca}

Although it is reasonably easy to just add up the entries in each row,
there is a simple matrix operation that will produce the status for
each vertex.  Simply multiply $D(G)$ by an $n\times 1$ column matrix
of all $1$'s.  The result will be an $n\times 1$ column matrix
containing the status of each vertex.

\sk Those vertices with minimum status (that is, minimum sum of
distances) will be the vertices whose average distance to all others
will be as small as possible.  These vertices are called the median of
a graph.

\begin{defn} The {\em median} of graph $G$ is
$$M(G) = \{v \in V : s(v) \mbox{ is minimum}\}.$$
\end{defn}

Using your answers to Exercise 8, you see that $s(d) = 11$ gives the
minimum status.  Thus, $M(G) = \{d\}$.  So a service facility like a
shopping mall or post office could be located at vertex $d$.  However,
due to practical considerations --- for example, the price of property
at central locations might be rather high --- the facility might not
actually be located at the ideal site.

\begin{xca}
1.  For the graph pictured in Exercise 6:

a)  Find the status of every vertex.

b)  Find the median of the graph.

c)  At which site should a service facility be located?
\end{xca}

The status of the vertices can also be used to determine which of
several possible sites for an emergency facility is best.  Thus, for
example, in Exercise 6, a number of vertices have eccentricity $3$,
and are all at the center of the graph --- $d, f, g,$ and $j$.  If an
ambulance were located at any one of these vertices, it could get to
any other vertex at a cost of at most $3$ units; in that sense, these
four vertices are equivalent.  However, a secondary criterion for
placement of emergency services should be that if a number of sites
all have minimum worst travel time, then choose the one that has
lowest average travel time.  In other words, if more than one vertex
is in the center, choose one with lowest status or, in case of a tie,
one of the vertices of lowest status.  Thus, if this secondary
criterion is used, the emergency vehicle should be located at vertex d
whose status is $15$.

\sk
You may have noticed that the center and median of our example
contain a common vertex $\{d\}$.  This does not always have to be the
case.

\begin{xca}
1.  Construct a graph with disjoint center and median.  (HINT: Think of a
         tree consisting of a path with lots of branches on one end.)
\end{xca}

\sk
\section{More Realistic Models}

Now let us consider the situation where the edges have (possibly)
different weights rather than all having the same weight of $1$.
Recall that edge weights might represent the actual length of a road
segment, or time or cost to travel it.  As before, the distance
between vertices still means the length of the shortest path between
them, but now the length of a shortest path is the lowest sum of the
``weights'' on its edges; as in the diagram below, the shortest path
between $u$ and $v$ may involve more edges than some longer path.
\begin{center}
\includegraphics{sec6.eps}
\end{center}

The solutions for both types of facilities are found by using the same
formulas as previously discussed.

\sk
For emergency types of facilities, we would find (for each vertex)
the eccentricity $e(v) = \max \{d(v,u) : u \in V\}$ and let the set of
central vertices of the graph $CV(G)$ be the set of vertices with
minimum eccentricity.  For service types of facilities, we would find
(for each vertex) the status
$$s(v)=\sum_{u\in G}d(v,u)$$ and let the median of the graph $M(G)$ be
the set of vertices with minimum status.


\newpage
\begin{xca}


For the graph pictured below:

\begin{center}

\includegraphics{g6b.eps}

\end{center}





1. Find the center of the graph.

2. Find the median of the graph.

3. Determine the optimal placement for an emergency facility.

4. Determine the optimal placement for a service facility.

\end{xca}


You may also have noticed that for both types of location problems we
have assumed (perhaps unrealistically) that the facility in question
was to be built in a town (that is, at a vertex).  This may not
necessarily be the case.  We can allow for the possibility that the
facility should be built between two sites by simply adding a vertex
between those sites, and reevaluating the graph with the extra vertex.
Suppose that in the graph for Exercise 6 (where each edge has weight
1) there is a location on the road from $d$ to $g$ (called $k$) that
is proposed as a possible site for a facility.  This new site can be
represented by adding a new vertex $k$ to the graph of Exercise 6 and
replacing the edge joining $d$ and $g$ by two edges, one joining $d$
and $k$, and the other joining $k$ and $g$; assuming that $k$ is
halfway between $d$ and $g$, each of these edges is assigned the
weight of $1/2$.  The resulting problem, whose graph is below, is used
in Exercise 12.
\begin{center}
\includegraphics{er11.eps}
\end{center}

\begin{xca}
1.  Add vertex $k$ on the road between $d$ and $g$ in the graph for
    Exercise 6:

a)  Find the new distance matrix $D(G)$.

b)  Find the center of this graph.

c)  Find the median of this graph.

d)  How does the addition of the new vertex $k$ along a pre-existing road
    affect the center and median of the graph, and how does this affect
    the potential location of emergency and service facilities.

2.  (Note: This problem is difficult and may be omitted without
     breaking the continuity of the document.)  Prove that if half or
     more of the users in a graph are located at the same vertex, then
     that vertex is a location with minimum sum of distances (and thus
     the unique median).
\end{xca}

An even more realistic model involves weights on both the edges and
vertices.  Recall that vertex weights might represent the population
at the town or the demand for services.  Such a graph is called a {\em
general network}.  As an example, consider the following general
network:
\begin{center}
\includegraphics{g6.eps}

Figure 6
\end{center}

The solutions for both types of facilities will again be similar to
those discussed in sections 4 and 5.  The central vertices will again
be those vertices with minimum eccentricity and the median will again
be the set of vertices with minimum status.

\sk Before we give the definitions of center and median in a general
network and solve the Facility Location Problem for Figure 6, consider
the following example (see Figure 7).
\begin{center}
\includegraphics{g7.eps}

Figure 7
\end{center}

Where should we place an emergency facility?  If, as before, we want
to ensure that the worst case scenario is as good as possible, then we
would want to place the facility at $b$, since the emergency vehicle
would be able to get from $b$ to either $a$ or $c$ in $10$ minutes ---
in other words, since $e(b) = 10$ and $e(a) = e(c) = 15$, $b$ has the
minimum eccentricity and is therefore the unique central vertex of the
graph.

\sk On the other hand, one could argue that the emergency facility
should be at $c$ since a very high percentage of emergency calls will
be from c.  This amounts to saying that an emergency facility should
be treated just like a service facility.

\sk Now suppose (as discussed in section 5) that a service facility
must be placed so that the average distance to the facility is
minimized.  We easily calculate the averages as follows:

\sk
If the facility is at vertex $a$ then the average is
$$\frac{1\cdot 0+1\cdot 5+100\cdot 15}{102}= \frac{1505}{102}=14.7549.$$

\sk
If the facility is at vertex $b$ then the average is
$$\frac{1\cdot 5+1\cdot 0+100\cdot 10}{102}= \frac{1005}{102}=9.8529.$$

\sk
If the facility is at vertex $c$ then the average is
$$\frac{1\cdot 15+1\cdot 10+100\cdot 0}{102}= \frac{25}{102}=0.2451.$$

\sk Since the status of vertex $c$, $s(c)$, is $25$, this vertex has
the lowest average distance and thus the median of the graph is $M(G)
= \{c\}$.

\sk How could the question be resolved?  One way is if there is some
recommended maximum time from an emergency facility.  For example, if
the guideline was that the emergency vehicle should be within $20$
minutes from every site, then it would be fine to locate the emergency
vehicle at $c$.  If, on the other hand, the guideline was that the
emergency vehicle should be within $10$ minutes from every site, then,
in order to ensure that every site could be reached within the
recommended maximum time, the emergency vehicle would have to be
located at $b$.  (Note, however, that the benefits of getting to $100$
potential customers much more quickly than this recommended maximum
time --- if the vehicle were at $c$ --- might outweigh the benefits of
getting to $102$ customers within the recommended maximum time --- if
the vehicle were at $b$.)  And if the guideline was that the emergency
vehicle should be within $12$ minutes from every site, then it would
probably be located somewhere between $b$ and $c$.

\sk Summarizing for a general network, we should continue to define
the eccentricity of a vertex as before.

\begin{defn} The eccentricity $e(v)$ of vertex $v$ is
$$e(v) = \max \{d(v,u) : u \in V\}.$$
\end{defn}

However, when using a general network, we should now use the weights
on the vertices to determine the status.

\begin{defn} The status $s(v)$ of vertex $v$ in general network $G$ is
$$s(v)=\sum_{u\in G}w(u)\cdot d(v,u).$$
where as before, the sum is taken over all vertices $u \in G$.
\end{defn}
Note that we multiply $d(v,u)$ by the vertex weight at the arrival
vertex $u$.  Why is that?  Suppose we are dealing with a service
facility (like a shopping mall) located at vertex $v$.  Then the
people living at $u$ must travel to $v$ to avail themselves of the
service.  Thus it is the demand for services at vertex $u$ which is
most important.

\sk In making a decision about the placement of a service facility, we
focus on the vertices of minimum status, that is, the median of the
graph.  On the other hand, in making a decision about the placement of
an emergency facility, we may need to consider both the central
vertices and the median vertices, as discussed above.

\sk
In order to determine both the status and eccentricity of the
vertices of a graph, we need to be able to calculate the distance
between any two vertices of a weighted graph --- that is, we need to
find the matrix for distance in graphs with weighted edges.  If the
general network is small enough then simple brute force will do.  The
adjacency matrix approach that we used with unweighted graphs will not
work with weighted graphs.

\sk
Of the three methods used for unweighted graphs, this leaves only
the breadth-first search tree.  If you use exactly the same algorithm,
it doesn't quite work.  Just because a vertex appears at (say) level
two of the tree, that doesn't preclude the same vertex appearing again
at the next (or even lower) level and at a shorter distance to the
root of the tree.  The algorithm can be slightly modified however so
that it will work properly.  When this is done the algorithm turns out
to be just a reworking of Dijkstra's algorithm which is a very well
known procedure for finding the shortest path between two vertices in
a weighted graph.

\sk There are other procedures for calculating distances in weighted
graphs (see the bibliography).  However Dijkstra's algorithm is what
is usually used.

\sk
Once we have this weighted distance matrix we take it and multiply by the vertex weight matrix.  This matrix has
vertex weights on the main diagonal and has zeros in all other positions.  For the graph in Figure 6 the
computations are as follows:
$$\left[\begin{array}{cccccc}
0&4&8&6&6&5\\
4&0&5&3&2&2\\
8&5&0&2&3&6\\
6&3&2&0&1&4\\
6&2&3&1&0&3\\
5&2&6&4&3&0
\end{array}\right]\cdot
\left[\begin{array}{cccccc}
3&0&0&0&0&0\\
0&2&0&0&0&0\\
0&0&3&0&0&0\\
0&0&0&1&0&0\\
0&0&0&0&4&0\\
0&0&0&0&0&1
\end{array}\right]=
\left[\begin{array}{cccccc}
0&8&24&6&24&5\\
12&0&15&3&8&2\\
24&10&0&2&12&6\\
18&6&6&0&4&4\\
18&4&9&1&0&3\\
15&4&18&4&12&0
\end{array}\right].$$

We now read off the eccentricities (the maximum in each row of the
unweighted distance matrix):
$$e(a) = 8\quad e(b) = 5\quad e(c) = 8\quad e(d) = 6\quad e(e) =
6\quad e(f) = 6$$ and the statuses (the sum of each row of the
weighted distance matrix):
$$s(a) = 67\quad s(b) = 40\quad s(c) = 54\quad s(d) = 38\quad s(e) =
35\quad s(f) = 53.$$

\sk
The center of the graph is $\{b\}$ and the median of the graph is
$\{e\}$.  Thus (under our assumptions) an emergency facility should be
located at vertex $b$ while a service facility should be located at
vertex $e$.

\begin{xca}
For the network pictured below:

a)  Find the weighted distance matrix.

b)  Find the eccentricity of every vertex.

c)  Find the status of every vertex.

d)  Find the center and median of the network.

e)  Where would you place a fire station?  a shopping mall?
\begin{center}
\includegraphics{er12.eps}
\end{center}
\end{xca}


\section*{Solutions to Exercises}

\noindent{\bf Exercise 1:}

a)  $d(c,b) = 1$\qquad  b)  $d(b,c) = 1$\qquad  c)  $d(c,c) = 0$

d)  $d(b,a) = 2$\qquad  e)  $d(c,a) = 1$\qquad  f)  $d(c,b) + d(b,a) = 3$

Food for thought: $d(b,g)$ is not defined since there is no path from
$b$ to $g$.

\sk
\noindent{\bf Exercise 2:}

a)  The third row is    $1\  1\  0\  1\  1\  2\  1\  2\  3$

b)  The fifth column is
\[
\begin{array}{c}2\\1\\1\\2\\0\\3\\1\\2\\3\end{array}
\]

\sk
\noindent{\bf Exercise 3:}
\begin{center}
\includegraphics{s1.eps}
\end{center}

\sk
\noindent{\bf Exercise 4:}

a) $A(G)=\left[\begin{array}{cccc}
0&1&1&1\\
1&0&1&1\\
1&1&0&0\\
1&1&0&0
\end{array}\right]$\qquad
b)  The entry in the $a$ row, $a$ column of $A^4$ is $15$.

c) The entries in the $a$ row and $c$ column of $A^2$ and $A^3$ are
$1$ and $5$.  Therefore, $1 + 5 = 6$.

\sk
\noindent{\bf Exercise 4 (continued):}

d)  $D(G)=\left[\begin{array}{cccc}
0&1&1&1\\
1&0&1&1\\
1&1&0&2\\
1&1&2&0
\end{array}\right]$

\sk
\noindent{\bf Exercise 5:}

$e(a) = 4$\qquad $e(b) = 3$\qquad $e(c) = 3$\qquad $e(d) = 2$\qquad
$e(e) = 3$

$e(f) = 3$\qquad $e(g) = 2$\qquad $e(h) = 3$\qquad $e(i) = 4$

\sk
\noindent{\bf Exercise 6:}

a) $D(G)=\left[\begin{array}{cccccccccc}
0&1&2&1&1&2&2&4&3&3\\
1&0&1&2&2&3&3&4&3&2\\
2&1&0&1&2&3&2&3&2&1\\
1&2&1&0&1&2&1&3&2&2\\
1&2&2&1&0&1&2&4&3&3\\
2&3&3&2&1&0&1&3&2&3\\
2&3&2&1&2&1&0&2&1&2\\
4&4&3&3&4&3&2&0&1&2\\
3&3&2&2&3&2&1&1&0&1\\
3&2&1&2&3&3&2&2&1&0
\end{array}\right]$

b) $e(a) = 4$\qquad $e(b) = 4$\qquad $e(c) = 3$\qquad $e(d) = 3$\qquad
$e(e) = 4$

\hspace{0.3cm} $e(f) = 3$\qquad $e(g) = 3$\qquad $e(h) = 4$\qquad
$e(i) = 3$\qquad $e(j) = 3$

c)  center is $\{c,d,f,g,i,j\}$

d) An emergency facility should be located at any vertex in the center
$\{c,d,f,g,i,j\}$.

\sk
\noindent{\bf Exercise 7:}

\noindent NOTE: As stated in the module, these proofs may be omitted
without loss of continuity of the document if the instructor feels
that the students are not quite ready to attempt them.
\begin{enumerate}
\item[1.] {\bf Prove:} In any graph, the diameter is less than or
equal to twice the radius.

{\it Proof:} Let $G$ be a connected graph.  Recall from Exercise 1
that if the graph is not connected then distances might not be
defined.

Let $v$ be a vertex having minimum eccentricity.

Let $u$ be a vertex having maximum eccentricity.

Since $u$ has maximum eccentricity, there exists a vertex $w$ such
that $d(u,w)$ is maximum.  That is, diameter $= d(u,w)$.

Now consider $d(u,v)$ and $d(v,w)$.  Each of these must be less than
or equal to the radius since the radius has minimum eccentricity.
Remember that it is the minimum among all vertices and also that
eccentricity is the maximum distance from $v$ to all other vertices.
So we now have
\[
2\cdot{\rm radius} \geq d(u,v) + d(v,w) \geq d(u,w) = {\rm diameter}.
\]
Q.E.D.

\item[2.]One of the simpler graphs with this property is a circuit
graph.  Consider the graph $C_4$.
\begin{center}
\includegraphics{s2.eps}
\end{center}

Constructing a distance matrix easily shows that $e(a) = e(b) = e(c) =
e(d) = 2$.  Thus diameter $=$ radius $= 2$ and clearly diameter $\leq
2\cdot{\rm radius}$.

\item[3.] {\bf Prove:} A tree has either one center or two adjacent
centers.

{\it Proof:} Let $T$ be any tree.  If $T$ is a single vertex ($K_1$)
or two vertices joined by a single edge ($K_2$) then the result is
trivial.

For all other trees we will describe a ``pruning'' procedure.  Clearly
the vertices having maximum eccentricity must be the ``leaves''
(vertices having degree $1$).  Prune all the leaves from the tree.
That is, delete each vertex of degree $1$ and its adjacent edge.  This
now leaves a tree $T_1$ whose center is the same as $T$ since all
eccentricities have decreased by $1$.  Clearly this process must
terminate with either a $K_1$ or $K_2$.  Q.E.D.
\end{enumerate}

\sk
\noindent{\bf Exercise 8:}

$s(b) = 13$\qquad $s(c) = 12$\qquad $s(d) = 11$\qquad $s(f) = 18$

$s(g) = 12$\qquad $s(h) = 14$\qquad $s(i) = 21$

\sk
\noindent{\bf Exercise 9:}

1.

a) $s(a) = 19$\qquad $s(b) = 21$\qquad $s(c) = 17$\qquad $s(d) =
15$\qquad $s(e) = 19$

\hspace{0.3cm} $s(f) = 20$\qquad $s(g) = 16$\qquad $s(h) = 26$\qquad
$s(i) = 18$\qquad $s(j) = 19$

b) $M(G) = {d}$

c) A service facility should be located at vertex $d$.

\sk
\noindent{\bf Exercise 10:}

1. Here is one possible example. (There are others)
\begin{center}
\includegraphics{s3.eps}
\end{center}

\sk
\noindent{\bf Exercise 11:}
\begin{enumerate}
\item[1.]

a) $D(G)=
\left[\begin{array}{ccccccccccc}
0&1&2&1&1&2&3&5&4&3&2\\
1&0&1&2&2&3&4&4&3&2&3\\
2&1&0&1&2&3&3&3&2&1&2\\
1&2&1&0&1&2&2&4&3&2&1\\
1&2&2&1&0&1&2&4&3&3&2\\
2&3&3&2&1&0&1&3&2&3&2\\
3&4&3&2&2&1&0&2&1&2&1\\
5&4&3&4&4&3&2&0&1&2&3\\
4&3&2&3&3&2&1&1&0&1&2\\
3&2&1&2&3&3&2&2&1&0&3\\
2&3&2&1&2&2&1&3&2&3&0
\end{array}\right]$

b) $C(G) = \{c, f, j, k\}$

c) $M(G) = \{d\}$

d) The median remains the same.  The central vertices change with $k$
joining the center and $d$, $g$, and $i$ leaving.

NOTE: As stated in the module, this proof may be omitted without loss
of continuity of the document if the instructor feels that the
students are not quite ready to attempt it.

\item[2.] {\bf Prove:} If half or more of the users in a graph are
located at the same vertex, then that vertex is a location with
minimum sum of distances (and thus the unique median).

{\it Proof:} Let $u$ be the vertex with half or more of the users.
Designate these users as $A_1, A_2, \dots, A_m$.  Let the other users
located at other vertices be $O_1, O_2, \dots, O_n$.  Notice that
since half or more of the users are at vertex $u$ we then have $m \geq
n$.  Pair up users from $u$ with the other users $(A_1,O_1),
(A_2,O_2),\dots, (A_n,O_n)$.  Notice that users $A_{n+1}$ to $A_m$ are
not paired with anyone.  Let $d(A_i,O_i)$ be the distance from the
vertex where $A_i$ is to the vertex where $O_i$ is.  This distance
function obeys the usual reflexive, symmetric, and transitive
properties.  Consider the following sum
\[
S = d(A_1,O_1) + d(A_2,O_2) +\dots+ d(A_n,O_n).
\]
If the facility is placed at $u$ then $S$ represents the status of
vertex $u$.  Suppose we place the facility at another vertex, say
vertex $i$.  Then in the above sum we would replace $d(A_i,O_i)$ with
$d(O_i,A_i)$ because $A_i$ must now travel to where $O_i$ is.  For
$k\neq i$, we would replace $d(A_k,O_k)$ with $d(A_k,O_i) +
d(O_i,O_k)$ since now both $A_k$ and $O_k$ must travel to where $O_i$
is.  Thus by the triangle inequality, the value of $S$ would increase.
In addition, all the users $A_{n+1}$ to $A_m$ would have to now travel
some distance to $O_i$.  Therefore, $u$ is the vertex with minimum sum
of distances and is thus the median.  Q.E.D.
\end{enumerate}

\sk
\noindent{\bf Exercise 12:}

a) $D(G)=
\left[\begin{array}{ccccccc}
0&3&4&4&5&7&9\\
3&0&3&1&2&4&6\\
4&3&0&2&3&5&7\\
4&1&2&0&1&3&5\\
5&2&3&1&0&2&4\\
7&4&5&3&2&0&2\\
9&6&7&5&4&2&0
\end{array}\right]
$

b) We now multiply by the weights on the vertices to obtain our final
matrix
\[
\left[\begin{array}{ccccccc}
0&3&4&4&5&7&9\\
3&0&3&1&2&4&6\\
4&3&0&2&3&5&7\\
4&1&2&0&1&3&5\\
5&2&3&1&0&2&4\\
7&4&5&3&2&0&2\\
9&6&7&5&4&2&0
\end{array}\right]
\left[\begin{array}{ccccccc}
3&0&0&0&0&0&0\\
0&2&0&0&0&0&0\\
0&0&1&0&0&0&0\\
0&0&0&3&0&0&0\\
0&0&0&0&5&0&0\\
0&0&0&0&0&1&0\\
0&0&0&0&0&0&4
\end{array}\right]
=\left[\begin{array}{ccccccc}
0&6&4&12&25&7&36\\
9&0&3&3&10&4&24\\
12&6&0&6&15&5&28\\
12&2&2&0&5&3&20\\
15&4&3&3&0&2&16\\
21&8&5&9&10&0&8\\
27&12&7&15&20&2&0
\end{array}\right]
\]

\hspace{0.3cm} $e(a) = 36$\qquad $e(b) = 24$\qquad $e(c) = 28$\qquad
$e(d) = 20$\qquad $e(e) = 16$

\hspace{0.3cm} $e(f) = 21$\qquad $e(g) = 27$

c) $s(a) = 90$\qquad $s(b) = 53$\qquad $s(c) = 72$\qquad $s(d) =
44$\qquad $s(e) = 43$

\hspace{0.3cm} $s(f) = 61$\qquad $s(g) = 83$

d) $C(G) = \{e\}$ and $M(G) = \{e\}$

e) Both service and emergency facilities should be located at vertex $e$.

\newpage
\sk
\noindent
NOTE: Most of the material in this paper is adapted from the Buckley
article [1] which is probably the easiest for a student to read.

\sk
\begin{thebibliography}{A}
\addcontentsline{toc}{section}{References}

\bibitem {1} Buckley, F., Facility Location Problems, {\em The College
Mathematics Journal}, 18 (1987) 24-32.
\bibitem {2} Chartrand, G. and Lesniak, L., {\em Graphs and Digraphs},
2nd ed., Wadsworth and Brooks/Cole, (1986) 29-30, 31-34.
\bibitem {3} Christofides, N., {\em Graph Theory, An Algorithmic
Approach}, Academic Press, (1975) 79-80, 106, 108.
\bibitem {4} Gondran, M. and Minoux, M., {\em Graphs and Algorithms},
Translated by Steven Vajda, John Wiley \& Sons, (1984) 57-59
\bibitem {5} Harary, F. and Buckley, F., {\em Distance in Graphs},
Addison-Wesley, (1990), 31-50.
\end{thebibliography}
\end{document}
