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 problems we have also with the navy where a small number of ships have to protect as many regions as possible and again the placement of the ships is important.
A region can be protected if a legion in one step can be moved into that region. For example France is protected because a legion can be moved from Rome to France. But Britain requires four moves: 1) from Rome to France , 2) from Constantinople to Rome, 3) from Rome to France and 4) from France to Britain. The four moves are necessary because two legions are required in a region for a move from this region so that at least one legion remains.
Some interesting question: Minimum number of legions to secure the entire Empire and what is the optimal distribution of the legions?
A legion-region table showing the distribution of power in the Empire. A simplification of Constantine's solution. He left Britain without protection, a guess that with this solution the Empire was better protected by an attack simultaneously in 2 regions.
One better solution
Stephen Benecke, Higher Order Domination of Graphs, Thesis, Department of Applied Mathematics of the University of Stellenbosch, South Africa, December 2004