The Roman Empire divided in eight main regions: (B) Britain, (F)
France, (S) Spain, (R) Rome, (C) Constantinople, (M) Minor Asia,
(E) Egypt, A (North Africa). The Empire is approximated by a
Graph. (Here possible connections between E and M and between A
and B are not considered for simplification) Iam Stewart in
Scientific American 2000 described the problem of the
distribution of the legions in the Roman Empire. For
simplification we assume that four legions are available
(Constantine the Great (274-337 AD) actually had 25 legions that
he divided in 4 groups, each group of around 6 legions called a
&bdquofield army“) and that at least one legion is required to
protect a region. Unfortunately there are more regions that
legions and the problem is how to distribute the legions so that
there is a legion in a region that is attacked or at least there
is one close enough and can move in this regions (location
science problem). The move should be such that it does not leave
another region unprotected. Similar pro