Set Covering Deployment

Author

Eric W. Weisstein
September 18, 2007

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Optimization/SetCoveringDeployment.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/SetCoveringDeployment.html.

©2007 Wolfram Research, Inc. except for portions noted otherwise

Graph

cities =Reverse[CityData[#,"Coordinates"]]&/@{"Istanbul","Alexandria","Paris","London","Rome","Artashat","Madrid","Tunis"};

ShowGraph[g=Graph[List/@Union[Sort/@Join[Partition[{8,5,1,6,2,8,7,4,3,5},2,1],
Partition[{3,7,5,2,1},2,1]]],List/@cities]]

Through[{M,V}[g]]

RecognizeGraph[g]

Map

Module[
{
aspect=.7,
countries=Join@@(CountryData/@{"MiddleEast","Europe","Asia","Africa"}),
cities =Reverse[CityData[#,"Coordinates"]]&/@{"Istanbul","Alexandria","Paris","London","Rome","Artashat","Madrid","Tunis"},
names ={"Byzantium", "Alexandria", "Gaul","Britain","Rome","Asia Minor","Iberia","Tunis"},
red=RGBColor[{213,67,41}/255],
blue=RGBColor[{64,85,174}/255],
yellow=RGBColor[{245,247,228}/255]
},
Graphics[{
yellow,Polygon[First[CountryData[#,"Polygon"]]]&/@countries,
{Thickness[.005],red,Line[cities[[#]]&/@{8,5,1,6,2,8,7,4,3,5}],
Line[cities[[#]]&/@{3,7,5,2,1}]},
{White,EdgeForm[red],Disk[#,.8{1,aspect}]&/@cities},
{Black,Table[Text[names[[n]],cities[[n]]-{3,1},Background->White],{n,1,8}]}},
Frame->True,FrameTicks->False,
PlotRange-> {{-5,45},{32,50}},PlotRangeClipping-> True,
AspectRatio-> aspect,
Background->blue,
ImageSize->{420,240}]
]