3.. Графы и связанные с ними задачи

Объекты, допускающие интерпритацию на языке теории графов, встречаются в математике и ее приложениях повсеместно. Компьютерная геометрия не исключение. При этом в ней графы выступают и как техническое средство (сетка линий на поверхности, триангуляция параметризующей области и т.п.), и как объект изучения (прежде всего, оптимизационные задачи на графах). Мы дадим здесь лишь самые простые определения, отсылая заинтересованных к [Емеличев и др. Лекции по теории графов].

Определение. ГРАФОМ называется пара G=(V,E), где V  – некоторое конечное множество, элементы которого называются ВЕРШИНАМИ, а E – семейство неупорядоченных пар (двухэлементных подмножеств) множества V, называемых РЕБРАМИ.  Если пара вершин v и  w составляет ребро e = v w, то говорят, что эти вершины СМЕЖНЫЕ или СОСЕДНИЕ. Также в этом случае говорят, что ребро e и вершина v ИНЦИДЕНТНЫ. Наконец, ребра, пересекающиеся по вершине, также называют СМЕЖНЫМИ или СОСЕДНИМИ.

Замечание. Графы, которые мы только что определили, часто называют ПРОСТЫМИ. Аналогично определяются ОРИЕНТИРОВАННЫЕ графы (ребра – упорядоченные пары вершин) и МУЛЬТИГРАФЫ (допускаются петли и кратные, т.е. соединяющие одни и те же вершины ребра).

Граф G=(V,E) называется ВЗВЕШЕННЫМ, если на множестве его ребер задана весовая функция ω:E->R , которая, обычно, предполагается неотрицательной.

3.. Красивое изображение графов в пакете Mathematica

Для продуктовной работы с графами часто требуется визуализировать граф наиболее наглядным образом. Особенно эта проблема важна в случае больших графов. В Mathmatica имеется ряд встроенных функций рисования графов на плоскости или в трехмерном пространстве, при котором расположение вершин и форма ребер вычисляется так, чтобы оптимизировать тот или иной "эстетический" функционал.

Приведем примеры основных функций изображения графов.

GraphPlot[{(Subscript[v, i1])->(Subscript[v, j1]),(Subscript[v, i2])->(Subscript[v, j2]),…}] строит изображение мультиграфа, при котором вершина (Subscript[v, ik]) соединяется ребром с вершиной (Subscript[v, jk]).

GraphPlot[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4}]

При наведении курсора мыши на вершины графа возникают номера этих вершин. Заметьте, что пары {1,2} встречаются три раза, что изображено ребром кратности три. Кроме того, имеются петли, заданные двумя парами (4,4) и одной парой (3,3).

Вообще говоря, такое представление естественно для ориентированного графа, хотя приведенное выше изображение игнорировало этот факт. Визуализацию направления ребер можено включить следующей опцией.

GraphPlot[{1 -> 2,1 -> 2, 2 -> 1,3-> 3, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4},DirectedEdges->True]

Вот еще два формата команды GraphPlot: 
GraphPlot[{{(Subscript[v, i1])->(Subscript[v, j1]),(Subscript[lbl, 1])},…}] приписывает ребру (Subscript[v, ik])->(Subscript[v, jk]) метку (Subscript[lbl, k])

GraphPlot[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3,{3 -> 1,"метка"}, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4}]

GraphPlot[m] строит граф по матрице вершинной смежности, в которой на (i,j)-ом месте стоит кратность ребра, идущего из вершины с номером i в вершину с номером j (если ребра нет, то кратность равна нулю). Заметим, что теперь для визуализации петель и кратных ребер нужно специально включать соответствующие опции SelfLoopStyle  и MultiedgeStyle, которые по умолчанию выключены.

GraphPlot[{{0,2,0,0},{1,0,0,0},{1,1,1,0},{1,1,0,2}},DirectedEdges->True,SelfLoopStyle->True,MultiedgeStyle->True]

GraphPlot[{{0,2,0,0},{1,0,0,0},{1,1,1,0},{1,1,0,2}}]

У команды GraphPlot[m] имеется много опций, см. MORE INFORMATION из Help GraphPlot .

Следующая команда GraphPlot3D имеет такой же формат, как и  GraphPlot, однако изображает графы в трехмерном пространстве.

GraphPlot3D[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4}]

GraphPlot3D[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3, 3 -> 1, 3 -> 2, 3 -> 4,4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4}]

А вот пример более симпатичного изображения графа. Здесь EdgeRenderingFunction задает функцию прорисовки ребер (в нашем случае рисуются трубки Tube с осью, заданной набором последовательных точек на ребре, возвращаемым в виде первого параметра #1 этой функции), VertexRenderingFunction  – функцию прорисовки вершин (они изображаются сферами).

GraphPlot3D[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3, 3 -> 1, 3 -> 2, 3 -> 4,4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4},SelfLoopStyle->True,MultiedgeStyle->True,EdgeRenderingFunction->(Tube[#1,0.015]&),VertexRenderingFunction->({ColorData["Atoms"][RandomInteger[{1,117}]],Sphere[#1,.08]}&),PlotStyle->Directive[Specularity[White,20]],Boxed->False]

Функция LayeredGraphPlot относится к так называемому иерархическому рисованию и изображает ориентированный граф, располагая вершины на уровнях так, чтобы доминантные вершины (те, в которые входит как можно меньше стрелочек) оказались наверху, а стрелочки были направлены преимущественно вниз. Ниже приведена программа, демонстрирующая, как меняется вид графа при изменении направления ровно одного ребра.

DynamicModule[{v,vv,edge},
v ={1 -> 2,  3 -> 1, 3 -> 2, 3 -> 4,4 -> 1, 4 -> 2, 4 -> 4};
vv=v;
Manipulate[
If[ls≠"None",edge=List@@ToExpression[ls];vv=v/.Rule@@edge-> Rule@@(RotateLeft[edge])];
Row[{
LayeredGraphPlot[v,VertexLabeling->True,EdgeRenderingFunction->(If[(ls≠"None")&&(#2==edge),{Red,Arrowheads[{{Automatic,0.5}}],Arrow[#1]},{Blue, Arrowheads[{{Automatic,0.5}}],Arrow[#1]}]&),ImageSize->250],
LayeredGraphPlot[vv,VertexLabeling->True,ImageSize->250,EdgeRenderingFunction->(If[(ls≠"None")&&(#2==RotateLeft[edge]),{Red,Arrowheads[{{Automatic,0.5}}],Arrow[#1]},{Blue, Arrowheads[{{Automatic,0.5}}],Arrow[#1]}]&)]
},"    "],{{ls,"None","ребро"},{"None"}~Join~(ToString/@v)}
],UnsavedVariables->{vv,edge}
]

Отметим, что у функции LayeredGraphPlot имется еще один формат, а именно, LayeredGraphPlot[g,pos], позволяющий задавать, с какой стороны распологать доминантные вершины. Возможные значения для pos это  Right, Left, Top и Bottom.

Manipulate[
LayeredGraphPlot[{1 -> 2,1 -> 2,  3 -> 1, 3 -> 2, 3 -> 4,4 -> 1, 4 -> 2, 4 -> 4},pos,VertexLabeling->True],{{pos,"Top","Положение доминантной вершины"},{Top,Bottom,Left,Right}}
]

Еще одной иерархической функцией изображения графов является TreePlot. Не смотря на название, она применима не только к деревьям, но и к графам общего вида (в качестве деревьев у графов берутся остовные деревья их связных компонент, определения см. ниже). Ребра, не являющиеся петлями и кратными ребрами изображаются отрезками, что может приводить к совмещению некоторых ребер (см. пример ниже). По своим форматам эта функция похожа на LayeredGraphPlot, однако она имеет дополнительный формат TreePlot[g,pos,(Subscript[v, k])], в котором (Subscript[v, k]) обозначает вершину, которую нужно выбрать в качестве корня. Кроме того, pos может принимать еще и значение Center.

Manipulate[
TreePlot[{1 -> 2,1 -> 2,  3 -> 1, 3 -> 2, 3 -> 4,4 -> 1, 4 -> 2, 4 -> 4},pos,root,VertexLabeling->True,DirectedEdges->True],{{pos,Top,"Положение доминантной вершины"},{Top,Bottom,Left,Right,Center}},{{root,1,"Доминантная вершина"},{1,2,3,4}}
]

У всех перечисленных выше функций рисования графов имеется полезная для решения геометрических задач опция, а именно, VertexCoordinateRules, позволяющая явно указывать координаты вершин графа. Координаты можно задавать или в виде списка, или явно указывать, какой вершине какие координаты приписать, т.е.i->{(Subscript[x, i]), (Subscript[y, i]) ...}, а также вмето некоторых координат может стоять Automatic.

Manipulate[
graphPlot[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4},VertexCoordinateRules->p,PlotRange->{{-1,2},{-1,2}},AspectRatio->Automatic,DirectedEdges->True],
{{p,{{0,0},{1,0},{0,1},{1,1}}},Locator},{graphPlot,{GraphPlot,LayeredGraphPlot,TreePlot}}]

DynamicModule[{p0,pp,pInit},p0={{0,0},{1,0},{0,1},{1,1}};
pInit=p0[[Drop[Range[4],{1}]]];
Manipulate[pInit=p0[[Drop[Range[4],{automatic}]]];pp=MapIndexed[First[#2]->#1&,Insert[p,{Automatic,Automatic},automatic]];
Quiet@graphPlot[{1 -> 2,1 -> 2, 2 -> 1, 3-> 3, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4, 4 -> 4},VertexCoordinateRules->pp,PlotRange->{{-1,2},{-1,2}},AspectRatio->Automatic,DirectedEdges->True],
{{p,pInit},Locator},{graphPlot,{GraphPlot,LayeredGraphPlot,TreePlot}},{{automatic,1,"Вершина, позиционируемая автоматически"},{1,2,3,4}}],UnsavedVariables->{pp,pInit}
]

3.. ГРАФЫ В ПАКЕТЕ MATHEMATICA

В пакете Mathematica предусмотрено две группы средств для работы с графами. Одна предназначена для создания, хранения и преобразования информации в виде графов. Другая, с которой мы познакомились предыдущем разделе, – для визуализации уже имеющихся графов.

3... Графы: способы задания

Описываемые здесь процедуры являются частью пакета Combinatorica, поэтому следует выполнить команду, загружающую этот пакет.

Needs["Combinatorica`"]

Граф в пакете Combinatorica задается командойGraph[<список ребер>,<список вершин>,<список опций графа в целом>] , где каждое ребро (т.е. элемент списка ребер) имеет вид {{<номер вершины>,<номер вершины>},<опции ребра>}, каждая вершина (т.е. элемент списка вершин) имеет вид {{координаты вершины на плоскости},<опции вершины>}, и, наконец в списке опций стоят общие команды для всех вершин, всех ребер и графа в целом. В пакете Combinatorica  также имеются встроенные функции для визуализации графов, такие как ShowGraph[< граф >] или ShowGraphArray. Обратим внимание на ДВОЙНЫЕ фигурные скобки, что вызвано возможным наличием опций.

ShowGraph[Graph[{{{1,2}},{{2,3},EdgeColor->Red},{{3,1}}},
                            {{{-1,0}},{{1,1},VertexColor->Blue,VertexStyle->Disk[Large]},{{1,0}}}]]

Более сложный пример. В нем положение вершин задано случайно, а количество и соседство можно регулировать. Кроме того, справа тот же граф перерисован с установкой общих опций, регулирующих вид вершин и ребер. Заметим, что внешние опции, если установлены, перекрывают СООТВЕТСТВУЮЩИЕ опции, установленные для конкретных вершин (ребер).

Manipulate[Module[{vv,ee,gg},
If[k>n-1,k=n-1];
If[n≠ Length[vv],vv=Map[{#,VertexNumber->True}&,Table[{Random[],Random[]},{n}]]];
ee=Table[{{i,Mod[i+k,n]+1},If[Mod[i,2]==0,EdgeColor->Red,EdgeColor->Green]},{i,1,n}];
g=Graph[ee,vv];
gg=Graph[ee,vv,{EdgeStyle->edgSt,VertexStyle->vrSt}];
GraphicsRow[{ShowGraph[g],ShowGraph[gg]}]],
{{n,4},2,27,1},{{k,1},0,n-1,1},{{edgSt,{Green,Red},"Вид ребра"},{{Blue}->"Синий",{Dashed}->"Пунктир",{Blue,Dashed}->"Синий-Пунктир"}},{{vrSt,{Disk[Normal]},"Размер вершины"},{{Disk[Normal]}->"Нормальный",{Disk[Small]}->"Мелкий",{Disk[Medium]}->"Средний",{Disk[Large]}->"Крупный"}},
Initialization:> (Needs["Combinatorica`"] )
]

Граф, заданный в пакете Combinatorica, можно визуализировать с помощью GraphPlot  или GraphPlot3D. Картинка будет куда нагляднее, однако часть информации, такая как цвета ребер и пр., при этом теряется.

Dynamic[GraphPlot3D[g]]

Отметим, что описанные способы задания графов громоздки и не всегда удобны. Имеется ряд возможностей конструировать графы из более привычных  наборов данных, служащих для описания графов. Так можно породить неориентированный граф из списка неупорядоченных вершин  FromUnorderedPairs[<список>] и ориентированный граф из списка упорядоченных вершин  FromOrderedPairs[<список>]. Также граф можно породить из матрицы вершинной смежности FromAdjacencyMatrix[m] и из списков вершинной смежности FromAdjacencyLists[l].

listOfUnPairs={{1,2},{1,3},{1,4},{1,5},{1,6},{2,3},{3,4},{4,5},{5,6},{6,2}};
vc={{0,0}}~Join~Map[{Cos[((2π)/5)#],Sin[((2π)/5)#]}&, Range[5]];
g1=FromUnorderedPairs[listOfUnPairs] ;
g11=FromUnorderedPairs[listOfUnPairs,vc] ;
ShowGraphArray[{g1,g11}]

Отметим, что для такого задания графа координаты вершин, вообще говоря, не нужны. Mathematica сама выберет в качестве них по умолчанию равномерный набор точек на окружности. Последнее, впрочем, не всегда хорошо отражает суть дела. Если нам не нравится выбор Mathematica, то имеется возможность выбрать точки самим, для чего используется второй необязательный аргумент.

Как мы уже говорили, другой способ  получения наглядной картинки –  воспользоваться GraphPlot. Использование этой команды, однако, таит в себе некоторые неожиданности. Если, например, включить опции, показывающие направления ребер и их кратность, то мы увидим, что наш НЕОРИЕНТИРОВАННЫЙ ПРОСТОЙ граф воспринимается на самом деле как ориентированный.

GraphicsRow[{GraphPlot[g1],GraphPlot[g1,DirectedEdges->True,MultiedgeStyle->True]}]

Из тех же данных можно породить ориентированный граф командой   FromOrderedPairs[<список>].

g2=FromOrderedPairs[listOfUnPairs] ;
g21=FromOrderedPairs[listOfUnPairs,vc] ;
ShowGraphArray[{g2,g21}]

Теперь и GraphPlot даст нам тот ориентированный граф, который мы задавали на самом деле.

GraphPlot[g2,DirectedEdges->True,MultiedgeStyle->True]

При помощи команды FromAdjacencyMatrix[m]  можно породить как неориентированный граф, так и ориентированный (при этом обязательно выставить опцию Type->Directed, иначе получится неориентированный граф, заданный верхним треугольником матрицы смежности). Кроме того, имеется возможность задать граф с кратными ребрами  (в этом случае элементы матрицы интерпретируются как кратность ребер).

m1=(({{0, 1, 1, 1, 1, 1}, {1, 0, 1, 0, 0, 1}, {1, 1, 0, 1, 0, 0}, {1, 0, 1, 0, 1, 0}, {1, 0, 0, 1, 0, 1}, {1, 1, 0, 0, 1, 0}}));m2=(({{0, 1, 1, 1, 1, 1}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 0}})); m3=(({{0, 3, 1, 4, 1, 1}, {3, 0, 1, 0, 0, 1}, {1, 1, 0, 6, 0, 0}, {4, 0, 6, 0, 15, 0}, {1, 0, 0, 15, 0, 1}, {1, 1, 0, 0, 1, 0}}));
g3=FromAdjacencyMatrix[m1]; g31=FromAdjacencyMatrix[m1,vc]; g32=FromAdjacencyMatrix[m2,vc,Type-> Directed];
g33=FromAdjacencyMatrix[m3 ,vc];
ShowGraphArray[{g3,g31,g32,g33}]

GraphicsRow[GraphPlot[#,DirectedEdges->True,MultiedgeStyle->True]&/@{g3,g32,g33}]

Наконец, можно задать взыешенный граф, т.е. приписать ребрам графа некоторые числа, называемые весами. Установка опции EdgeWeight порождает взвешенный граф, в чем можно убедиться, выведя список ребер командой Edges. Теперь элементы матрицы интерпритируются как веса. Для отсутствующих ребер следует в этом случае ставить ∞ (а не нуль).

m4=(({{∞, 3, 1, 4, 1, 1}, {3, ∞, 1, ∞, ∞, 1}, {1, 1, ∞, 6, ∞, ∞}, {4, ∞, 6, ∞, 15, ∞}, {1, ∞, ∞, 15, ∞, 1}, {1, 1, ∞, ∞, 1, ∞}}));
g34=FromAdjacencyMatrix[m4,vc,EdgeWeight];
el=Edges[g34,EdgeWeight]

Чтобы визуализировать веса ребер взвешенного графа, можно установить значения меток ребер равными соответствующим весам (с помощью команды SetEdgeLabels[<граф>,<список меток>]) и выставить опцию {EdgeLabel -> True} . Обратите внимание: команда SetEdgeLabels не меняет метки исходного графа, а создает новый граф.

g35=SetEdgeLabels[g34, #[[2]] & /@ el];
ShowGraphArray[{g35,g34},{EdgeLabel->True}]

Снова можно воспользоваться GraphPlot, применяя функцию EdgeRenderingFunction для визуализации значений весов ребер. Отметим, что GraphPlot воспринимает графы старого формата так, что каждое ребро учетверяется: две копии ориентированы в одну сторону, а две другие – в другую. Ниже предлагается реализация функции прорисовки ребра, основанная на том, что функция GetEdgeWeights не различает направления ребер.

GraphPlot[g34,EdgeRenderingFunction->({Line[#1],Inset[Style[" "<>ToString@@GetEdgeWeights[g34,{#2}]<>" ",Red,Large],Mean[#1],Automatic,Automatic,#1[[1]]-#1[[2]],Background->White]}&)]

Наконец, для задания графов можно воспользоваться списками смежности и командой FromAdjacencyLists. Отметим, что в этих списках также допускается  указывать веса ребер. Списки смежности устроены так. На i-ом месте списка стоит список номеров вершин, смежных с i-ой вершиной. Если надо указать веса ребер, то в i-ом списке вместо номера j  ставится пара вида { j, ω}, где ω – вес ребра  i j.

(* Обычные списки смежности *)
ll={{2,3,4,5,6},{1,3,6},{1,2,4},{1,3,5},{1,4,6},{1,2,5}};
vc={{0,0}}~Join~Map[{Cos[((2π)/5)#],Sin[((2π)/5)#]}&, Range[5]];
g4=FromAdjacencyLists[ll]; g41= FromAdjacencyLists[ll,vc];
(* Списки смежности с весами *)
lw={{{2,1},{3,3},{4,2},{5,1},{6,2}},{{1,1},{3,2},{6,3}},{{1,3},{2,2},{4,5}},{{1,2},{3,5},{5,1}},{{1,1},{4,1},{6,6}},{{1,2},{2,3},{5,6}}};
g42=FromAdjacencyLists[lw,EdgeWeight];
(* Устанавливаем метки ребер равными их весам *)
g43=SetEdgeLabels[g42, #[[2]] & /@ Edges[g42, EdgeWeight]];
ShowGraphArray[{g4,g41,g43},VertexNumber->True,EdgeLabelColor->Red]

Если граф уже есть, то можно получить из него набор соответствующих (упорядоченных) пар, матрицу смежности, списки смежности с помощью обратных команд ToUnorderedPairs, ToOrderedPairs, ToAdjacencyMatrix и ToAdjacencyLists, соответственно. При этом надо внимательно следить за опциями. Например, отсутствие опции EdgeWeight проиводит к потере информации о весах ребер.

ll={{{2,0.1},{2,π//N},{3,.13}},{{2,(Sqrt[3])//N},{3,Log[2]//N}},{}};
(*ll={{{2,10},{2,π//N},{3,.13}},{{2,(Sqrt[3])//N},{3,Log[2]//N}},{}};*)
gr=FromAdjacencyLists[ll,EdgeWeight,Type-> Directed];
Row[{ShowGraph[gr,EdgeLabel->GetEdgeWeights[gr],EdgeLabelColor->Red,EdgeLabelPosition->{{.0,.05},{.1,-.05},{.05,.05},{.05,.05},{.05,.05}}],ToAdjacencyMatrix[gr,EdgeWeight] //MatrixForm,ToAdjacencyMatrix[gr] //MatrixForm},Spacer[64]]

Обратите внимание, что при переходе к матрице смежности веса кратных ребер теряются не смотря на опции (из них берется максимальный). Ориентируемость – сохраняется. Отметим также, что визуализировать веса кратных ребер с помощью меток не тривиально, так как, во-первых, некорректно работает функция SetEdgeLabels и положение меток кратных ребер по умолчанию совпадают.

ll={{{2,.1},{2,π//N},{3,.13}},{{2,(Sqrt[3])//N},{3,Log[2]//N}},{}};
gr=FromAdjacencyLists[ll,EdgeWeight,Type-> Directed];
wgh=GetEdgeWeights[gr]
grr=SetEdgeLabels[gr,wgh];
Edges[grr,All]

Так же некорректно работает функция SetEdgeWeights.

ll={{2,2,3},{2,3},{}};
gr=FromAdjacencyLists[ll,Type-> Directed];
grr=SetEdgeWeights[gr,{.1,.2,.3,.4,.5}];
Edges[grr,All]

3...  Построение графов из уже имеющихся

Имеется много команд, позволяющих менять уже заданный граф. Вот лишь некоторые из них: AddEdge, AddEdges, DeleteEdge, DeleteEdges, RemoveMultipleEdges, MakeDirected,  MakeUndirected, AddVertex,  AddVertices,  DeleteVertex,  DeleteVertices, ReverseEdges (полный список содержится в разделе Constructing Graphs).

ShowGraphArray[{g11,AddEdges[g11,{{2,5},{2,4}}],g21,AddEdges[g21,{{2,5},{2,4}}]}]

gg=DeleteVertex[g11,1]; gg1=AddVertex[gg];gg2=AddEdges[AddVertex[gg],{{6,1},{6,2},{6,3},{6,4}}];
GraphicsRow[Framed/@ShowGraph/@{gg,gg1,gg2}]

В этом же разделе  Constructing Graphs описаны некоторые операции над графами, способы порождать случайные графы и деревья (см. определение ниже).

Отметим, что, по-видимому, авторы пакета Combinatorica предполагали, вместо непосредственного задания графов, использовать именно построение их из уже имеющихся. Поэтому операции над графами хорошо разработаны и имеется богатая коллекция встроенных графов, см. Built-in Graphs, а также огромная база GraphData.

Manipulate[If[SameQ[h,RandomGraph],ShowGraph[h[n,0.5]],ShowGraph[h[n]]],{{h,EmptyGraph},{EmptyGraph->"Пустой",Wheel->"Колесо",CompleteGraph->"Полный",Hypercube->"Гиперкуб",RandomGraph->"Случайный"},Setter},{{n,3},Drop[Range[7],2],PopupMenu}]

3...  Пример оптимизационной задачи: задача о кратчайших путях

Маршрутом γ  в графе G = (V,E) называется такая последовательность вида (Subscript[v, 1])(Subscript[e, 1])(Subscript[v, 2])... (Subscript[v, k])(Subscript[e, k])(Subscript[v, k+1]), где (Subscript[v, i])∈ V и (Subscript[e, i])∈ E, что для каждого i, 1 ≤ i ≤ k, ребро (Subscript[e, i])  соединяет вершину (Subscript[v, i]) с вершиной (Subscript[v, i+1]). Удобно говорить, что маршрут γ соединяет вершины (Subscript[v, 1])  и (Subscript[v, k+1]) , и называть такой маршут ((Subscript[v, 1]),(Subscript[v, k+1]))-маршрутом. Маршрут называется путём, если все его элементы, кроме, быть может, (Subscript[v, 1]) и (Subscript[v, k+1]), различны. Путь, в котором (Subscript[v, 1])=(Subscript[v, k+1]), называется циклом. Граф называется связным, если для каждых двух его различных вершин u и v существует (u, v)-маршрут.

Пусть G = (V,E)  –  ориентированный граф. Говорят, что вершина  v∈V достижима из u∈V, если существует некоторый (u,v)-маршрут.

Пусть G = (V,E) –  взвешенный граф (ориентированный или нет), и ω – весовая функция. Весом маршрута  называется сумма весов всех входящих в него ребер. Предположим, что вершина  v∈V достижима из u∈V, и рассмотрим множество Γ(u,v) всех (u , v)-маршрутов в G. Маршрут γ∈Γ(u, v) называется кратчайшим путем, если его вес не превосходит веса любого другого маршрута из Γ(u,v). Оказывается, если весовая функция ω не отрицательна, то существуют полиномиальные (порядка (n^3), где n – количество вершин) алгоритмы поиска кратчайшего пути. В Mathematica реализован известный алгоритмы  Dijkstra (для положительных весов), а также BellmanFord (для любых весов). Имеется несколько возможностей использования этих алгоритмов. Чтобы проиллюстрировать это, мы воспользуемся сначала генератором случайных графов и случайных весов ребер.

g:=SetEdgeWeights[ RandomGraph[17,.2,Type->Directed]];
SG[g_]:=Module[{gg,el},
gg=g;
el=Edges[gg,EdgeWeight];
ShowGraph[SetEdgeLabels[gg,#[[2]]&/@el] ,EdgeLabel->True,EdgeLabelColor->Green, VertexLabel->True,VertexLabelColor-> Red]
];

gcur=g;
SG[gcur]

Отметим, что такая визуализация не очень наглядная. Ниже мы предложим другие картинки, а пока прокомментируем, как работают нужные нам функции.

Команда ShortestPath[<граф>,<начальная вершина>,<конечная вершина>] выдает кратчайший путь в виде списка последовательных вершин:

sp=ShortestPath[gcur,1,#]&/@ Drop[Range[17],1]

Команда Dijkstra[<взвешенный граф>,<вершина>] ищет кратчайшие пути из заданной вершины во все остальные и выдает дерево, составленное из этих кратчайших путей, а также список весов этих путей. Если вершина не достижима, вес пути равен ∞. Дерево задано списком, на i-ом месте которого стоит номер предшественника i-ой вершины на ее кратчайшем пути.

dres=Dijkstra[gcur,1]

Column[{TreePlot[gcur,Center,1,VertexLabeling->True,DirectedEdges->True,PlotStyle->{Arrowheads[{{.02,0.5}}]}],
LayeredGraphPlot[gcur,VertexLabeling->True,DirectedEdges->True]},Spacer[4]]

Эта функция восстанавливает пути, найденные процедурой  Dijkstra.

path[end_,start_,dij_]:=Module[{ic,p,spt},If[dij[[2,end]]==∞,{start},
spt=dij[[1]];ic=end;p={end};While[spt[[ic]]≠start,ic=spt[[ic]];p={ic}~Join~p]; {start}~Join~p]];

path[#,1,dres]&/@ Drop[Range[17],1]

Если забыть про ориентацию ребер, то кратчайшие пути могут измениться, так как возникают дополнительные возможности.

DynamicModule[{n=11,gres=gcur},
(*gcur=SetEdgeWeights[ RandomGraph[11,.2,Type->Directed]];*)
Manipulate[If[dir,gres=gcur,gres=MakeUndirected [gcur]];
shortPShowL[gcur,ShortestPath[gres,i,j],i,j,dir],{{i,1,"Начальная вершина"},Range[V[gcur]],ControlType->PopupMenu},
{{j,2,"Терминальная вершина"},Range[V[gcur]],ControlType->PopupMenu},{{dir,True,"Ориентируемость"},{True,False}},SaveDefinitions->True],
Initialization:>(Needs["Combinatorica`"];
edgeW[g_,e_]:=GetEdgeWeights[g,{e}][[1]];
shortPShowL[g_,p_,ii_,jj_,test_]:=
Module[{edg,ll,ends,ϵ=0.1},
edg=Table[Take[p,{i,i+1}],{i,1,Length[p]-1}]; ends={ii,jj};
ll=edg~Join~(RotateLeft[#,1]&/@edg);If[Length[p]<2,Show[{Graphics[Text[Style["Путей НЕТ",Red,Bold,Large],{0,0}]],
LayeredGraphPlot[g,
EdgeRenderingFunction->(If[test,{Black,Arrowheads[{{.02,0.5}}],Arrow[#1]},{Black,Line[#1]}] &),
VertexRenderingFunction->({If[MemberQ[ends,#2],Pink,White],EdgeForm[Black],Disk[#,.5],Black,Text[#2,#1]}&),ImageSize->600]
}],
LayeredGraphPlot[g,
EdgeRenderingFunction->(If[MemberQ[ll,#2],{Red},{Orange,Opacity[0.5]}]~Join~If[test,{Arrowheads[{{.02,0.5}}],Arrow[#1]} ,{Line[#1]}]&),
VertexRenderingFunction->({Which[MemberQ[ends,#2],Pink,MemberQ[p,#2],LightBlue,True,White],EdgeForm[Black],Disk[#,.5],Black,Text[#2,#1]}&),ImageSize->600]
]])]

Если выделенной вершины нет, то проще применить процедуру ShortestPath. Для визуализации воспользуемся продвинутыми возможностями GraphPlot3D. Ребра изобразим в виде разноцветных цилиндров разной толщины. Толщина  и  цвет зависят от веса. Ребра кратчайшего пути выделены матовым красным. Номера концевых вершин пути – черные, промежуточных вершин – синие. Напомним, что двигая мышкой при нажатой клавише <Alt> можно приблизить-удалить объект, а при нажатой клавише <Shift> – сместить его в сторону.

DynamicModule[{},
(*gcur=SetEdgeWeights[ RandomGraph[11,.2,Type->Directed]];*)
Manipulate[shortPathShow[gcur,ShortestPath[gcur,i,j],r],{{i,1},Range[V[gcur]],ControlType->PopupMenu},
{{j,2},Range[V[gcur]],ControlType->PopupMenu},{{r,0.1},0.01,0.4},SaveDefinitions->True],
Initialization:>(Needs["Combinatorica`"];
edgeWeight[g_,e_]:=GetEdgeWeights[g,{e}];shortPathShow[g_,p_,r_]:=Module[{edg,ll,ends,ϵ=0.1},edg=Table[Take[p,{i,i+1}],{i,1,Length[p]-1}]; ends={p[[1]],p[[-1]]};
ll=edg~Join~(RotateLeft[#,1]&/@edg);If[Length[p]<2,Show[{Graphics3D[Text[Style["Нет пути!",Red,Bold,Large],{0,0,0}]],
GraphPlot3D[g,
EdgeRenderingFunction->({Hue[edgeWeight[g,#2]],Cylinder[#1,r edgeWeight[g,#2]]} &),
VertexRenderingFunction->({Yellow,Sphere[#1,r+0.03],Text[Style[#2,Green,Bold,Large],#1+{ϵ,ϵ,ϵ}]}&),ImageSize->500,ViewPoint->{3.25,0.57,3.25}]
}],
GraphPlot3D[g,
EdgeRenderingFunction->(If[MemberQ[ll,#2],{Glow[Black],Red},{Lighter[Hue[edgeWeight[g,#2]],.5]}]~Join~{Cylinder[#1,Max[r edgeWeight[g,#2],0.01]]} &),
VertexRenderingFunction->({If[MemberQ[p,#2],Red,Yellow],Sphere[#1,r+0.03],Text[Style[#2,Which[MemberQ[ends,#2],Black,MemberQ[p,#2],Blue,True,Green],Bold,Large],#1+{ϵ,ϵ,ϵ}]}&),Boxed->False,ImageSize->500,ViewPoint->{3.25,0.57,3.25}]
]])]

В этом варианте картинка двумерная, веса ребер снова проиллюстрированы их толщиной. Зато хорошо видны стрелки.

DynamicModule[{n=11},
Manipulate[shortPShow[gcur,ShortestPath[gcur,i,j],i,j,r],{{i,1},Range[V[gcur]],ControlType->PopupMenu},
{{j,2},Range[V[gcur]],ControlType->PopupMenu},{{r,0.003},0.003,.01},SaveDefinitions->True],
Initialization:>(Needs["Combinatorica`"];
edgeW[g_,e_]:=GetEdgeWeights[g,{e}][[1]];
shortPShow[g_,p_,ii_,jj_,r_]:=
Module[{edg,ll,ends,ϵ=0.1},
edg=Table[Take[p,{i,i+1}],{i,1,Length[p]-1}]; ends={ii,jj};
ll=edg~Join~(RotateLeft[#,1]&/@edg);If[Length[p]<2,Show[{Graphics[Text[Style["Путей НЕТ",Red,Bold,Large],{0,0}]],
GraphPlot[g,
EdgeRenderingFunction->({Black,Arrowheads[{{0.02,0.5}}],Arrow[#1]} &),
VertexRenderingFunction->({If[MemberQ[ends,#2],Pink,White],EdgeForm[Black],Disk[#,.1],Black,Text[#2,#1]}&),ImageSize->500]
}],
GraphPlot[g,
EdgeRenderingFunction->(If[MemberQ[ll,#2],{Blue},{Orange,Opacity[0.5]}]~Join~{Thickness[r edgeW[g,#2]],Arrowheads[{{3r ,0.5}}],Arrow[#1,.1]} &),
VertexRenderingFunction->({Which[MemberQ[ends,#2],Pink,MemberQ[p,#2],LightBlue,True,White],EdgeForm[Black],Opacity[0.7],Disk[#,.1],Opacity[1],Black,Text[#2,#1]}&),ImageSize->500]
]])]

3...  Пример оптимизационной задачи: задача о минимальном остовном дереве

Связный граф без циклов называется деревом. Понятие дерева играет важную роль в приложениях, поскольку моделирует такой вид соединения своих вершин, в котором "нет ничего лишнего".

Подграфом H в графе G = ((Subscript[V, G]),(Subscript[E, G])) называется такой граф H = ((Subscript[V, H]),(Subscript[E, H])), что (Subscript[V, H])⊂ V, и (Subscript[E, H])⊂ E. Если граф G – взвешенный с весовой функцией ω, то для каждого его подграфа H естественно определяется его вес, равный сумме весов всех ребер этого подграфа.

Подграф H ⊂ G называется остовным, если (Subscript[V, H])=(Subscript[V, G]). В каждом связном графе, очевидно, имеется остовный подграф, являющийся деревом. Такие подграфы называются остовными деревьями. Количество разных остовных деревьев зависит от структуры графа. Для простого связного графа оно может быть вычислено с помощью так называемой матричной теоремы Кирхгофа. Интересующая нас точная оценка сверху имеет вид (n^(n-2)), где n – количество вершин графа.

Остовное дерево наименьшего веса в связном взвешенном графе называется минимальным остовным деревом. Несмотря на упомянутую оценку, имеются полиномиальные алгоритмы построения минимальных остовных деревьев. Одним из таких алгоритмов является алгоритм Крускала .

Пусть G=(V,E) – связный взвешенный граф с весовой функцией ω. Определим граф (Subscript[T, 0])=(V,∅). На i-ом шаге, 1≤ i≤ n-1, среди всех ребер, добавление которых к  (Subscript[T, i-1]) порождает ацикличный граф, выберем  ребро наименьшего веса и добавим к (Subscript[T, i-1]), получив тем самым (Subscript[T, i]). Алгоритм заканчивает работу, построив граф (Subscript[T, n-1]), который и является минимальным остовным деревом.

В пакете Combinatorica имеется команда  MinimumSpanningTree [<граф>], возвращающая минимальное остовное дерево в формате Graph.

Снова нарисуем красивые картинки.

DynamicModule[{gu,gcur,mst,n=11},
gu=RandomGraph[n,.6];
While[!ConnectedQ[gu],gu=RandomGraph[n,.6]];
gcur=SetEdgeWeights[gu];
mst=MinimumSpanningTree[gcur];
Manipulate[plot3DWGraph[gcur,Edges[mst],r,{Glow[Red], Brown}],{r,0.01,0.2}],
Initialization:>(Needs["Combinatorica`"];
edgeWeight[g_,e_]:=GetEdgeWeights[g,{e}];
plot3DWGraph[g_,l_,r_,col_,op_:1]:=Module[{ll},
ll=l~Join~(RotateLeft[#,1]&/@l);
GraphPlot3D[g,
EdgeRenderingFunction->(If[MemberQ[ll,#2],col,{Lighter[Hue[edgeWeight[g,#2]],.9],Opacity[op]}]~Join~{Cylinder[#1,Max[r edgeWeight[g,#2],0.01]]} &),
VertexRenderingFunction->({Yellow,Sphere[#,r+0.03]}&),Boxed->False]
])]

DynamicModule[{gu,gcur,mst,n=11},
gu=RandomGraph[n,.6];
While[!ConnectedQ[gu],gu=RandomGraph[n,.6]];
gcur=SetEdgeWeights[gu];
mst=MinimumSpanningTree[gcur];
Manipulate[plotWGraph[gcur,Edges[mst],r,Red, Orange],{r,0.01,0.1}],
Initialization:>(Needs["Combinatorica`"];
edgeW[g_,e_]:=GetEdgeWeights[g,{e}][[1]];
plotWGraph[g_,l_,r_,col1_,col2_]:=Module[{ll},
ll=l~Join~(RotateLeft[#,1]&/@l);
GraphPlot[g,
EdgeRenderingFunction->(If[MemberQ[ll,#2],{col1,Thickness[r edgeW[g,#2]],Line[#1]},{col2,Thickness[r edgeW[g,#2]],Opacity[0.4],Line[#1]}] &),
VertexLabeling->True]
])]

3...  Пример оптимизационной задачи: евклидовы минимальные остовные деревья, триангуляции Делоне, диаграммы Вороного

Если множество вершин графа содержится в метрическом пространстве (X,ρ), то весовая функция на ребрах такого графа естественно определяется как ρ-расстояние между соответствующими вершинами. Минимальное остовное дерево (МОД) в полном графе с вершинами в метрическом пространстве называется метрическим МОД. В частном случае, когда метрическое пространство – это евклидово пространство, а весовая функция – евклидово расстояние между точками, метрическое МОД называют ЕМОД.

В этом примере рассматривается случай евклидовой плоскости. Нам показалось удобнее самим написать процедуру рисования графов. Пунктир изображает полный граф. Отметим, что когда количество точек становится порядка 20 и выше, программа начинает все более заметно тормозить. Это связано с тем, что алгоритм Краскала имеет порядок сложности, пропорциональный квадрату количества ребер графа, т.е., для полного графа – четвертая степень от колическтва вершин. (Последнее связано с тем, что количество ребер полного графа растет квадратично с ростом числа его вершин.)  Тут на помощь приходит геометрия. Оказывается, ЕМОД (полного) графа всегда лежит в его специальном подграфе с линейным количеством ребер, а именно, в так называемой триангуляции Делоне.

DynamicModule[{pts,pCG,pts0,vv,mst,ee,delauney,showTr},
pts0={{1,0},{0,1},{-1,0}};
Manipulate[vv=Map[{#,VertexNumber->True}&,pts];
pCG=SetEdgeWeights[Graph[CompleteGraph[Length[pts]][[1]],vv],WeightingFunction->Euclidean];
mst=MinimumSpanningTree[pCG];
ee=Edges[mst];
delauney=FromAdjacencyLists[#[[2]]&/@DelaunayTriangulation[pts]];
Show[If[showTr,{showCG[Length[pts],pts,ee],showGr[delauney,pts,{Black}]},showCG[Length[pts],pts,ee]],PlotRange->{{-2,2},{-2,2}}],{{pts,pts0},Locator,LocatorAutoCreate->True},
{{showTr,False,"Показать триангуляцию Делоне"},{True,False}}],Initialization:>(Needs["Combinatorica`"];Needs["ComputationalGeometry`"];showCG[n_,v_,edg_:{}]:=Graphics[GraphicsComplex[v,If[MemberQ[edg,#[[1]]],{Red,Thickness[0.015],Opacity[0.7],Line[#[[1]]]},{Blue,Dotted,Line[#[[1]]]}]&/@CompleteGraph[n][[1]]]];
showGr[g_,v_,col_:{Blue}]:=Graphics[GraphicsComplex[v,Append[col,Line[Edges[g]] ]]];)
]

Триангуляция Делоне тесно связана с так называемой диаграммой Вороного конечного подмножества  M  евкдидова пространства. Если M={(Subscript[m, 1]),... , (Subscript[m, n])}, n≥2, то ячейкой Вороного точки (Subscript[m, i]) называется множество W((Subscript[m, i]))={x| ρ((Subscript[m, i]),x)≤ ρ ((Subscript[m, j]),x) для  всех j}, где через ρ, как и выше, обозначена функция расстояния. Ячейки Вороного точек двухточечного множества M={(Subscript[m, 1]),(Subscript[m, 2])} – суть полупространства (в двумерном случае – полуплоскости), порожденные серединным перпендикуляром к отрезку [(Subscript[m, 1]),(Subscript[m, 2])]. В общем случае – это выпуклые многогранные области, полученные пересечением соответствующих полупространств.

Manipulate[DiagramPlot[ pp],{{pp,{{0,0},{1,0}}},Locator,LocatorAutoCreate->True}]

Триангуляция Делоне – это граф на множестве точек M евклидова пространства, две вершины которого соединены ребром-отрезком, если и только если ячейки Вороного этих вершин пересекаются по множеству коразмерности один. В случае плоскости – по отрезку или лучу.

DynamicModule[{pts,pts0,vor,delauney},
pts0={{1,0},{0,1},{-1,0},{0,-1}};
Manipulate[
delauney=FromAdjacencyLists[#[[2]]&/@DelaunayTriangulation[pts]];
Show[{showDiaG[pts],showGr[delauney,pts,{Blue}]},PlotRange->{{-2,2},{-2,2}}],{{pts,pts0},Locator,LocatorAutoCreate->True}],
Initialization:>(Needs["Combinatorica`"];Needs["ComputationalGeometry`"];
pairs[ls_]:=Table[{ls[[i]],ls[[i+1]]},{i,1,Length[ls]-1}];
showGr[g_,v_,col_:{Blue}]:=Graphics[GraphicsComplex[v,Append[col,Line[Edges[g]] ]]];
showDiaG[pp_]:=Module[{hh,vd,ln,edg,rs,cls},
vd=VoronoiDiagram[pp];
hh=Head[#]&/@vd[[1]];
ln=Union[Sort/@Flatten[pairs[#]&/@Select[Table[Select[vd[[2,i,2]],hh[[#]]==List&],{i,1,Length[vd[[2]]]}],Length[#]>1&],1]];
edg=Line[vd[[1]][[#]]]&/@ln;
rs=Select[vd[[1]],Head[#]== Ray&];
Graphics[edg~Join~(Line/@Apply[List,rs,{1}])]
];)
]

На следующей картинке ячейки Вороного раскрашены в разные цвета.

DynamicModule[{pts,pts0,vor,delauney},
pts0={{1,0},{0,1},{-1,0},{0,-1}};
Manipulate[
delauney=FromAdjacencyLists[#[[2]]&/@DelaunayTriangulation[pts]];
Show[{showDia[pts],showGr[delauney,pts,{Blue}]},PlotRange->{{-2,2},{-2,2}}],{{pts,pts0},Locator,LocatorAutoCreate->True}],
Initialization:>(Needs["Combinatorica`"];Needs["ComputationalGeometry`"];
showGr[g_,v_,col_:{Blue}]:=Graphics[GraphicsComplex[v,Append[col,Line[Edges[g]] ]]];
append[l_,r_]:=Module[{bg,en,res},
If[Length[r]≠4,res=l~Join~r,
bg=r[[{1,2}]];
en=r[[{3,4}]];
Which[bg[[1]]==l[[1]],res={bg[[2]],bg[[1]]}~Join~l,
bg[[2]]==l[[1]],res=bg~Join~l,
bg[[1]]==l[[-1]],res=l~Join~bg,
bg[[2]]==l[[-1]],res=l~Join~{bg[[2]],bg[[1]]}
];
Which[en[[1]]==l[[1]],res={en[[2]],en[[1]]}~Join~res,
en[[2]]==l[[1]],res=en~Join~res,
en[[1]]==l[[-1]],res=res~Join~en,
en[[2]]==l[[-1]],res=res~Join~{en[[2]],en[[1]]}
]
];
res
];
showDia[pp_]:=Module[{hh,vd,ln,rs,cls,pl},
vd=VoronoiDiagram[pp];
hh=Head[#]&/@vd[[1]];
ln=vd[[1]][[#]]&/@Table[Select[vd[[2,i,2]],hh[[#]]==List&],{i,1,Length[vd[[2]]]}];
rs=Map[If[Length[#]>0,Flatten[Apply[List,#,1],1],{}]&,vd[[1]][[#]]&/@Table[Select[vd[[2,i,2]],hh[[#]]==Ray&],{i,1,Length[vd[[2]]]}]];
cls=MapThread[append[#1,#2]&,{ln,rs}];
(*Print[{"ln = ",ln,"rs = ",rs,"cls = ",cls}];*)
pl=Polygon[#]&/@cls;
Graphics[Table[{EdgeForm[{Thick,Dashed}],ColorData[Length[pp],"ColorList"][[i]],Opacity[0.7], pl[[i]],Black,PointSize[0.02], Point[pp[[i]]]},{i,1,Length[pp]}]]
];)
]

Возвращаясь к задаче о ЕМОД, с помощью триангуляции Делоне можно построить квадратичный (по количеству вершин) алгоритм построения ЕМОД. А имено, сначала строим триангуляцию Делоне, а затем уже к ней применяем алгоритм Краскала.

DynamicModule[{pts,pts0,mst,ee,delauney, showTr},
pts0={{1,0},{0,1},{-1,0}};
showGr[g_,v_,col_:{Blue}]:=Graphics[GraphicsComplex[v,Append[col,Line[Edges[g]] ]]];
Manipulate[
delauney=SetEdgeWeights[FromAdjacencyLists[#[[2]]&/@DelaunayTriangulation[pts],pts],WeightingFunction->Euclidean];
mst=MinimumSpanningTree[delauney];
Show[If[showTr,{showGr[mst,pts,{Red,Thickness[0.01],Opacity[0.7]}],showGr[delauney,pts,{Blue}]},
showGr[mst,pts,{Red,Thickness[0.01]}]],PlotRange->{{-2,2},{-2,2}}],{{pts,pts0},Locator,LocatorAutoCreate->True},
{{showTr,False,"Показать триангуляцию Делоне"},{True,False}}],
Initialization:>(Needs["Combinatorica`"];Needs["ComputationalGeometry`"])
]

Замечание. На самом деле, в общем случае алгоритм Краскала построения  МОД работает со скоростью |E| Log|E|. Алгоритм построения ЕМОД, использующий триангуляцию Делоне,  работает со скоростью |V| Log |V|.

В качестве примера, построим минимальные остовные деревья, соединяющие крупные города Германии и Великобритании. На самом деле, Mathematica включает в себя большие базы данных по естественным наукам, в частности, по географии. Эти базы данных, впрочем, находятся на сайте компании Wolfram, поэтому, чтобы ими пользоваться непоредственно, нужен доступ к сети. В приведенных примерах мы просто выкачали информацию о геометричекой форме страны и ее флаге из базы CountryData, и координаты и названия крупных (больше 100000 жителей) городов выбранных стран из базы CityData. Отметим также наличие баз данных по молекулярной биологии, астрономии, физике, химии, лингвистике, финансам и пр., см. Scientific & Technical Data.

germCitiesCoord={{{52.52`,13.38`}},{{53.55`,10.`}},{{48.14`,11.58`}},{{50.95`,6.97`}},{{50.120000000000005`,8.68`}},{{51.47`,7.`}},{{48.79`,9.19`}},{{51.51`,7.48`}},{{51.24`,6.79`}},{{53.08`,8.81`}},{{52.4`,9.73`}},{{51.43`,6.75`}},{{51.35`,12.4`}},{{49.45`,11.05`}},{{51.050000000000004`,13.74`}},{{51.480000000000004`,7.2`}},{{51.26`,7.18`}},{{52.03`,8.53`}},{{50.730000000000004`,7.1000000000000005`}},{{49.5`,8.47`}},{{49.`,8.4`}},{{50.08`,8.23`}},{{51.96`,7.62`}},{{51.51`,7.11`}},{{50.77`,6.09`}},{{51.2`,6.42`}},{{48.36`,10.89`}},{{50.83`,12.92`}},{{52.27`,10.51`}},{{51.480000000000004`,11.96`}},{{51.33`,6.55`}},{{54.32`,10.120000000000001`}},{{52.13`,11.620000000000001`}},{{51.47`,6.86`}},{{47.99`,7.8500000000000005`}},{{53.870000000000005`,10.66`}},{{50.99`,11.03`}},{{51.370000000000005`,7.46`}},{{54.09`,12.1`}},{{51.32`,9.48`}},{{51.67`,7.8`}},{{50.`,8.26`}},{{49.25`,6.97`}},{{51.54`,7.21`}},{{51.43`,6.86`}},{{52.28`,8.05`}},{{51.18`,7.0600000000000005`}},{{49.480000000000004`,8.44`}},{{51.04`,6.99`}},{{53.15`,8.21`}},{{51.2`,6.69`}},{{49.42`,8.69`}},{{51.72`,8.74`}},{{49.870000000000005`,8.64`}},{{49.800000000000004`,9.94`}},{{49.02`,12.11`}},{{52.43`,10.78`}},{{51.61`,7.19`}},{{51.53`,9.92`}},{{49.14`,9.22`}},{{48.77`,11.43`}},{{48.4`,9.97`}},{{51.53`,6.93`}},{{48.89`,8.69`}},{{50.1`,8.77`}},{{53.550000000000004`,8.58`}},{{52.4`,13.07`}},{{51.18`,7.19`}},{{48.49`,9.21`}},{{49.480000000000004`,10.98`}},{{52.17`,10.33`}},{{51.45`,6.65`}},{{50.35`,7.6000000000000005`}},{{50.870000000000005`,8.01`}},{{50.980000000000004`,7.15`}},{{50.93`,11.58`}},{{50.88`,12.08`}},{{52.160000000000004`,9.950000000000001`}},{{49.6`,11.01`}},{{51.44`,7.34`}},{{49.75`,6.63`}}};
ukCitiesCoord={{{51.5`,-0.1166667`}},{{52.4666667`,-1.9166667`}},{{55.8333333`,-4.25`}},{{53.4166667`,-3.`}},{{53.794161837371`,-1.55319213867188`}},{{53.3666667`,-1.5`}},{{55.95`,-3.2`}},{{51.45`,-2.5833333`}},{{53.5`,-2.2166667`}},{{52.6333333`,-1.1333333`}},{{52.4166667`,-1.55`}},{{53.7166667`,-0.3333333`}},{{51.5`,-3.2`}},{{53.7833333`,-1.75`}},{{54.5833333`,-5.9333333`}},{{53.`,-2.1833333`}},{{52.5833333`,-2.1333333`}},{{50.3963889`,-4.1386111`}},{{52.9666667`,-1.1666667`}},{{50.9`,-1.4`}},{{51.4333333`,-1.`}},{{52.9333333`,-1.5`}},{{52.5`,-2.0833333`}},{{52.25`,-0.8833333`}},{{50.8090805768295`,-1.07142448425293`}},{{51.8833333`,-0.4166667`}},{{54.9880556`,-1.6194444`}},{{53.7666667`,-2.7166667`}},{{57.1333333`,-2.1`}},{{54.9119444`,-1.3833333`}},{{52.6333333`,1.3`}},{{50.7166667`,-1.8833333`}},{{52.6`,-2.`}},{{51.6333333`,-3.9666667`}},{{51.5333333`,0.7`}},{{51.7522210025796`,-1.25596046447754`}},{{56.5`,-2.9666667`}},{{50.7166667`,-2.`}},{{53.65`,-1.7833333`}},{{53.9666667`,-1.0833333`}},{{52.0546544307833`,1.15699768066406`}},{{53.8166667`,-3.05`}},{{54.5727778`,-1.1627778`}},{{53.5833333`,-2.4333333`}},{{52.5833333`,-0.25`}},{{53.4`,-2.15`}},{{50.8283849472495`,-0.139474868774414`}},{{52.5166667`,-2.`}},{{51.5`,-0.5833333`}},{{51.8333333`,-2.25`}},{{52.2`,0.1166667`}},{{51.6666667`,-0.4`}},{{53.4333333`,-1.35`}},{{51.5833333`,-2.9833333`}},{{50.7`,-3.5333333`}},{{50.8`,0.25`}},{{51.8833333`,0.9`}},{{51.1166667`,-0.1833333`}},{{52.5651863563903`,-1.82235717773438`}},{{53.75`,-2.4833333`}},{{53.55`,-2.1166667`}},{{51.3166667`,-0.5333333`}},{{51.9`,-2.0833333`}},{{51.7333333`,0.4833333`}},{{53.45`,-2.7333333`}},{{51.5666667`,0.4666667`}},{{51.4`,0.5666667`}},{{52.2`,-2.2`}}};
germCitiesNames={"Berlin","Hamburg","Munich","Cologne","Frankfurt","Essen","Stuttgart","Dortmund","Dusseldorf","Bremen","Hanover","Duisburg","Leipzig","Nuremberg","Dresden","Bochum","Wuppertal","Bielefeld","Bonn","Mannheim","Karlsruhe","Wiesbaden","Munster","Gelsenkirchen","Aachen","Monchengladbach","Augsburg","Chemnitz","Brunswick","Halle","Krefeld","Kiel","Magdeburg","Oberhausen","Freiburg","Lubeck","Erfurt","Hagen","Rostock","Kassel","Hamm","Mainz","Saarbrucken","Herne","Mulheim","Osnabruck","Solingen","Ludwigshafen","Leverkusen","Oldenburg","Neuss","Heidelberg","Paderborn","Darmstadt","Wurzburg","Ratisbon","Wolfsburg","Recklinghausen","Gottingen","Heilbronn","Ingolstadt","Ulm","Bottrop","Pforzheim","Offenbach","Bremerhaven","Potsdam","Remscheid","Reutlingen","Furth","Salzgitter","Moers","Koblenz","Siegen","Bergisch Gladbach","Jena","Gera","Hildesheim","Erlangen","Witten","Trier"};
ukCitiesNames={"London","Birmingham","Glasgow","Liverpool","Leeds","Sheffield","Edinburgh","Bristol","Manchester","Leicester","Coventry","Kingston upon Hull","Caerdydd","Bradford","Belfast","Stoke-on-Trent","Wolverhampton","Plymouth","Nottingham","Southampton","Reading","Derby","Dudley","Northampton","Portsmouth","Luton","Newcastle upon Tyne","Preston","Aberdeen","Sunderland","Norwich","Bournemouth","Walsall","Swansea","Southend-on-Sea","Oxford","Dundee","Poole","Huddersfield","York","Ipswich","Blackpool","Middlesbrough","Bolton","Peterborough","Stockport","Brighton","West Bromwich","Slough","Gloucester","Cambridge","Watford","Rotherham","Casnewydd","Exeter","Eastbourne","Colchester","Crawley","Sutton Coldfield","Blackburn","Oldham","Woking","Cheltenham","Chelmsford","Saint Helens","Basildon","Gillingham","Worcester"};
germPoly=Polygon[{{{5.90725`,50.7242`},{6.02985`,50.8203`},{6.07395`,50.8833`},{6.08445`,50.9323`},{6.05505`,50.9715`},{6.02985`,50.9785`},{5.9689`,50.9715`},{5.88065`,51.0234`},{5.87225`,51.0444`},{5.90585`,51.0682`},{6.04555`,51.1319`},{6.0834`,51.1767`},{6.0897`,51.223`},{6.0729`,51.2356`},{5.99725`,51.23`},{5.97835`,51.237`},{5.98675`,51.2538`},{6.0855`,51.3182`},{6.1359`,51.3798`},{6.15375`,51.4632`},{6.12645`,51.5164`},{6.08235`,51.5556`},{6.0739`,51.6663`},{6.0382`,51.7111`},{5.9342`,51.772`},{5.9048`,51.8239`},{5.9006`,51.8967`},{5.9405`,51.9205`},{6.00985`,51.9317`},{6.1191`,51.9219`},{6.1863`,51.9093`},{6.28295`,51.8799`},{6.3586`,51.8757`},{6.48045`,51.9107`},{6.6107`,51.9191`},{6.7042`,51.9226`},{6.7567`,51.9478`},{6.7714`,51.9786`},{6.7693`,52.0109`},{6.7483`,52.0249`},{6.7063`,52.0291`},{6.65795`,52.0557`},{6.65375`,52.0809`},{6.6769`,52.1033`},{6.8933`,52.2056`},{6.9794`,52.2336`},{7.00355`,52.2567`},{7.02875`,52.3575`},{7.0519`,52.4038`},{7.0393`,52.4304`},{6.99725`,52.4598`},{6.867`,52.4836`},{6.6611`,52.534`},{6.64325`,52.5488`},{6.64955`,52.5684`},{6.7168`,52.6468`},{6.7294`,52.6636`},{6.7588`,52.6706`},{6.93315`,52.672`},{6.9668`,52.6678`},{6.9899`,52.679`},{7.0319`,52.7967`},{7.04665`,52.8625`},{7.11705`,52.9753`},{7.14225`,53.0859`},{7.10235`,53.1504`},{6.9228`,53.3489`},{6.98895`,53.3211`},{7.0476`,53.3093`},{7.0902`,53.314`},{7.10085`,53.3288`},{7.10615`,53.3501`},{7.09375`,53.3726`},{7.07955`,53.3903`},{7.0138`,53.3998`},{6.95515`,53.4045`},{6.92495`,53.4294`},{6.92495`,53.453`},{6.9925`,53.5092`},{6.9943`,53.5471`},{7.0565`,53.611`},{7.11865`,53.6536`},{7.19505`,53.6808`},{7.2839`,53.6932`},{7.59475`,53.695`},{7.7262`,53.7245`},{7.85945`,53.7482`},{7.91455`,53.7494`},{7.9696`,53.7423`},{7.9856`,53.7269`},{7.99805`,53.6879`},{8.0176`,53.6577`},{8.08865`,53.6139`},{8.1082`,53.5855`},{8.1082`,53.569`},{8.08865`,53.5477`},{8.06555`,53.5311`},{8.0194`,53.5181`},{8.00695`,53.5181`},{7.9661`,53.5098`},{7.96255`,53.4909`},{7.99805`,53.4755`},{8.0407`,53.4755`},{8.0798`,53.472`},{8.1029`,53.4619`},{8.13665`,53.4406`},{8.15975`,53.4442`},{8.1722`,53.4607`},{8.1775`,53.4785`},{8.1917`,53.4992`},{8.1935`,53.5181`},{8.18285`,53.5364`},{8.1633`,53.5672`},{8.1651`,53.5944`},{8.1793`,53.6122`},{8.2255`,53.6252`},{8.2752`,53.6133`},{8.3374`,53.5885`},{8.3907`,53.579`},{8.40845`,53.5708`},{8.4227`,53.5518`},{8.4227`,53.5299`},{8.4067`,53.453`},{8.3978`,53.382`},{8.3783`,53.3465`},{8.3623`,53.2874`},{8.37115`,53.246`},{8.3907`,53.2377`},{8.40135`,53.2483`},{8.42625`,53.2791`},{8.46175`,53.314`},{8.4742`,53.3389`},{8.4795`,53.3672`},{8.4742`,53.4158`},{8.47065`,53.4631`},{8.4831`,53.4897`},{8.5151`,53.543`},{8.51865`,53.5666`},{8.49375`,53.595`},{8.42095`,53.6814`},{8.41025`,53.7009`},{8.4227`,53.7447`},{8.48845`,53.8322`},{8.5435`,53.8866`},{8.5915`,53.9062`},{8.64835`,53.9014`},{8.6874`,53.8837`},{8.72115`,53.8683`},{8.76915`,53.8659`},{8.93255`,53.8713`},{9.0729`,53.8772`},{9.17415`,53.8606`},{9.2488`,53.8375`},{9.44595`,53.6701`},{9.5454`,53.5838`},{9.5845`,53.5719`},{9.7284`,53.5542`},{9.85275`,53.5376`},{9.9096`,53.5293`},{9.9185`,53.5388`},{9.8741`,53.5601`},{9.84385`,53.5678`},{9.7266`,53.5867`},{9.5827`,53.6151`},{9.5436`,53.6376`},{9.46185`,53.721`},{9.3659`,53.8062`},{9.2238`,53.905`},{9.12605`,53.9428`},{9.0621`,53.9487`},{8.98575`,53.9452`},{8.91645`,53.9381`},{8.8294`,53.944`},{8.8045`,53.9629`},{8.785`,54.028`},{8.7921`,54.0505`},{8.8152`,54.0706`},{8.8454`,54.073`},{8.8738`,54.0647`},{8.91465`,54.0517`},{8.9413`,54.0469`},{8.9644`,54.0576`},{8.98215`,54.0759`},{8.9875`,54.0961`},{8.98395`,54.1221`},{8.96615`,54.1481`},{8.9395`,54.1635`},{8.87555`,54.1599`},{8.8045`,54.1623`},{8.7654`,54.186`},{8.7583`,54.2061`},{8.76895`,54.2286`},{8.7761`,54.2493`},{8.8081`,54.2682`},{8.8543`,54.2765`},{8.8685`,54.2871`},{8.86495`,54.2966`},{8.8294`,54.3001`},{8.769`,54.2942`},{8.69975`,54.3037`},{8.6482`,54.2942`},{8.59315`,54.2954`},{8.5487`,54.3096`},{8.53095`,54.3368`},{8.53275`,54.3522`},{8.56115`,54.3664`},{8.57715`,54.3782`},{8.5789`,54.3971`},{8.58245`,54.419`},{8.59845`,54.4332`},{8.6322`,54.438`},{8.64465`,54.4344`},{8.69085`,54.4309`},{8.7246`,54.4415`},{8.74945`,54.4415`},{8.80455`,54.4249`},{8.84185`,54.4261`},{8.87385`,54.4344`},{8.93955`,54.4604`},{8.96265`,54.4806`},{8.9502`,54.4983`},{8.9289`,54.5172`},{8.90045`,54.5403`},{8.8596`,54.577`},{8.8134`,54.5983`},{8.77255`,54.6492`},{8.72455`,54.7042`},{8.6482`,54.7586`},{8.55225`,54.8604`},{8.554`,54.8899`},{8.5576`,54.9201`},{8.56805`,54.9392`},{8.64445`,54.9295`},{8.8199`,54.9215`},{9.2261`,54.875`},{9.31625`,54.871`},{9.4364`,54.8886`},{9.48118`,54.8886`},{9.4387`,54.8693`},{9.3996`,54.8303`},{9.40495`,54.8137`},{9.44225`,54.8102`},{9.476`,54.8232`},{9.51685`,54.8539`},{9.53285`,54.8628`},{9.56835`,54.8498`},{9.62165`,54.8203`},{9.68205`,54.8084`},{9.73`,54.7871`},{9.7904`,54.7836`},{9.8117`,54.8049`},{9.82595`,54.8297`},{9.86145`,54.8357`},{9.913`,54.812`},{9.9361`,54.7635`},{9.90945`,54.7209`},{9.8153`,54.6754`},{9.72115`,54.621`},{9.6643`,54.5654`},{9.6465`,54.5535`},{9.56125`,54.55`},{9.5417`,54.5322`},{9.5577`,54.5157`},{9.64295`,54.492`},{9.68025`,54.4962`},{9.70335`,54.5163`},{9.71755`,54.547`},{9.73`,54.5742`},{9.7691`,54.6062`},{9.8526`,54.6417`},{9.88635`,54.6642`},{9.90945`,54.6689`},{9.929`,54.66`},{9.95385`,54.6233`},{9.9414`,54.55`},{9.91835`,54.5168`},{9.87215`,54.4944`},{9.79575`,54.4802`},{9.7922`,54.4648`},{9.80465`,54.4506`},{9.9041`,54.4459`},{9.9663`,54.4577`},{10.0285`,54.463`},{10.1191`,54.4701`},{10.1476`,54.4689`},{10.16`,54.45`},{10.1476`,54.4275`},{10.1334`,54.4027`},{10.1103`,54.3743`},{10.1032`,54.366`},{10.1263`,54.3589`},{10.1582`,54.3672`},{10.1742`,54.379`},{10.24`,54.4263`},{10.2861`,54.4453`},{10.3377`,54.45`},{10.3803`,54.4435`},{10.4744`,54.4044`},{10.5775`,54.3808`},{10.6432`,54.3488`},{10.6965`,54.3305`},{10.7533`,54.3352`},{10.8226`,54.3695`},{10.8617`,54.3872`},{10.9061`,54.3932`},{10.9452`,54.3872`},{11.0038`,54.392`},{11.0447`,54.3872`},{11.0553`,54.3719`},{11.0464`,54.3565`},{11.0216`,54.3376`},{11.0198`,54.3098`},{11.0145`,54.2837`},{11.0536`,54.24`},{11.0589`,54.221`},{11.0323`,54.2057`},{10.9968`,54.1962`},{10.9186`,54.169`},{10.8795`,54.1293`},{10.8635`,54.0962`},{10.8476`,54.082`},{10.8245`,54.082`},{10.8014`,54.0927`},{10.757`,54.1116`},{10.7072`,54.1033`},{10.6894`,54.0844`},{10.6894`,54.0619`},{10.7161`,54.0465`},{10.7747`,54.03`},{10.7818`,54.0181`},{10.7623`,53.959`},{10.7729`,53.9341`},{10.7889`,53.9305`},{10.8138`,53.9513`},{10.8493`,53.9868`},{10.9008`,53.9974`},{10.9648`,54.0116`},{11.0429`,54.04`},{11.1051`,54.0459`},{11.1513`,54.0501`},{11.2011`,54.0477`},{11.2046`,54.0347`},{11.1887`,54.0182`},{11.1887`,54.0016`},{11.1904`,53.9886`},{11.2242`,53.9815`},{11.2331`,53.9732`},{11.2348`,53.9566`},{11.226`,53.9271`},{11.2455`,53.92`},{11.2686`,53.9271`},{11.2864`,53.9424`},{11.3148`,53.9507`},{11.3361`,53.9448`},{11.3628`,53.9211`},{11.3983`,53.907`},{11.448`,53.9081`},{11.4658`,53.9282`},{11.4729`,53.949`},{11.4747`,54.0057`},{11.4854`,54.0329`},{11.5209`,54.0578`},{11.576`,54.0779`},{11.5849`,54.0921`},{11.5582`,54.1004`},{11.4996`,54.1004`},{11.48`,54.1134`},{11.48`,54.1347`},{11.512`,54.1524`},{11.5689`,54.1631`},{11.7074`,54.169`},{11.7909`,54.1773`},{11.8638`,54.1891`},{11.9162`,54.1993`},{12.`,54.2229`},{12.024`,54.2305`},{12.1082`,54.2552`},{12.1813`,54.2874`},{12.2127`,54.3039`},{12.2756`,54.3398`},{12.3329`,54.3802`},{12.3745`,54.4117`},{12.4025`,54.4439`},{12.4407`,54.4798`},{12.4834`,54.5097`},{12.5137`,54.5202`},{12.5542`,54.5224`},{12.5867`,54.5269`},{12.616`,54.5202`},{12.6586`,54.5082`},{12.7047`,54.4865`},{12.7328`,54.4693`},{12.7856`,54.4461`},{12.8215`,54.4334`},{12.8474`,54.4326`},{12.8766`,54.4431`},{12.9114`,54.4566`},{12.9373`,54.4611`},{12.9631`,54.4603`},{12.9912`,54.4454`},{13.0193`,54.4064`},{13.0485`,54.3817`},{13.053`,54.357`},{13.0619`,54.3241`},{13.0867`,54.3069`},{13.1125`,54.2889`},{13.1518`,54.2717`},{13.19`,54.2523`},{13.2316`,54.2425`},{13.2552`,54.2365`},{13.3226`,54.2223`},{13.3563`,54.2118`},{13.3765`,54.2006`},{13.39`,54.1916`},{13.3956`,54.1647`},{13.4102`,54.1362`},{13.4383`,54.1273`},{13.454`,54.1302`},{13.4562`,54.1377`},{13.4619`,54.1542`},{13.4709`,54.1722`},{13.5102`,54.1864`},{13.5517`,54.1886`},{13.6281`,54.1999`},{13.6663`,54.2006`},{13.6877`,54.1871`},{13.6888`,54.1609`},{13.7068`,54.1295`},{13.7304`,54.0996`},{13.7326`,54.0726`},{13.7405`,54.0397`},{13.7585`,54.0097`},{13.7866`,53.985`},{13.8079`,53.9566`},{13.8191`,53.9296`},{13.8169`,53.9057`},{13.8113`,53.8758`},{13.8427`,53.8473`},{13.8731`,53.8353`},{13.9371`,53.8196`},{14.0023`,53.7971`},{14.0506`,53.7889`},{14.0876`,53.7799`},{14.1359`,53.7777`},{14.1966`,53.7784`},{14.2561`,53.7778`},{14.291`,53.6629`},{14.3848`,53.4455`},{14.3963`,53.2957`},{14.3667`,53.1804`},{14.3542`,53.1451`},{14.3199`,53.1193`},{14.2816`,53.0835`},{14.2514`,53.055`},{14.2234`,53.0324`},{14.18`,53.0123`},{14.1399`,52.9787`},{14.1141`,52.9521`},{14.1053`,52.933`},{14.1082`,52.9099`},{14.1178`,52.8844`},{14.1509`,52.8643`},{14.2006`,52.8464`},{14.2573`,52.8257`},{14.3074`,52.8071`},{14.3501`,52.785`},{14.3917`,52.7612`},{14.4278`,52.7322`},{14.458`,52.692`},{14.4985`,52.6611`},{14.5368`,52.6488`},{14.5806`,52.6299`},{14.6196`,52.6064`},{14.6439`,52.5877`},{14.6534`,52.572`},{14.6549`,52.5504`},{14.6431`,52.5273`},{14.6104`,52.4957`},{14.575`,52.4623`},{14.5581`,52.4373`},{14.5537`,52.4073`},{14.5629`,52.3752`},{14.6063`,52.3428`},{14.6475`,52.3148`},{14.6608`,52.2844`},{14.6634`,52.2498`},{14.6766`,52.212`},{14.6906`,52.1776`},{14.7171`,52.1565`},{14.7547`,52.1393`},{14.76`,52.0998`},{14.7509`,52.0687`},{14.7367`,52.0359`},{14.7227`,51.9972`},{14.6929`,51.9657`},{14.6547`,51.9363`},{14.6167`,51.9097`},{14.5921`,51.8769`},{14.5804`,51.8488`},{14.5798`,51.8242`},{14.5969`,51.7968`},{14.6209`,51.7687`},{14.6507`,51.7462`},{14.689`,51.7151`},{14.7217`,51.7015`},{14.7515`,51.6881`},{14.7832`,51.6665`},{14.791`,51.6419`},{14.7904`,51.6276`},{14.7748`,51.5874`},{14.7797`,51.5544`},{14.8102`,51.5228`},{14.8458`,51.4935`},{14.9203`,51.4585`},{14.9596`,51.4358`},{14.9625`,51.4307`},{14.9832`,51.3932`},{14.9877`,51.3461`},{14.9981`,51.3064`},{15.0078`,51.2589`},{15.035`,51.2113`},{15.0457`,51.1718`},{15.0477`,51.1429`},{15.0328`,51.107`},{15.0227`,51.0826`},{14.9935`,51.0502`},{14.956`,51.0156`},{14.9132`,50.975`},{14.8901`,50.9558`},{14.8736`,50.9201`},{14.8827`,50.8873`},{14.9111`,50.8548`},{14.8786`,50.847`},{14.7906`,50.8334`},{14.7476`,50.8334`},{14.707`,50.8515`},{14.6709`,50.8831`},{14.6189`,50.9796`},{14.6008`,51.0067`},{14.5647`,51.0233`},{14.5037`,51.0368`},{14.4314`,51.0413`},{14.3637`,51.0293`},{14.3163`,51.0157`},{14.3004`,50.9961`},{14.3072`,50.9796`},{14.3682`,50.954`},{14.4089`,50.9344`},{14.4224`,50.9133`},{14.4179`,50.8861`},{14.3863`,50.8696`},{14.1785`,50.8153`},{13.7957`,50.7144`},{13.6895`,50.7038`},{13.615`,50.6933`},{13.5653`,50.6812`},{13.5495`,50.6692`},{13.5472`,50.6451`},{13.5269`,50.624`},{13.4862`,50.6089`},{13.4298`,50.6104`},{13.3688`,50.6119`},{13.3033`,50.6059`},{13.2446`,50.5908`},{13.1768`,50.5577`},{13.0707`,50.4944`},{12.8809`,50.4266`},{12.6517`,50.3648`},{12.5162`,50.3196`},{12.4394`,50.2819`},{12.3942`,50.2412`},{12.3536`,50.2036`},{12.3174`,50.1749`},{12.2971`,50.1734`},{12.2858`,50.1885`},{12.279`,50.2171`},{12.2655`,50.2412`},{12.2452`,50.2669`},{12.145`,50.2933`},{12.126`,50.2756`},{12.0978`,50.2493`},{12.1029`,50.2305`},{12.1732`,50.1666`},{12.2678`,50.0711`},{12.3119`,50.0365`},{12.4206`,49.9913`},{12.5363`,49.9133`},{12.5541`,49.8877`},{12.5554`,49.8673`},{12.5452`,49.8519`},{12.5171`,49.8238`},{12.489`,49.7786`},{12.4519`,49.7394`},{12.4442`,49.7232`},{12.4538`,49.7066`},{12.6289`,49.5795`},{12.7593`,49.4354`},{12.8443`,49.3744`},{12.9517`,49.3369`},{12.9977`,49.3233`},{13.0335`,49.2968`},{13.1358`,49.2218`},{13.2188`,49.1698`},{13.539`,48.9672`},{13.7256`,48.853`},{13.8644`,48.7868`},{13.8614`,48.6944`},{13.8628`,48.6672`},{13.8348`,48.5822`},{13.7963`,48.5203`},{13.7371`,48.5424`},{13.6517`,48.5618`},{13.4925`,48.5729`},{13.4592`,48.5472`},{13.4392`,48.5151`},{13.4307`,48.4713`},{13.4307`,48.4207`},{13.4328`,48.38`},{13.4319`,48.343`},{13.4132`,48.3231`},{13.3782`,48.3043`},{13.3423`,48.2912`},{13.295`,48.2847`},{13.2301`,48.2727`},{13.1413`,48.2625`},{13.0411`,48.2332`},{13.0129`,48.2235`},{12.9694`,48.2264`},{12.957`,48.2251`},{12.8372`,48.1682`},{12.782`,48.109`},{12.7694`,48.0881`},{12.7873`,48.0667`},{12.8975`,48.`},{12.9117`,47.9312`},{12.9488`,47.8711`},{12.9408`,47.834`},{12.8799`,47.7969`},{12.8719`,47.758`},{12.917`,47.7421`},{12.9992`,47.7333`},{13.0601`,47.6962`},{13.0761`,47.6697`},{13.0389`,47.6131`},{13.0283`,47.5495`},{13.0058`,47.5159`},{12.9422`,47.5212`},{12.8255`,47.5813`},{12.7884`,47.6431`},{12.7486`,47.6873`},{12.6214`,47.728`},{12.571`,47.7174`},{12.5365`,47.6696`},{12.4994`,47.6449`},{12.4702`,47.6467`},{12.4265`,47.6767`},{12.3496`,47.7156`},{12.2197`,47.7545`},{12.1534`,47.7527`},{12.1189`,47.7315`},{12.1163`,47.6838`},{12.0832`,47.6443`},{12.`,47.5976`},{11.9227`,47.587`},{11.8005`,47.5703`},{11.7267`,47.5385`},{11.3903`,47.4634`},{11.368`,47.4437`},{11.3608`,47.4044`},{11.3286`,47.3936`},{11.1694`,47.3936`},{11.0405`,47.3471`},{10.9842`,47.3525`},{10.8679`,47.4145`},{10.8553`,47.4836`},{10.8213`,47.5075`},{10.6818`,47.5218`},{10.5753`,47.5248`},{10.468`,47.5677`},{10.4143`,47.5677`},{10.3785`,47.5522`},{10.3749`,47.5391`},{10.4375`,47.4091`},{10.4107`,47.371`},{10.2801`,47.2649`},{10.1969`,47.2261`},{10.1557`,47.2249`},{10.145`,47.2344`},{10.17`,47.2833`},{10.1754`,47.3417`},{10.1504`,47.3513`},{10.1271`,47.3525`},{10.0573`,47.337`},{9.99825`,47.3382`},{9.9732`,47.3704`},{9.975`,47.3954`},{10.009`,47.4324`},{10.0054`,47.4502`},{9.941`,47.48`},{9.9079`,47.4985`},{9.90075`,47.5081`},{9.9079`,47.5307`},{9.9043`,47.5403`},{9.86855`,47.545`},{9.7916`,47.545`},{9.68425`,47.5248`},{9.56615`,47.5152`},{9.52885`,47.5176`},{9.47885`,47.5207`},{9.1711`,47.6451`},{9.1389`,47.6567`},{9.13085`,47.6545`},{9.11635`,47.6556`},{9.01655`,47.6835`},{8.98435`,47.6846`},{8.95695`,47.6803`},{8.9441`,47.6728`},{8.93925`,47.661`},{8.8387`,47.6323`},{8.7859`,47.6314`},{8.7609`,47.6342`},{8.6665`,47.6934`},{8.6081`,47.6911`},{8.5596`,47.6685`},{8.5329`,47.6257`},{8.5317`,47.5804`},{8.4553`,47.5384`},{8.4116`,47.5254`},{8.35825`,47.5254`},{8.23455`,47.5691`},{8.11875`,47.5735`},{7.9635`,47.5404`},{7.89375`,47.5327`},{7.69125`,47.5376`},{7.6312`,47.5444`},{7.55965`,47.5703`},{7.53455`,47.5915`},{7.47355`,47.6495`},{7.4596`,47.6976`},{7.46175`,47.7265`},{7.4642`,47.7598`},{7.4768`,47.7931`},{7.48685`,47.8176`},{7.51825`,48.`},{7.5067`,48.0768`},{7.4931`,48.1096`},{7.48805`,48.1232`},{7.4948`,48.1639`},{7.51345`,48.1854`},{7.5593`,48.2182`},{7.56945`,48.2307`},{7.5873`,48.2674`},{7.63985`,48.3223`},{7.6534`,48.3596`},{7.6568`,48.4535`},{7.7044`,48.5299`},{7.73825`,48.5553`},{7.7586`,48.5847`},{7.7705`,48.6486`},{7.79765`,48.6848`},{7.89605`,48.7515`},{7.91045`,48.7759`},{7.92405`,48.7883`},{7.98`,48.8222`},{8.1361`,48.9025`},{8.15135`,48.9139`},{8.16155`,48.9433`},{8.16495`,48.958`},{8.187`,48.9715`},{8.19205`,48.974`},{8.177`,48.9901`},{8.1505`,48.999`},{8.0062`,49.0025`},{7.9413`,49.0087`},{7.844`,49.0299`},{7.7685`,49.0466`},{7.65865`,49.0519`},{7.60435`,49.0643`},{7.5428`,49.0983`},{7.4395`,49.1875`},{7.4011`,49.1919`},{7.35345`,49.1813`},{7.2012`,49.1504`},{7.04695`,49.1521`},{7.02575`,49.1654`},{7.00855`,49.1954`},{6.9847`,49.2157`},{6.941`,49.2281`},{6.88805`,49.2237`},{6.83645`,49.1928`},{6.7729`,49.1813`},{6.73315`,49.1901`},{6.69145`,49.2135`},{6.60805`,49.2753`},{6.57625`,49.3124`},{6.4743`,49.3954`},{6.44255`,49.432`},{6.39885`,49.4603`},{6.2981`,49.4885`},{6.3481`,49.5218`},{6.35655`,49.5274`},{6.40305`,49.5952`},{6.414`,49.6369`},{6.4276`,49.6796`},{6.4237`,49.7094`},{6.43925`,49.7495`},{6.4072`,49.7812`},{6.2752`,49.855`},{6.1179`,49.9599`},{6.08295`,50.0013`},{6.082`,50.0964`},{6.1145`,50.1758`},{6.1286`,50.2103`},{6.1927`,50.2711`},{6.27035`,50.3074`},{6.348`,50.3126`},{6.3713`,50.3281`},{6.3713`,50.341`},{6.34025`,50.363`},{6.3315`,50.3883`},{6.35095`,50.4556`},{6.3548`,50.4763`},{6.33735`,50.4944`},{6.2946`,50.5035`},{6.2286`,50.4983`},{6.17425`,50.5125`},{6.1529`,50.5358`},{6.16065`,50.5565`},{6.23635`,50.607`},{6.248`,50.6277`},{6.23055`,50.6484`},{6.20335`,50.6562`},{6.14705`,50.6342`},{6.1296`,50.6407`},{6.11015`,50.664`},{6.07715`,50.673`},{6.00435`,50.6672`},{5.95385`,50.6802`},{5.90725`,50.7242`}},{{13.9187`,53.886`},{13.8735`,53.8918`},{13.87`,53.9166`},{13.8895`,53.9521`},{13.8912`,53.9709`},{13.8735`,53.9863`},{13.8664`,54.0075`},{13.87`,54.0229`},{13.8966`,54.0323`},{13.9497`,54.0052`},{13.9816`,54.0004`},{14.0117`,54.0134`},{14.017`,54.0347`},{13.9922`,54.0701`},{13.9639`,54.0878`},{13.932`,54.0925`},{13.9178`,54.0784`},{13.9089`,54.0559`},{13.8806`,54.0595`},{13.8434`,54.063`},{13.7796`,54.0677`},{13.769`,54.1032`},{13.7779`,54.1468`},{13.7726`,54.1634`},{13.7655`,54.1811`},{13.7655`,54.2035`},{13.7938`,54.2082`},{13.8381`,54.1976`},{13.8806`,54.1657`},{13.9028`,54.1516`},{13.9807`,54.1315`},{14.0232`,54.1114`},{14.0905`,54.0689`},{14.149`,54.017`},{14.1694`,54.0081`},{14.1972`,53.9506`},{14.2139`,53.9064`},{14.1613`,53.919`},{14.0781`,53.9202`},{14.0125`,53.9013`},{13.9736`,53.8895`},{13.9187`,53.886`}},{{13.1932`,54.5372`},{13.1702`,54.5474`},{13.1371`,54.5508`},{13.1155`,54.5703`},{13.1333`,54.589`},{13.1741`,54.589`},{13.2327`,54.5907`},{13.2594`,54.6017`},{13.29`,54.6102`},{13.3193`,54.5949`},{13.3397`,54.5771`},{13.3563`,54.5491`},{13.3779`,54.5262`},{13.4276`,54.527`},{13.4633`,54.5134`},{13.4901`,54.4846`},{13.5117`,54.426`},{13.5181`,54.3954`},{13.5009`,54.3716`},{13.4487`,54.3623`},{13.4053`,54.3487`},{13.3684`,54.3402`},{13.3582`,54.3309`},{13.3735`,54.3088`},{13.376`,54.2918`},{13.3722`,54.2757`},{13.3518`,54.274`},{13.3238`,54.2765`},{13.3149`,54.2944`},{13.2983`,54.3241`},{13.2907`,54.3419`},{13.2748`,54.3428`},{13.2302`,54.3301`},{13.183`,54.3241`},{13.1321`,54.3377`},{13.1053`,54.37`},{13.0837`,54.4031`},{13.0837`,54.4506`},{13.0989`,54.477`},{13.1015`,54.5041`},{13.1346`,54.5135`},{13.1869`,54.5262`},{13.1932`,54.5372`}},{{13.2174`,54.6926`},{13.2671`,54.7121`},{13.3219`,54.7189`},{13.369`,54.7121`},{13.3996`,54.6943`},{13.4123`,54.6773`},{13.4123`,54.6399`},{13.448`,54.6204`},{13.5245`,54.6196`},{13.5856`,54.6187`},{13.6149`,54.6017`},{13.6149`,54.5678`},{13.5933`,54.5313`},{13.5958`,54.5066`},{13.592`,54.488`},{13.5627`,54.4795`},{13.5398`,54.4795`},{13.5054`,54.5143`},{13.4722`,54.5499`},{13.4021`,54.5848`},{13.3703`,54.6`},{13.3601`,54.6255`},{13.3282`,54.6399`},{13.29`,54.6425`},{13.2709`,54.6391`},{13.2314`,54.6365`},{13.2212`,54.6544`},{13.1932`,54.6527`},{13.1753`,54.6298`},{13.1397`,54.6298`},{13.1346`,54.6467`},{13.1613`,54.6688`},{13.2174`,54.6926`}}}];
ukPolygon=Polygon[{{{-5.80035`,55.3191`},{-5.83335`,55.3252`},{-5.8559`,55.3505`},{-5.86665`,55.3898`},{-5.85945`,55.4124`},{-5.78775`,55.4745`},{-5.7826`,55.4902`},{-5.7903`,55.5343`},{-5.77185`,55.6258`},{-5.715`,55.7109`},{-5.66785`,55.7546`},{-5.55105`,55.8318`},{-5.5316`,55.8557`},{-5.5326`,55.8728`},{-5.5439`,55.879`},{-5.5562`,55.8776`},{-5.5818`,55.8598`},{-5.64225`,55.8264`},{-5.68325`,55.8072`},{-5.7017`,55.8045`},{-5.715`,55.8106`},{-5.75395`,55.8455`},{-5.75445`,55.8602`},{-5.7268`,55.8916`},{-5.69195`,55.9135`},{-5.66635`,55.9374`},{-5.66735`,55.9442`},{-5.67965`,55.9462`},{-5.71245`,55.9421`},{-5.7309`,55.949`},{-5.73395`,55.9606`},{-5.72575`,55.9859`},{-5.72475`,55.9961`},{-5.74115`,56.0255`},{-5.735`,56.0405`},{-5.70425`,56.0549`},{-5.67865`,56.0555`},{-5.61`,56.0275`},{-5.5946`,56.0296`},{-5.58845`,56.0371`},{-5.59085`,56.0589`},{-5.6104`,56.0781`},{-5.60465`,56.1004`},{-5.5862`,56.1219`},{-5.5908`,56.1318`},{-5.6104`,56.1403`},{-5.62885`,56.1387`},{-5.65535`,56.128`},{-5.67265`,56.1211`},{-5.6865`,56.1272`},{-5.69455`,56.1403`},{-5.6911`,56.1556`},{-5.6196`,56.207`},{-5.5735`,56.2408`},{-5.5735`,56.2492`},{-5.59195`,56.2569`},{-5.61615`,56.2546`},{-5.6254`,56.2684`},{-5.62885`,56.2907`},{-5.63`,56.2983`},{-5.65305`,56.3037`},{-5.7003`,56.3129`},{-5.71645`,56.3275`},{-5.70955`,56.3475`},{-5.6865`,56.3613`},{-5.645`,56.3689`},{-5.56315`,56.3797`},{-5.5516`,56.3851`},{-5.55275`,56.3904`},{-5.5885`,56.4081`},{-5.60005`,56.4211`},{-5.59315`,56.4334`},{-5.577`,56.4411`},{-5.4617`,56.4741`},{-5.4444`,56.4748`},{-5.33605`,56.4564`},{-5.29455`,56.4587`},{-5.2565`,56.4695`},{-5.2311`,56.4848`},{-5.1239`,56.5846`},{-5.12045`,56.5999`},{-5.132`,56.6091`},{-5.1481`,56.6099`},{-5.16305`,56.6068`},{-5.18845`,56.5853`},{-5.3106`,56.4886`},{-5.3394`,56.4848`},{-5.36825`,56.4917`},{-5.42355`,56.5101`},{-5.4397`,56.5132`},{-5.45585`,56.5094`},{-5.4766`,56.5078`},{-5.51235`,56.5201`},{-5.52155`,56.5324`},{-5.51695`,56.5539`},{-5.49735`,56.5692`},{-5.47545`,56.5754`},{-5.3498`,56.5746`},{-5.3256`,56.5815`},{-5.31635`,56.593`},{-5.3233`,56.6053`},{-5.3475`,56.6114`},{-5.4201`,56.6068`},{-5.43855`,56.6122`},{-5.4466`,56.626`},{-5.43855`,56.6391`},{-5.427`,56.6483`},{-5.3555`,56.6943`},{-5.3371`,56.7028`},{-5.3048`,56.7051`},{-5.2103`,56.7051`},{-5.13765`,56.7196`},{-5.10655`,56.7411`},{-5.0858`,56.7611`},{-5.08925`,56.7711`},{-5.10655`,56.7795`},{-5.12845`,56.7757`},{-5.2414`,56.7419`},{-5.2702`,56.7381`},{-5.2898`,56.7427`},{-5.2921`,56.7565`},{-5.28175`,56.7688`},{-5.61555`,56.6203`},{-5.69905`,56.5854`},{-5.76425`,56.5836`},{-5.79275`,56.5972`},{-5.8593`,56.6162`},{-5.97605`,56.6343`},{-6.0324`,56.6592`},{-6.0704`,56.6764`},{-6.0799`,56.6909`},{-6.0731`,56.7017`},{-6.0446`,56.7063`},{-6.00115`,56.7017`},{-5.97805`,56.6909`},{-5.9509`,56.6909`},{-5.92645`,56.6963`},{-5.91965`,56.7099`},{-5.8925`,56.7298`},{-5.8436`,56.7371`},{-5.7771`,56.728`},{-5.74315`,56.7325`},{-5.72685`,56.7452`},{-5.72685`,56.7561`},{-5.7662`,56.7724`},{-5.8708`,56.7887`},{-5.94545`,56.7832`},{-5.993`,56.7624`},{-6.0582`,56.7334`},{-6.16275`,56.7072`},{-6.1967`,56.709`},{-6.23065`,56.7144`},{-6.26595`,56.7325`},{-6.2741`,56.7588`},{-6.25985`,56.7764`},{-6.23`,56.7918`},{-6.1064`,56.8389`},{-6.04125`,56.8371`},{-6.04125`,56.8371`},{-5.99235`,56.8335`},{-5.95705`,56.838`},{-5.9455`,56.8439`},{-5.9251`,56.8719`},{-5.90065`,56.8846`},{-5.8545`,56.8909`},{-5.82055`,56.9036`},{-5.80425`,56.9226`},{-5.8083`,56.9299`},{-5.8287`,56.9317`},{-5.8409`,56.938`},{-5.8382`,56.9543`},{-5.845`,56.9624`},{-5.86535`,56.9615`},{-5.8871`,56.948`},{-5.9061`,56.9416`},{-5.9197`,56.9425`},{-5.93055`,56.9516`},{-5.9251`,57.0294`},{-5.91015`,57.0439`},{-5.89315`,57.0507`},{-5.87005`,57.0507`},{-5.83475`,57.0426`},{-5.78995`,57.0227`},{-5.7723`,57.0181`},{-5.7614`,57.0236`},{-5.76005`,57.029`},{-5.77365`,57.0399`},{-5.8266`,57.0752`},{-5.8402`,57.0987`},{-5.83475`,57.1286`},{-5.78585`,57.1612`},{-5.7533`,57.1684`},{-5.66095`,57.1422`},{-5.6202`,57.1313`},{-5.56995`,57.1286`},{-5.5584`,57.1308`},{-5.54345`,57.1444`},{-5.54345`,57.1535`},{-5.5611`,57.1616`},{-5.6385`,57.177`},{-5.71865`,57.2042`},{-5.7458`,57.2304`},{-5.74985`,57.2458`},{-5.73355`,57.263`},{-5.70235`,57.2829`},{-5.66975`,57.2875`},{-5.6195`,57.2875`},{-5.56925`,57.2666`},{-5.5421`,57.263`},{-5.5258`,57.2693`},{-5.50815`,57.2811`},{-5.50815`,57.2902`},{-5.5475`,57.3164`},{-5.56515`,57.3173`},{-5.6222`,57.3173`},{-5.69555`,57.3282`},{-5.73695`,57.3386`},{-5.7573`,57.3522`},{-5.76005`,57.3703`},{-5.7424`,57.3875`},{-5.67585`,57.402`},{-5.61065`,57.4174`},{-5.5699`,57.4319`},{-5.5509`,57.4473`},{-5.5482`,57.4617`},{-5.5699`,57.4663`},{-5.59705`,57.4617`},{-5.62965`,57.4473`},{-5.6636`,57.4391`},{-5.6799`,57.4418`},{-5.69215`,57.4527`},{-5.66905`,57.4681`},{-5.6772`,57.4744`},{-5.69485`,57.4735`},{-5.75325`,57.4482`},{-5.81165`,57.4273`},{-5.82655`,57.431`},{-5.84695`,57.4445`},{-5.89175`,57.5378`},{-5.9182`,57.6143`},{-5.91275`,57.627`},{-5.8924`,57.6333`},{-5.85845`,57.6342`},{-5.8286`,57.6215`},{-5.7335`,57.588`},{-5.70095`,57.5826`},{-5.6765`,57.589`},{-5.66835`,57.6016`},{-5.667`,57.6125`},{-5.6751`,57.6234`},{-5.7213`,57.6279`},{-5.7566`,57.636`},{-5.78785`,57.6641`},{-5.8123`,57.6777`},{-5.853`,57.6876`},{-5.88155`,57.703`},{-5.90325`,57.7229`},{-5.9114`,57.7501`},{-5.90665`,57.7551`},{-5.88495`,57.7659`},{-5.85505`,57.7687`},{-5.8469`,57.7759`},{-5.84555`,57.784`},{-5.85505`,57.7931`},{-5.9094`,57.8311`},{-5.93655`,57.8592`},{-5.93925`,57.8854`},{-5.93245`,57.909`},{-5.9162`,57.9226`},{-5.8958`,57.9289`},{-5.85235`,57.928`},{-5.82925`,57.9189`},{-5.7994`,57.8954`},{-5.7668`,57.8538`},{-5.72335`,57.8203`},{-5.67855`,57.8013`},{-5.6663`,57.8031`},{-5.65815`,57.8094`},{-5.6541`,57.8203`},{-5.6663`,57.8501`},{-5.70705`,57.9117`},{-5.71385`,57.9389`},{-5.70705`,57.9633`},{-5.68965`,57.9769`},{-5.6598`,57.9778`},{-5.63125`,57.9624`},{-5.581`,57.928`},{-5.55655`,57.9271`},{-5.4798`,57.9275`},{-5.4676`,57.9194`},{-5.4187`,57.8841`},{-5.40375`,57.8777`},{-5.3603`,57.8768`},{-5.35485`,57.8868`},{-5.37115`,57.9076`},{-5.41595`,57.9339`},{-5.41325`,57.9429`},{-5.3983`,57.9583`},{-5.37795`,57.9565`},{-5.34535`,57.9357`},{-5.32365`,57.9302`},{-5.26525`,57.932`},{-5.25165`,57.9293`},{-5.21155`,57.9062`},{-5.1749`,57.8782`},{-5.1559`,57.8764`},{-5.14775`,57.8836`},{-5.14775`,57.8936`},{-5.15315`,57.9126`},{-5.1844`,57.9352`},{-5.2428`,57.9597`},{-5.255`,57.9669`},{-5.25775`,57.9941`},{-5.26725`,58.0058`},{-5.28625`,58.0104`},{-5.36775`,58.0149`},{-5.3922`,58.0221`},{-5.44785`,58.0746`},{-5.4587`,58.0946`},{-5.4981`,58.1281`},{-5.5029`,58.1421`},{-5.50015`,58.1548`},{-5.48115`,58.1593`},{-5.4635`,58.1566`},{-5.4241`,58.1312`},{-5.3983`,58.1149`},{-5.37385`,58.114`},{-5.35485`,58.1267`},{-5.34535`,58.1385`},{-5.3562`,58.191`},{-5.37115`,58.22`},{-5.4187`,58.2643`},{-5.4377`,58.2851`},{-5.44175`,58.306`},{-5.42955`,58.3141`},{-5.41325`,58.3132`},{-5.3888`,58.3032`},{-5.3657`,58.3051`},{-5.34265`,58.315`},{-5.31275`,58.334`},{-5.29845`,58.3381`},{-5.2618`,58.3363`},{-5.1939`,58.2956`},{-5.12465`,58.2675`},{-5.09205`,58.2639`},{-5.07985`,58.2711`},{-5.0717`,58.2829`},{-5.07845`,58.2956`},{-5.1002`,58.3064`},{-5.1681`,58.3263`},{-5.19795`,58.3426`},{-5.21565`,58.3743`},{-5.2102`,58.3933`},{-5.19255`,58.4277`},{-5.19255`,58.4685`},{-5.18985`,58.4848`},{-5.17895`,58.4984`},{-5.16945`,58.5056`},{-5.12735`,58.5056`},{-5.1124`,58.5128`},{-5.10565`,58.5318`},{-5.109`,58.5486`},{-5.1294`,58.5694`},{-5.1294`,58.621`},{-5.1158`,58.6445`},{-5.07915`,58.6617`},{-4.99765`,58.6599`},{-4.95015`,58.65`},{-4.92295`,58.6382`},{-4.9216`,58.6246`},{-4.9325`,58.612`},{-4.9284`,58.5984`},{-4.9121`,58.5938`},{-4.8931`,58.5938`},{-4.8768`,58.6074`},{-4.8632`,58.6355`},{-4.84555`,58.6445`},{-4.82925`,58.6436`},{-4.8157`,58.6346`},{-4.79395`,58.6255`},{-4.7498`,58.6242`},{-4.7308`,58.6206`},{-4.72125`,58.6133`},{-4.724`,58.597`},{-4.7525`,58.5771`},{-4.78915`,58.5554`},{-4.80545`,58.5273`},{-4.7946`,58.5237`},{-4.77965`,58.5237`},{-4.75115`,58.54`},{-4.71855`,58.5554`},{-4.6914`,58.5599`},{-4.66425`,58.568`},{-4.64385`,58.5825`},{-4.633`,58.607`},{-4.62215`,58.6215`},{-4.59225`,58.6341`},{-4.5719`,58.6405`},{-4.5556`,58.6341`},{-4.51895`,58.6088`},{-4.5135`,58.5925`},{-4.52845`,58.5617`},{-4.5583`,58.5228`},{-4.57325`,58.5083`},{-4.57325`,58.4983`},{-4.5651`,58.4929`},{-4.5488`,58.4929`},{-4.47685`,58.5626`},{-4.4422`,58.5893`},{-4.41095`,58.5993`},{-4.33355`,58.602`},{-4.3064`,58.6092`},{-4.2765`,58.6201`},{-4.229`,58.6201`},{-4.21815`,58.6246`},{-4.1665`,58.6626`},{-4.15225`,58.6703`},{-4.12375`,58.6712`},{-4.102`,58.6649`},{-4.0613`,58.6386`},{-4.04635`,58.6359`},{-3.9703`,58.635`},{-3.8766`,58.6432`},{-3.8019`,58.654`},{-3.75235`,58.6699`},{-3.71975`,58.6735`},{-3.6505`,58.6762`},{-3.63015`,58.6708`},{-3.5799`,58.6409`},{-3.5541`,58.6264`},{-3.50115`,58.6291`},{-3.48145`,58.6341`},{-3.46105`,58.6649`},{-3.4502`,58.6776`},{-3.42575`,58.6866`},{-3.3144`,58.6767`},{-3.1392`,58.6685`},{-3.12495`,58.6662`},{-3.1141`,58.6563`},{-3.1209`,58.6373`},{-3.15075`,58.6164`},{-3.20375`,58.5884`},{-3.20915`,58.5766`},{-3.20375`,58.5594`},{-3.18335`,58.544`},{-3.1263`,58.515`},{-3.1236`,58.4978`},{-3.14125`,58.4779`},{-3.3151`,58.3919`},{-3.381`,58.3661`},{-3.55755`,58.2792`},{-3.6811`,58.1977`},{-3.8271`,58.1384`},{-3.8855`,58.1067`},{-3.9602`,58.047`},{-3.98055`,58.0398`},{-4.0586`,58.0112`},{-4.0749`,57.9977`},{-4.0749`,57.9796`},{-4.0532`,57.9578`},{-4.0518`,57.9334`},{-4.0749`,57.9153`},{-4.1496`,57.9053`},{-4.20525`,57.9026`},{-4.2202`,57.8945`},{-4.2202`,57.8872`},{-4.21615`,57.8754`},{-4.19035`,57.8709`},{-4.0464`,57.8727`},{-3.9622`,57.8818`},{-3.9011`,57.9053`},{-3.8848`,57.9135`},{-3.8753`,57.9135`},{-3.86035`,57.908`},{-3.85765`,57.899`},{-3.878`,57.8782`},{-3.9853`,57.8139`},{-4.10685`,57.7646`},{-4.20195`,57.7003`},{-4.3187`,57.5998`},{-4.40495`,57.5649`},{-4.49325`,57.5514`},{-4.51225`,57.5459`},{-4.51905`,57.5333`},{-4.5`,57.5224`},{-4.2833`,57.507`},{-4.2349`,57.527`},{-4.19915`,57.54`},{-4.1807`,57.5531`},{-4.1565`,57.5738`},{-4.12305`,57.6076`},{-4.0954`,57.6206`},{-4.07465`,57.6229`},{-3.9974`,57.6152`},{-3.96745`,57.6221`},{-3.87985`,57.6536`},{-3.80375`,57.6759`},{-3.7461`,57.6927`},{-3.7265`,57.692`},{-3.7138`,57.6812`},{-3.685`,57.6659`},{-3.66425`,57.6689`},{-3.63775`,57.6758`},{-3.5305`,57.7357`},{-3.4521`,57.7802`},{-3.4175`,57.7871`},{-3.323`,57.7879`},{-3.29305`,57.7779`},{-3.2412`,57.7403`},{-3.1962`,57.7226`},{-3.1386`,57.7127`},{-3.0936`,57.715`},{-3.03945`,57.7204`},{-2.9772`,57.748`},{-2.91265`,57.7672`},{-2.8492`,57.7695`},{-2.7593`,57.7572`},{-2.689`,57.7395`},{-2.6417`,57.7035`},{-2.60945`,57.6927`},{-2.5806`,57.6943`},{-2.5207`,57.7088`},{-2.43535`,57.7465`},{-2.38005`,57.7618`},{-2.3524`,57.7633`},{-2.31665`,57.7518`},{-2.2878`,57.7311`},{-2.25785`,57.7227`},{-2.22095`,57.7227`},{-2.1903`,57.7314`},{-2.13595`,57.7653`},{-2.0903`,57.7581`},{-2.0846`,57.7572`},{-2.03155`,57.7434`},{-1.9728`,57.7104`},{-1.88745`,57.6444`},{-1.85515`,57.5907`},{-1.854`,57.54`},{-1.8794`,57.4925`},{-1.93475`,57.4456`},{-1.9866`,57.4165`},{-2.01775`,57.3958`},{-2.04885`,57.3697`},{-2.0777`,57.3313`},{-2.095`,57.3029`},{-2.1019`,57.2438`},{-2.12495`,57.2001`},{-2.1307`,57.1855`},{-2.1457`,57.1732`},{-2.16415`,57.1594`},{-2.2045`,57.121`},{-2.2264`,57.0965`},{-2.24135`,57.0734`},{-2.2713`,56.9875`},{-2.3036`,56.913`},{-2.3393`,56.857`},{-2.3785`,56.8148`},{-2.435`,56.7795`},{-2.4696`,56.7626`},{-2.50645`,56.7511`},{-2.57335`,56.7112`},{-2.58025`,56.7043`},{-2.58715`,56.6836`},{-2.61135`,56.6383`},{-2.64365`,56.6053`},{-2.7209`,56.5424`},{-2.7451`,56.5224`},{-2.7601`,56.5155`},{-2.84195`,56.5155`},{-2.93995`,56.5193`},{-3.01715`,56.5124`},{-3.061`,56.5063`},{-3.0875`,56.4909`},{-3.1382`,56.4794`},{-3.24655`,56.4664`},{-3.32265`,56.4587`},{-3.35145`,56.4441`},{-3.36415`,56.4357`},{-3.3538`,56.4242`},{-3.3238`,56.4165`},{-3.24885`,56.4211`},{-3.1739`,56.4249`},{-3.0644`,56.451`},{-2.9895`,56.4717`},{-2.9007`,56.4878`},{-2.8696`,56.484`},{-2.83615`,56.4779`},{-2.8304`,56.4648`},{-2.83385`,56.4541`},{-2.8592`,56.4349`},{-2.8811`,56.4195`},{-2.8811`,56.4142`},{-2.8673`,56.4103`},{-2.82925`,56.4027`},{-2.75775`,56.3942`},{-2.71625`,56.3766`},{-2.69085`,56.3535`},{-2.6874`,56.3152`},{-2.6978`,56.296`},{-2.73235`,56.2668`},{-2.7762`,56.2507`},{-2.81885`,56.2445`},{-2.88575`,56.2538`},{-2.9526`,56.2614`},{-3.00905`,56.2653`},{-3.07245`,56.2507`},{-3.11165`,56.2238`},{-3.16925`,56.1425`},{-3.19925`,56.101`},{-3.24535`,56.0703`},{-3.2995`,56.0596`},{-3.35025`,56.0558`},{-3.386`,56.0573`},{-3.469`,56.0734`},{-3.5439`,56.0918`},{-3.5762`,56.0941`},{-3.6154`,56.0895`},{-3.6719`,56.0849`},{-3.71455`,56.0972`},{-3.76645`,56.121`},{-3.80795`,56.1317`},{-3.8264`,56.1271`},{-3.8414`,56.1171`},{-3.84485`,56.1026`},{-3.8391`,56.0719`},{-3.80335`,56.0412`},{-3.76415`,56.0258`},{-3.70535`,56.0074`},{-3.65695`,56.0019`},{-3.44015`,56.0031`},{-3.31085`,56.0157`},{-3.2028`,56.0013`},{-3.09905`,55.9997`},{-3.03795`,56.012`},{-2.97105`,56.0419`},{-2.9042`,56.065`},{-2.85695`,56.0864`},{-2.8016`,56.0995`},{-2.72435`,56.1064`},{-2.684`,56.1064`},{-2.63555`,56.0918`},{-2.59985`,56.0673`},{-2.51455`,56.0013`},{-2.4915`,55.9905`},{-2.4281`,55.9882`},{-2.2702`,55.9836`},{-2.163`,55.9598`},{-2.10305`,55.9268`},{-2.07535`,55.8992`},{-2.0719`,55.8747`},{-2.07675`,55.8425`},{-2.0823`,55.8186`},{-2.08`,55.8048`},{-2.05005`,55.7833`},{-1.97975`,55.7388`},{-1.97515`,55.7258`},{-1.97515`,55.7105`},{-1.97515`,55.6867`},{-1.96245`,55.6736`},{-1.9463`,55.6675`},{-1.92905`,55.6667`},{-1.90715`,55.6775`},{-1.8933`,55.6782`},{-1.88525`,55.6682`},{-1.88405`,55.6337`},{-1.8783`,55.6253`},{-1.8633`,55.626`},{-1.8449`,55.6329`},{-1.808`,55.6613`},{-1.79185`,55.6659`},{-1.78035`,55.6567`},{-1.7734`,55.6421`},{-1.76995`,55.6222`},{-1.755`,55.5946`},{-1.73885`,55.57`},{-1.6904`,55.5247`},{-1.67425`,55.5086`},{-1.66965`,55.491`},{-1.6662`,55.4273`},{-1.66275`,55.4027`},{-1.6547`,55.3896`},{-1.6282`,55.372`},{-1.6201`,55.3612`},{-1.6201`,55.3444`},{-1.62705`,55.3068`},{-1.6201`,55.2914`},{-1.6028`,55.2768`},{-1.5521`,55.2339`},{-1.52785`,55.207`},{-1.51865`,55.1778`},{-1.51865`,55.1633`},{-1.529`,55.1402`},{-1.5382`,55.1088`},{-1.53705`,55.098`},{-1.51975`,55.0842`},{-1.47135`,55.0481`},{-1.4425`,55.0098`},{-1.4056`,54.9576`},{-1.3941`,54.9238`},{-1.39295`,54.8847`},{-1.3895`,54.8356`},{-1.3722`,54.8079`},{-1.3434`,54.7826`},{-1.2788`,54.7458`},{-1.24305`,54.7158`},{-1.23155`,54.6882`},{-1.2327`,54.656`},{-1.2396`,54.6483`},{-1.25345`,54.6406`},{-1.2546`,54.6322`},{-1.24305`,54.6237`},{-1.22465`,54.6161`},{-1.20505`,54.6153`},{-1.1912`,54.6199`},{-1.18775`,54.6322`},{-1.17505`,54.6414`},{-1.14395`,54.6422`},{-1.07705`,54.6253`},{-1.01485`,54.6015`},{-0.96525`,54.5923`},{-0.91225`,54.5907`},{-0.80045`,54.5815`},{-0.73705`,54.5654`},{-0.6275`,54.5194`},{-0.5491`,54.4695`},{-0.4753`,54.425`},{-0.44765`,54.4043`},{-0.4361`,54.3828`},{-0.4292`,54.3475`},{-0.405`,54.3229`},{-0.38425`,54.3129`},{-0.35545`,54.3068`},{-0.3266`,54.293`},{-0.31625`,54.2746`},{-0.3174`,54.2462`},{-0.3151`,54.2377`},{-0.24365`,54.184`},{-0.231`,54.1778`},{-0.1595`,54.1656`},{-0.13415`,54.1564`},{-0.12955`,54.141`},{-0.13185`,54.1264`},{-0.1457`,54.1134`},{-0.1964`,54.0896`},{-0.21485`,54.0773`},{-0.2229`,54.0612`},{-0.2275`,54.0351`},{-0.2286`,54.0188`},{-0.22405`,53.9914`},{-0.20905`,53.9683`},{-0.16875`,53.9292`},{-0.06265`,53.8348`},{-0.02465`,53.7888`},{-0.0085`,53.7696`},{0.04225`,53.7274`},{0.08145`,53.6882`},{0.11255`,53.646`},{0.11485`,53.636`},{0.1091`,53.6222`},{0.0895`,53.6153`},{0.06415`,53.6146`},{0.03645`,53.6238`},{-0.0385`,53.6568`},{-0.0627`,53.6606`},{-0.12265`,53.6529`},{-0.15265`,53.6514`},{-0.19415`,53.6706`},{-0.27945`,53.7166`},{-0.3083`,53.7274`},{-0.3567`,53.7312`},{-0.4074`,53.7335`},{-0.5849`,53.7289`},{-0.6506`,53.7266`},{-0.6506`,53.7205`},{-0.63105`,53.7182`},{-0.5492`,53.7136`},{-0.41205`,53.7143`},{-0.3636`,53.7113`},{-0.30595`,53.6921`},{-0.2656`,53.6683`},{-0.246`,53.6483`},{-0.2114`,53.6107`},{-0.1699`,53.5954`},{-0.11345`,53.5885`},{-0.03965`,53.5516`},{0.116`,53.4872`},{0.20245`,53.4319`},{0.2232`,53.4027`},{0.26815`,53.3636`},{0.27395`,53.3268`},{0.29125`,53.2707`},{0.2901`,53.2331`},{0.2901`,53.171`},{0.2751`,53.1165`},{0.2509`,53.0927`},{0.23935`,53.085`},{0.2209`,53.0819`},{0.1921`,53.0789`},{0.1633`,53.0743`},{0.1391`,53.0681`},{0.1218`,53.0535`},{0.09185`,53.0251`},{0.0423`,52.9937`},{0.0008`,52.9622`},{-0.00155`,52.9484`},{0.0111`,52.9384`},{0.0676`,52.9262`},{0.0872`,52.92`},{0.13905`,52.8817`},{0.2048`,52.8295`},{0.22095`,52.8203`},{0.2786`,52.8134`},{0.3224`,52.8249`},{0.3639`,52.8494`},{0.39275`,52.884`},{0.4135`,52.9269`},{0.43195`,52.9645`},{0.4677`,53.0006`},{0.4815`,53.0121`},{0.51725`,53.0229`},{0.5472`,53.0075`},{0.5622`,52.9814`},{0.57835`,52.9791`},{0.5968`,52.9922`},{0.59795`,53.0044`},{0.59795`,53.0159`},{0.61175`,53.0351`},{0.62905`,53.0382`},{0.64405`,53.0274`},{0.65555`,53.0113`},{0.67055`,53.0029`},{0.69705`,53.0029`},{0.7155`,53.0037`},{0.74205`,53.0198`},{0.7674`,53.0275`},{0.802`,53.0206`},{0.8239`,53.0113`},{1.07635`,52.9968`},{1.18355`,52.9829`},{1.35185`,52.9423`},{1.49015`,52.8855`},{1.59965`,52.8034`},{1.68845`,52.7151`},{1.7057`,52.6829`},{1.70915`,52.6522`},{1.7034`,52.5854`},{1.66075`,52.4757`},{1.62895`,52.4305`},{1.58925`,52.3451`},{1.56245`,52.2536`},{1.56735`,52.2086`},{1.55925`,52.1956`},{1.51315`,52.168`},{1.5039`,52.161`},{1.49585`,52.1419`},{1.48775`,52.115`},{1.4567`,52.0928`},{1.40485`,52.0444`},{1.35875`,52.0084`},{1.3518`,51.9922`},{1.3449`,51.9608`},{1.32645`,51.9485`},{1.2988`,51.9485`},{1.27225`,51.9408`},{1.2492`,51.9255`},{1.2158`,51.9178`},{1.19505`,51.9101`},{1.1904`,51.8948`},{1.19735`,51.8848`},{1.21465`,51.8817`},{1.23075`,51.8856`},{1.2665`,51.8932`},{1.28265`,51.8856`},{1.28265`,51.8779`},{1.2619`,51.8633`},{1.172`,51.8165`},{1.09135`,51.7812`},{1.0475`,51.7797`},{1.0164`,51.7904`},{1.0072`,51.8042`},{1.0095`,51.8165`},{1.00835`,51.8242`},{0.98875`,51.8349`},{0.9726`,51.8349`},{0.9523`,51.8284`},{0.90645`,51.8112`},{0.88405`,51.7763`},{0.8781`,51.7651`},{0.8493`,51.7551`},{0.8193`,51.7498`},{0.74785`,51.7521`},{0.7248`,51.7421`},{0.7144`,51.7267`},{0.7098`,51.7083`},{0.7225`,51.6968`},{0.7375`,51.6945`},{0.7744`,51.7144`},{0.78825`,51.7198`},{0.8032`,51.7191`},{0.81015`,51.7121`},{0.8067`,51.6953`},{0.81015`,51.6899`},{0.82165`,51.6899`},{0.85165`,51.7114`},{0.88045`,51.7329`},{0.90235`,51.7428`},{0.92655`,51.7382`},{0.9427`,51.7206`},{0.9508`,51.6983`},{0.94505`,51.6891`},{0.9266`,51.6807`},{0.90125`,51.6699`},{0.86665`,51.6469`},{0.8655`,51.6408`},{0.86895`,51.6385`},{0.8978`,51.6431`},{0.92085`,51.6492`},{0.93355`,51.6431`},{0.9289`,51.6323`},{0.9197`,51.6162`},{0.9001`,51.6039`},{0.80785`,51.5732`},{0.7433`,51.5609`},{0.7214`,51.5517`},{0.70065`,51.5471`},{0.6672`,51.5471`},{0.63725`,51.5479`},{0.62455`,51.5433`},{0.6211`,51.5356`},{0.61995`,51.5249`},{0.6073`,51.5157`},{0.59115`,51.5149`},{0.5335`,51.5172`},{0.4851`,51.5118`},{0.40785`,51.4942`},{0.3952`,51.4873`},{0.39635`,51.4735`},{0.4102`,51.4673`},{0.4367`,51.4666`},{0.50815`,51.4804`},{0.6361`,51.4865`},{0.6707`,51.4842`},{0.6926`,51.4704`},{0.6972`,51.4597`},{0.688`,51.4458`},{0.6638`,51.432`},{0.60615`,51.4198`},{0.54965`,51.4128`},{0.537`,51.4052`},{0.5439`,51.3998`},{0.58195`,51.3944`},{0.61765`,51.396`},{0.7064`,51.3906`},{0.75135`,51.376`},{0.8655`,51.3614`},{0.94505`,51.3599`},{0.9681`,51.3576`},{1.0292`,51.3699`},{1.0638`,51.3714`},{1.1076`,51.3607`},{1.14795`,51.3514`},{1.186`,51.3514`},{1.209`,51.3593`},{1.2542`,51.3683`},{1.309`,51.3874`},{1.35095`,51.3921`},{1.39015`,51.3814`},{1.4017`,51.3629`},{1.3971`,51.3491`},{1.3752`,51.3184`},{1.35785`,51.2854`},{1.3648`,51.2647`},{1.3798`,51.2494`},{1.38785`,51.2302`},{1.3867`,51.214`},{1.36595`,51.1903`},{1.33135`,51.1695`},{1.3129`,51.1442`},{1.30485`,51.122`},{1.2887`,51.1135`},{1.26565`,51.1074`},{1.2334`,51.1035`},{1.1596`,51.0989`},{1.10545`,51.0797`},{1.0374`,51.0514`},{0.9775`,51.0291`},{0.95905`,51.0137`},{0.95675`,50.9884`},{0.97175`,50.9439`},{0.96365`,50.9286`},{0.93025`,50.9124`},{0.87375`,50.9071`},{0.7804`,50.9071`},{0.65935`,50.9048`},{0.5637`,50.8979`},{0.4772`,50.884`},{0.42535`,50.8649`},{0.38845`,50.8464`},{0.34005`,50.8035`},{0.2928`,50.7774`},{0.2271`,50.752`},{0.1925`,50.7436`},{0.1591`,50.7444`},{0.09335`,50.7582`},{-0.0323`,50.7935`},{-0.15915`,50.7988`},{-0.20295`,50.7927`},{-0.3148`,50.7658`},{-0.3701`,50.7574`},{-0.43695`,50.7605`},{-0.54415`,50.7658`},{-0.5764`,50.762`},{-0.6928`,50.7213`},{-0.8461`,50.6584`},{-0.898`,50.6293`},{-0.91645`,50.6246`},{-0.96255`,50.6339`},{-0.99715`,50.6477`},{-1.04785`,50.6761`},{-1.0686`,50.6983`},{-1.0582`,50.7121`},{-1.0167`,50.7267`},{-0.97635`,50.7359`},{-0.9579`,50.7421`},{-0.9429`,50.7582`},{-0.9406`,50.7873`},{-0.94755`,50.8104`},{-0.97635`,50.8296`},{-1.0086`,50.8395`},{-1.0328`,50.8365`},{-1.05355`,50.8188`},{-1.07545`,50.7935`},{-1.1273`,50.7758`},{-1.1688`,50.7843`},{-1.2126`,50.8012`},{-1.30715`,50.8656`},{-1.3786`,50.8909`},{-1.4247`,50.8986`},{-1.4616`,50.8956`},{-1.4593`,50.8909`},{-1.427`,50.8748`},{-1.3221`,50.8273`},{-1.30595`,50.8142`},{-1.31175`,50.8019`},{-1.329`,50.7881`},{-1.41435`,50.7336`},{-1.5492`,50.6507`},{-1.5976`,50.6346`},{-1.661`,50.6346`},{-1.8604`,50.6377`},{-1.8892`,50.6431`},{-1.9503`,50.6676`},{-2.01945`,50.7037`},{-2.0575`,50.7175`},{-2.0771`,50.7167`},{-2.099`,50.7083`},{-2.1059`,50.6914`},{-2.10595`,50.6845`},{-2.0633`,50.6607`},{-2.01605`,50.6292`},{-2.01375`,50.6208`},{-2.0241`,50.5916`},{-2.0437`,50.5732`},{-2.0737`,50.5602`},{-2.1336`,50.554`},{-2.22005`,50.5563`},{-2.2823`,50.5663`},{-2.39415`,50.597`},{-2.43565`,50.5978`},{-2.46215`,50.5863`},{-2.4633`,50.574`},{-2.45525`,50.5533`},{-2.446`,50.5394`},{-2.4437`,50.5256`},{-2.45755`,50.5172`},{-2.47485`,50.5203`},{-2.4979`,50.531`},{-2.5613`,50.5855`},{-2.59475`,50.6016`},{-2.6766`,50.6177`},{-2.7377`,50.6392`},{-2.79995`,50.6622`},{-2.87605`,50.6814`},{-2.93715`,50.6822`},{-3.03745`,50.6676`},{-3.132`,50.6392`},{-3.1781`,50.6308`},{-3.25535`,50.6208`},{-3.33375`,50.6223`},{-3.4271`,50.6254`},{-3.46745`,50.6254`},{-3.4767`,50.6208`},{-3.47785`,50.6016`},{-3.47785`,50.577`},{-3.49515`,50.5602`},{-3.52395`,50.541`},{-3.5378`,50.5218`},{-3.547`,50.4765`},{-3.5574`,50.4658`},{-3.58045`,50.4573`},{-3.5966`,50.4397`},{-3.59085`,50.4274`},{-3.5747`,50.4174`},{-3.5551`,50.4082`},{-3.50555`,50.4097`},{-3.4848`,50.399`},{-3.47905`,50.3844`},{-3.4825`,50.3714`},{-3.4894`,50.3576`},{-3.5159`,50.343`},{-3.56435`,50.323`},{-3.62315`,50.2977`},{-3.66465`,50.257`},{-3.67385`,50.2325`},{-3.67385`,50.2102`},{-3.6808`,50.1995`},{-3.69575`,50.1941`},{-3.7246`,50.2048`},{-3.74765`,50.2256`},{-3.7603`,50.2355`},{-3.76955`,50.2325`},{-3.77645`,50.2225`},{-3.79835`,50.2102`},{-3.826`,50.2041`},{-3.8594`,50.2202`},{-3.88595`,50.2532`},{-3.8986`,50.28`},{-3.9286`,50.2931`},{-3.95855`,50.2938`},{-3.99085`,50.2831`},{-4.02775`,50.2839`},{-4.04735`,50.2923`},{-4.05315`,50.3099`},{-4.0485`,50.3245`},{-4.0416`,50.336`},{-4.0439`,50.346`},{-4.06005`,50.3529`},{-4.07965`,50.356`},{-4.11075`,50.3552`},{-4.1315`,50.356`},{-4.14075`,50.369`},{-4.13615`,50.3813`},{-4.13845`,50.3944`},{-4.16265`,50.4036`},{-4.188`,50.4013`},{-4.2099`,50.3913`},{-4.218`,50.3828`},{-4.20645`,50.3721`},{-4.17995`,50.3598`},{-4.16955`,50.3437`},{-4.1834`,50.3299`},{-4.1984`,50.3284`},{-4.23645`,50.3353`},{-4.2849`,50.3506`},{-4.33445`,50.3675`},{-4.3621`,50.3706`},{-4.4013`,50.3667`},{-4.43475`,50.3552`},{-4.4693`,50.3399`},{-4.4958`,50.3345`},{-4.5258`,50.3345`},{-4.5696`,50.3322`},{-4.59265`,50.3214`},{-4.6157`,50.3168`},{-4.64105`,50.3122`},{-4.6653`,50.3191`},{-4.68605`,50.3191`},{-4.73215`,50.3084`},{-4.7633`,50.2969`},{-4.78405`,50.2838`},{-4.7875`,50.2647`},{-4.78865`,50.2447`},{-4.8013`,50.2263`},{-4.82435`,50.2194`},{-4.8774`,50.2194`},{-4.90855`,50.2117`},{-4.93275`,50.1887`},{-4.9662`,50.171`},{-5.0008`,50.1703`},{-5.03305`,50.1787`},{-5.06075`,50.1833`},{-5.07915`,50.1833`},{-5.09875`,50.1764`},{-5.1126`,50.1572`},{-5.1149`,50.1234`},{-5.11375`,50.1081`},{-5.10535`,50.0884`},{-5.10225`,50.0766`},{-5.1011`,50.0244`},{-5.1276`,49.9845`},{-5.1737`,49.9515`},{-5.21175`,49.9446`},{-5.25325`,49.9592`},{-5.2786`,49.9861`},{-5.29245`,50.006`},{-5.327`,50.0237`},{-5.37315`,50.0398`},{-5.42735`,50.0651`},{-5.48845`,50.0828`},{-5.56225`,50.0897`},{-5.60375`,50.0858`},{-5.6395`,50.072`},{-5.73285`,50.0252`},{-5.77435`,50.0214`},{-5.7997`,50.0306`},{-5.81815`,50.0513`},{-5.82625`,50.0736`},{-5.83085`,50.1173`},{-5.81585`,50.1472`},{-5.79625`,50.1756`},{-5.77205`,50.1933`},{-5.7252`,50.2209`},{-5.6636`,50.237`},{-5.6163`,50.2356`},{-5.5635`,50.2216`},{-5.51725`,50.2155`},{-5.49765`,50.2094`},{-5.4596`,50.2002`},{-5.43885`,50.204`},{-5.4285`,50.2186`},{-5.4308`,50.2332`},{-5.42385`,50.2447`},{-5.39505`,50.2478`},{-5.304`,50.2623`},{-5.26595`,50.2869`},{-5.2037`,50.3084`},{-5.1772`,50.3337`},{-5.16685`,50.3536`},{-5.16685`,50.3744`},{-5.1484`,50.392`},{-5.1161`,50.402`},{-5.07695`,50.4089`},{-5.0389`,50.4281`},{-5.03775`,50.4488`},{-5.0389`,50.4665`},{-5.0562`,50.4864`},{-5.07005`,50.511`},{-5.0677`,50.5348`},{-5.0458`,50.544`},{-5.00775`,50.5409`},{-4.9628`,50.5156`},{-4.9259`,50.5002`},{-4.8948`,50.501`},{-4.8821`,50.5056`},{-4.8694`,50.5217`},{-4.8729`,50.5332`},{-4.89015`,50.5371`},{-4.9213`,50.5363`},{-4.9478`,50.547`},{-4.9478`,50.5631`},{-4.93165`,50.5762`},{-4.8994`,50.5862`},{-4.85905`,50.5992`},{-4.84985`,50.6161`},{-4.83025`,50.6361`},{-4.71615`,50.6921`},{-4.64355`,50.7366`},{-4.6009`,50.7673`},{-4.58935`,50.7896`},{-4.58935`,50.8164`},{-4.5974`,50.8479`},{-4.5974`,50.8655`},{-4.58125`,50.8893`},{-4.55355`,50.9131`},{-4.5524`,50.9331`},{-4.56855`,50.9576`},{-4.5697`,50.9837`},{-4.5547`,51.0029`},{-4.52015`,51.0144`},{-4.47865`,51.0029`},{-4.4129`,50.9799`},{-4.3818`,50.9807`},{-4.3299`,50.9929`},{-4.25385`,51.0374`},{-4.21465`,51.0559`},{-4.12935`,51.0605`},{-4.1109`,51.0643`},{-4.10165`,51.0727`},{-4.10745`,51.0812`},{-4.1236`,51.0873`},{-4.1478`,51.0858`},{-4.187`,51.085`},{-4.2181`,51.0958`},{-4.225`,51.1088`},{-4.2273`,51.1349`},{-4.2158`,51.1587`},{-4.19155`,51.1771`},{-4.14545`,51.1879`},{-4.0878`,51.1932`},{-4.02675`,51.1932`},{-3.9518`,51.2117`},{-3.8792`,51.2232`},{-3.8077`,51.2285`},{-3.6263`,51.2175`},{-3.5559`,51.2354`},{-3.51655`,51.2382`},{-3.4213`,51.1981`},{-3.3654`,51.1981`},{-3.29085`,51.2202`},{-3.2598`,51.2271`},{-3.19975`,51.2244`},{-3.1521`,51.2285`},{-3.13245`,51.2403`},{-3.1097`,51.319`},{-3.0807`,51.3645`},{-3.0455`,51.388`},{-2.92125`,51.4142`},{-2.82395`,51.4667`},{-2.7142`,51.5026`},{-2.6873`,51.526`},{-2.6728`,51.5633`},{-2.6645`,51.5868`},{-2.6169`,51.6351`},{-2.5196`,51.711`},{-2.5082`,51.728`},{-2.54445`,51.7207`},{-2.60655`,51.6917`},{-2.74735`,51.5964`},{-2.85605`,51.5502`},{-2.9596`,51.5364`},{-2.98235`,51.5323`},{-3.0279`,51.5019`},{-3.05485`,51.4908`},{-3.1128`,51.4798`},{-3.13145`,51.4674`},{-3.2039`,51.4053`},{-3.32505`,51.37`},{-3.4389`,51.3631`},{-3.48035`,51.3756`},{-3.55485`,51.428`},{-3.6149`,51.4625`},{-3.6584`,51.4708`},{-3.71015`,51.4667`},{-3.7288`,51.4722`},{-3.764`,51.5053`},{-3.7909`,51.5136`},{-3.88305`,51.5184`},{-3.9638`,51.5626`},{-3.9969`,51.5668`},{-4.1025`,51.5488`},{-4.1522`,51.5226`},{-4.175`,51.5226`},{-4.2102`,51.546`},{-4.24125`,51.5543`},{-4.29095`,51.5585`},{-4.31165`,51.5668`},{-4.32615`,51.5957`},{-4.30545`,51.6165`},{-4.2785`,51.6234`},{-4.20605`,51.6026`},{-4.16255`,51.6013`},{-4.07975`,51.6303`},{-4.0259`,51.6606`},{-4.028`,51.6772`},{-4.0404`,51.6855`},{-4.07145`,51.6882`},{-4.15015`,51.6399`},{-4.175`,51.633`},{-4.19775`,51.6344`},{-4.25365`,51.6579`},{-4.35305`,51.6758`},{-4.3634`,51.6869`},{-4.35925`,51.6965`},{-4.293`,51.72`},{-4.2806`,51.731`},{-4.2868`,51.7435`},{-4.3096`,51.7545`},{-4.3365`,51.7517`},{-4.3572`,51.7559`},{-4.3748`,51.7745`},{-4.3976`,51.7745`},{-4.5011`,51.7442`},{-4.63365`,51.7207`},{-4.71855`,51.7207`},{-4.74545`,51.7097`},{-4.75375`,51.6945`},{-4.73715`,51.6462`},{-4.7475`,51.6337`},{-4.7848`,51.6241`},{-4.85105`,51.6282`},{-4.8904`,51.6448`},{-4.91525`,51.6475`},{-5.0105`,51.6337`},{-5.05395`,51.6379`},{-5.0871`,51.6586`},{-5.0933`,51.6765`},{-5.07055`,51.7083`},{-5.0809`,51.7166`},{-5.10575`,51.7166`},{-5.1492`,51.7041`},{-5.16575`,51.6986`},{-5.20305`,51.7124`},{-5.2341`,51.7138`},{-5.2465`,51.7262`},{-5.2403`,51.7414`},{-5.2072`,51.758`},{-5.16575`,51.758`},{-5.13265`,51.7663`},{-5.10365`,51.7883`},{-5.0933`,51.8229`},{-5.10985`,51.8477`},{-5.1782`,51.8767`},{-5.2755`,51.8822`},{-5.2962`,51.8974`},{-5.29415`,51.9181`},{-5.27965`,51.9319`},{-5.20305`,51.9512`},{-5.14505`,51.9927`},{-5.10365`,52.0396`},{-5.09745`,52.0658`},{-5.0809`,52.0713`},{-5.0167`,52.0658`},{-4.96905`,52.0727`},{-4.9401`,52.0713`},{-4.90075`,52.0465`},{-4.87795`,52.0479`},{-4.8614`,52.0589`},{-4.8614`,52.0713`},{-4.8821`,52.1017`},{-4.8614`,52.1155`},{-4.81585`,52.1114`},{-4.791`,52.1224`},{-4.7701`,52.1426`},{-4.74015`,52.1572`},{-4.7113`,52.1633`},{-4.62485`,52.1595`},{-4.59255`,52.1649`},{-4.56605`,52.184`},{-4.53605`,52.2247`},{-4.48995`,52.2439`},{-4.4346`,52.2508`},{-4.385`,52.2593`},{-4.33085`,52.2777`},{-4.2755`,52.316`},{-4.20405`,52.3728`},{-4.1326`,52.4327`},{-4.1061`,52.4826`},{-4.1003`,52.5171`},{-4.07725`,52.5601`},{-4.0565`,52.5777`},{-4.0265`,52.5869`},{-4.03`,52.5954`},{-4.0415`,52.6015`},{-4.1026`,52.6253`},{-4.1222`,52.6368`},{-4.13375`,52.6568`},{-4.1245`,52.7005`},{-4.0853`,52.7412`},{-4.07725`,52.7558`},{-4.083`,52.7673`},{-4.1095`,52.775`},{-4.1614`,52.778`},{-4.1752`,52.7865`},{-4.18095`,52.8294`},{-4.1821`,52.8509`},{-4.1994`,52.8693`},{-4.204`,52.8885`},{-4.1971`,52.9023`},{-4.14985`,52.9261`},{-4.13255`,52.9468`},{-4.1429`,52.9561`},{-4.17635`,52.9607`},{-4.204`,52.9599`},{-4.2582`,52.9361`},{-4.31355`,52.933`},{-4.41615`,52.933`},{-4.4542`,52.9246`},{-4.52565`,52.8908`},{-4.56025`,52.8839`},{-4.57525`,52.877`},{-4.58905`,52.8486`},{-4.59365`,52.8217`},{-4.6052`,52.8118`},{-4.6294`,52.8133`},{-4.64785`,52.8317`},{-4.66285`,52.8409`},{-4.68475`,52.8363`},{-4.73775`,52.8171`},{-4.76545`,52.8095`},{-4.7931`,52.8118`},{-4.80345`,52.8302`},{-4.80115`,52.8517`},{-4.78275`,52.8739`},{-4.7297`,52.9069`},{-4.69285`,52.9161`},{-4.64905`,52.9399`},{-4.58565`,52.9768`},{-4.49455`,53.0021`},{-4.4473`,53.0313`},{-4.3735`,53.0796`},{-4.35045`,53.1141`},{-4.279`,53.1694`},{-4.1925`,53.217`},{-4.12105`,53.2392`},{-4.04035`,53.2569`},{-3.9919`,53.2822`},{-3.95155`,53.3206`},{-3.94695`,53.3919`},{-3.9331`,53.4234`},{-3.91465`,53.4303`},{-3.89625`,53.4272`},{-3.88355`,53.418`},{-3.8628`,53.3935`},{-3.81555`,53.3628`},{-3.7694`,53.3428`},{-3.72215`,53.3321`},{-3.66335`,53.3221`},{-3.5965`,53.3229`},{-3.5538`,53.329`},{-3.43735`,53.3659`},{-3.39585`,53.3774`},{-3.3555`,53.3743`},{-3.33475`,53.3605`},{-3.33015`,53.3405`},{-3.3163`,53.3283`},{-3.28405`,53.3221`},{-3.2656`,53.3229`},{-3.21945`,53.3037`},{-3.15375`,53.273`},{-3.13765`,53.2738`},{-3.1192`,53.2838`},{-3.11575`,53.2999`},{-3.11575`,53.3137`},{-3.1457`,53.3313`},{-3.19645`,53.3636`},{-3.2022`,53.3889`},{-3.18955`,53.405`},{-3.1584`,53.4127`},{-3.13535`,53.415`},{-3.12035`,53.425`},{-3.10425`,53.4265`},{-3.0858`,53.4257`},{-3.06045`,53.4081`},{-3.01895`,53.3644`},{-2.97165`,53.3321`},{-2.92785`,53.3129`},{-2.8979`,53.3053`},{-2.87025`,53.3152`},{-2.86215`,53.3329`},{-2.87255`,53.3605`},{-2.88985`,53.3789`},{-2.9544`,53.4265`},{-3.0466`,53.4733`},{-3.0754`,53.5117`},{-3.1157`,53.57`},{-3.1215`,53.5862`},{-3.1065`,53.6099`},{-3.06845`,53.6383`},{-3.0327`,53.6667`},{-3.0154`,53.6867`},{-3.0085`,53.7044`},{-2.99005`,53.7128`},{-2.9578`,53.7159`},{-2.92895`,53.7258`},{-2.91165`,53.742`},{-2.91285`,53.7535`},{-2.9324`,53.7611`},{-2.982`,53.7634`},{-3.0039`,53.7588`},{-3.03385`,53.7504`},{-3.05345`,53.7527`},{-3.0765`,53.7719`},{-3.0788`,53.7872`},{-3.07075`,53.864`},{-3.05575`,53.877`},{-3.0373`,53.8816`},{-2.97275`,53.8809`},{-2.95545`,53.887`},{-2.9543`,53.8985`},{-2.9578`,53.9093`},{-2.99465`,53.9369`},{-2.9981`,53.9522`},{-2.99465`,53.9599`},{-2.97965`,53.9638`},{-2.94395`,53.9638`},{-2.9255`,53.963`},{-2.9197`,53.9691`},{-2.91625`,53.9837`},{-2.9278`,53.9968`},{-2.98425`,54.0336`},{-2.9935`,54.0466`},{-2.9889`,54.0581`},{-2.9808`,54.0697`},{-2.9635`,54.0781`},{-2.88515`,54.1188`},{-2.8759`,54.1326`},{-2.8805`,54.1441`},{-2.9001`,54.1733`},{-2.90125`,54.1886`},{-2.8932`,54.2178`},{-2.8932`,54.2293`},{-2.90245`,54.2354`},{-2.9232`,54.2339`},{-2.94395`,54.2224`},{-2.96935`,54.217`},{-2.9797`,54.2093`},{-2.9866`,54.1848`},{-3.00275`,54.174`},{-3.02005`,54.1717`},{-3.04885`,54.1817`},{-3.065`,54.1986`},{-3.07195`,54.2347`},{-3.07885`,54.2462`},{-3.095`,54.2485`},{-3.1134`,54.2393`},{-3.1353`,54.2047`},{-3.14685`,54.1687`},{-3.1572`,54.1533`},{-3.17795`,54.1418`},{-3.20565`,54.138`},{-3.2264`,54.1326`},{-3.23675`,54.1265`},{-3.23445`,54.1165`},{-3.21715`,54.0935`},{-3.2241`,54.082`},{-3.2483`,54.0766`},{-3.26905`,54.0797`},{-3.28635`,54.0912`},{-3.3025`,54.105`},{-3.3094`,54.1165`},{-3.30825`,54.1288`},{-3.30135`,54.1487`},{-3.2633`,54.2025`},{-3.2518`,54.2278`},{-3.23105`,54.28`},{-3.23565`,54.2907`},{-3.246`,54.2945`},{-3.261`,54.2938`},{-3.26905`,54.2823`},{-3.2979`,54.2362`},{-3.32095`,54.2247`},{-3.37975`,54.217`},{-3.39475`,54.2186`},{-3.40975`,54.2339`},{-3.4386`,54.2638`},{-3.472`,54.2838`},{-3.4847`,54.2984`},{-3.48355`,54.3145`},{-3.4847`,54.3391`},{-3.5008`,54.3536`},{-3.5953`,54.4066`},{-3.66565`,54.4703`},{-3.68525`,54.5002`},{-3.6899`,54.5202`},{-3.66105`,54.5631`},{-3.60345`,54.6345`},{-3.6011`,54.6629`},{-3.6115`,54.6821`},{-3.61035`,54.6936`},{-3.5746`,54.7166`},{-3.53885`,54.7358`},{-3.49855`,54.7703`},{-3.479`,54.8072`},{-3.46975`,54.8356`},{-3.4617`,54.8693`},{-3.4363`,54.897`},{-3.3429`,54.9507`},{-3.3072`,54.9584`},{-3.2772`,54.9591`},{-3.18615`,54.9468`},{-3.1723`,54.9484`},{-3.1677`,54.9584`},{-3.17`,54.9722`},{-3.17`,54.9852`},{-3.17925`,54.9998`},{-3.19885`,55.0059`},{-3.2277`,55.009`},{-3.245`,55.0059`},{-3.27265`,54.9983`},{-3.31185`,54.9867`},{-3.35565`,54.9783`},{-3.3787`,54.976`},{-3.4075`,54.9806`},{-3.44205`,54.9867`},{-3.4755`,54.9898`},{-3.51585`,54.9844`},{-3.5539`,54.9752`},{-3.58155`,54.9714`},{-3.61385`,54.976`},{-3.65535`,54.9821`},{-3.67955`,54.9821`},{-3.71185`,54.9722`},{-3.7222`,54.9583`},{-3.72795`,54.9438`},{-3.7268`,54.9276`},{-3.70835`,54.9085`},{-3.70835`,54.8931`},{-3.72105`,54.8808`},{-3.7395`,54.8755`},{-3.80635`,54.8785`},{-3.83405`,54.8762`},{-3.86745`,54.8609`},{-3.88015`,54.8601`},{-3.9032`,54.8639`},{-3.93895`,54.8808`},{-3.96085`,54.8808`},{-3.97005`,54.8762`},{-3.9793`,54.8655`},{-3.9735`,54.8356`},{-3.9793`,54.8271`},{-4.0012`,54.8187`},{-4.0208`,54.8056`},{-4.03925`,54.7795`},{-4.05535`,54.7711`},{-4.0911`,54.7726`},{-4.12455`,54.7957`},{-4.1349`,54.824`},{-4.14875`,54.831`},{-4.1649`,54.8287`},{-4.1718`,54.8171`},{-4.17985`,54.8003`},{-4.19255`,54.7934`},{-4.2179`,54.7957`},{-4.24675`,54.8095`},{-4.32975`,54.8471`},{-4.37355`,54.8532`},{-4.40465`,54.8701`},{-4.4277`,54.91`},{-4.45885`,54.9177`},{-4.48305`,54.9123`},{-4.4946`,54.9008`},{-4.49345`,54.8862`},{-4.48535`,54.8724`},{-4.4715`,54.8578`},{-4.4162`,54.8125`},{-4.40695`,54.7857`},{-4.40925`,54.7688`},{-4.4381`,54.7442`},{-4.445`,54.7304`},{-4.4381`,54.7197`},{-4.42425`,54.7074`},{-4.42655`,54.7005`},{-4.4519`,54.6836`},{-4.51995`,54.6713`},{-4.55565`,54.679`},{-4.5741`,54.6959`},{-4.59485`,54.7181`},{-4.62255`,54.7565`},{-4.6652`,54.7872`},{-4.709`,54.7987`},{-4.7482`,54.8026`},{-4.7839`,54.8133`},{-4.8692`,54.8709`},{-4.9234`,54.8778`},{-4.9568`,54.8693`},{-5.0052`,54.8379`},{-5.01445`,54.8072`},{-5.00985`,54.7665`},{-4.95795`,54.7082`},{-4.9591`,54.6898`},{-4.9741`,54.6783`},{-5.0052`,54.6813`},{-5.0271`,54.6905`},{-5.0744`,54.7258`},{-5.0905`,54.7542`},{-5.09745`,54.7811`},{-5.10205`,54.8033`},{-5.1159`,54.8225`},{-5.13435`,54.8317`},{-5.16665`,54.8548`},{-5.2462`,54.9614`},{-5.2485`,54.9814`},{-5.24505`,54.9967`},{-5.22085`,55.0182`},{-5.1874`,55.0251`},{-5.16205`,55.0205`},{-5.094`,54.9622`},{-5.07445`,54.9568`},{-5.06065`,54.9607`},{-5.0583`,54.9791`},{-5.0687`,54.996`},{-5.1217`,55.0558`},{-5.1217`,55.0781`},{-5.109`,55.0912`},{-5.0364`,55.1418`},{-4.943`,55.2086`},{-4.905`,55.2446`},{-4.89115`,55.273`},{-4.88425`,55.3045`},{-4.88195`,55.3505`},{-4.8727`,55.3705`},{-4.8393`,55.3912`},{-4.8266`,55.4043`},{-4.8243`,55.4503`},{-4.8116`,55.4772`},{-4.7966`,55.4941`},{-4.72975`,55.5247`},{-4.71935`,55.5432`},{-4.7159`,55.5654`},{-4.7228`,55.5854`},{-4.7378`,55.6015`},{-4.7666`,55.613`},{-4.9418`,55.6752`},{-4.966`,55.6967`},{-4.9683`,55.712`},{-4.96135`,55.7381`},{-4.95445`,55.7581`},{-4.9268`,55.8018`},{-4.91985`,55.8171`},{-4.92565`,55.8379`},{-4.94295`,55.8931`},{-4.93605`,55.9606`},{-4.9222`,55.9814`},{-4.90145`,55.9898`},{-4.82885`,55.9883`},{-4.664`,55.953`},{-4.6225`,55.9484`},{-4.6006`,55.9507`},{-4.5948`,55.9637`},{-4.60175`,55.9768`},{-4.61905`,55.9852`},{-4.7032`,56.0006`},{-4.7689`,56.0282`},{-4.81155`,56.0581`},{-4.8346`,56.0827`},{-4.8473`,56.0827`},{-4.87265`,56.0704`},{-4.89225`,56.0635`},{-4.92335`,56.0666`},{-4.9418`,56.0796`},{-4.93835`,56.095`},{-4.90955`,56.1203`},{-4.88645`,56.1656`},{-4.8934`,56.1801`},{-4.9049`,56.1832`},{-4.9268`,56.1748`},{-4.9568`,56.1617`},{-4.9764`,56.1625`},{-4.98445`,56.1725`},{-4.99485`,56.1824`},{-5.01095`,56.1817`},{-5.034`,56.1732`},{-5.04325`,56.154`},{-5.0398`,56.098`},{-5.03405`,56.0428`},{-5.0352`,56.0029`},{-5.03985`,55.9269`},{-5.04445`,55.9077`},{-5.07095`,55.8993`},{-5.094`,55.8962`},{-5.13895`,55.9138`},{-5.14815`,55.9284`},{-5.1493`,55.9668`},{-5.15625`,55.9791`},{-5.16775`,55.9852`},{-5.1793`,55.9791`},{-5.18965`,55.966`},{-5.2035`,55.9445`},{-5.21735`,55.9407`},{-5.23115`,55.9491`},{-5.2427`,55.9622`},{-5.25305`,55.9653`},{-5.27265`,55.9545`},{-5.2784`,55.9415`},{-5.28305`,55.9238`},{-5.26805`,55.9069`},{-5.245`,55.9`},{-5.215`,55.9`},{-5.1908`,55.9054`},{-5.1574`,55.8877`},{-5.10435`,55.8617`},{-5.0859`,55.8417`},{-5.08705`,55.8217`},{-5.0767`,55.8033`},{-5.0709`,55.7895`},{-5.0594`,55.7688`},{-5.0744`,55.7519`},{-5.1078`,55.7511`},{-5.13085`,55.7611`},{-5.1355`,55.7765`},{-5.1297`,55.7934`},{-5.1378`,55.8064`},{-5.147`,55.811`},{-5.1597`,55.8102`},{-5.17585`,55.8079`},{-5.1966`,55.8218`},{-5.2185`,55.8471`},{-5.2485`,55.8663`},{-5.29345`,55.8716`},{-5.3292`,55.8801`},{-5.373`,55.8947`},{-5.38565`,55.9138`},{-5.38915`,55.9399`},{-5.39955`,55.996`},{-5.4007`,56.0136`},{-5.38225`,56.0313`},{-5.3488`,56.0581`},{-5.3442`,56.0819`},{-5.31885`,56.098`},{-5.29`,56.1057`},{-5.15395`,56.1778`},{-5.109`,56.2201`},{-5.10785`,56.2331`},{-5.11595`,56.2362`},{-5.13555`,56.2339`},{-5.1701`,56.2231`},{-5.20815`,56.1993`},{-5.24045`,56.1771`},{-5.3119`,56.1564`},{-5.3626`,56.1195`},{-5.42135`,56.0643`},{-5.48595`,56.0397`},{-5.5311`,56.0255`},{-5.54645`,56.0009`},{-5.5403`,55.9681`},{-5.50915`,55.9259`},{-5.4001`,55.823`},{-5.3944`,55.805`},{-5.40575`,55.7861`},{-5.43835`,55.7663`},{-5.5035`,55.7484`},{-5.53895`,55.72`},{-5.54035`,55.6926`},{-5.52405`,55.6648`},{-5.5113`,55.6119`},{-5.52405`,55.5722`},{-5.585`,55.5221`},{-5.6374`,55.474`},{-5.6544`,55.4551`},{-5.6544`,55.4428`},{-5.6431`,55.4343`},{-5.5949`,55.4334`},{-5.58215`,55.4211`},{-5.585`,55.3937`},{-5.61335`,55.372`},{-5.66715`,55.3606`},{-5.69835`,55.3568`},{-5.72665`,55.3408`},{-5.80035`,55.3191`}},{{-7.1481`,55.1193`},{-7.1613`,55.0969`},{-7.154`,55.0852`},{-7.1336`,55.0862`},{-7.09715`,55.0998`},{-7.0622`,55.1474`},{-7.05925`,55.1824`},{-7.03305`,55.2135`},{-6.9995`,55.2222`},{-6.91645`,55.2213`},{-6.8669`,55.2038`},{-6.81445`,55.1814`},{-6.7818`,55.179`},{-6.77445`,55.1809`},{-6.7508`,55.1938`},{-6.72715`,55.2151`},{-6.6966`,55.2271`},{-6.6215`,55.2438`},{-6.46025`,55.2715`},{-6.3824`,55.2771`},{-6.3518`,55.2891`},{-6.31985`,55.2901`},{-6.28785`,55.2771`},{-6.24755`,55.2632`},{-6.21835`,55.2623`},{-6.20165`,55.2715`},{-6.1794`,55.2743`},{-6.1558`,55.2493`},{-6.14185`,55.2216`},{-6.1377`,55.1781`},{-6.11965`,55.1373`},{-6.064`,55.104`},{-5.9973`,55.0707`},{-5.94725`,55.0235`},{-5.87775`,54.9476`},{-5.8652`,54.9087`},{-5.865`,54.878`},{-5.8638`,54.8643`},{-5.84435`,54.8448`},{-5.8082`,54.83`},{-5.7693`,54.8004`},{-5.7693`,54.7699`},{-5.7804`,54.756`},{-5.81655`,54.7384`},{-5.8972`,54.7014`},{-5.93475`,54.6671`},{-5.9806`,54.6532`},{-6.0404`,54.6468`},{-6.08905`,54.6468`},{-6.10855`,54.6329`},{-6.1099`,54.6125`},{-6.0988`,54.5977`},{-6.0696`,54.5885`},{-6.02095`,54.5857`},{-5.96535`,54.6005`},{-5.9153`,54.619`},{-5.82215`,54.6699`},{-5.6984`,54.6875`},{-5.6303`,54.6884`},{-5.5747`,54.6792`},{-5.53715`,54.6514`},{-5.5135`,54.5968`},{-5.49125`,54.5385`},{-5.4648`,54.4922`},{-5.46345`,54.47`},{-5.4996`,54.4256`},{-5.5121`,54.408`},{-5.51905`,54.3774`},{-5.5399`,54.3598`},{-5.54965`,54.358`},{-5.558`,54.3691`},{-5.57605`,54.407`},{-5.62055`,54.5014`},{-5.6303`,54.5375`},{-5.65255`,54.5487`},{-5.6887`,54.5477`},{-5.71925`,54.5431`},{-5.7415`,54.5246`},{-5.73175`,54.5014`},{-5.7067`,54.482`},{-5.67755`,54.4533`},{-5.6678`,54.4385`},{-5.6817`,54.4237`},{-5.7095`,54.408`},{-5.7415`,54.383`},{-5.7512`,54.3672`},{-5.73175`,54.3608`},{-5.6956`,54.3719`},{-5.6553`,54.3904`},{-5.62745`,54.3876`},{-5.6024`,54.3626`},{-5.5913`,54.3312`},{-5.59685`,54.3173`},{-5.62605`,54.2988`},{-5.6469`,54.2886`},{-5.66635`,54.2691`},{-5.66775`,54.2414`},{-5.68025`,54.2256`},{-5.69275`,54.2201`},{-5.70945`,54.2182`},{-5.72475`,54.2275`},{-5.75115`,54.2451`},{-5.76925`,54.2469`},{-5.78175`,54.2442`},{-5.7998`,54.2247`},{-5.8179`,54.2136`},{-5.84155`,54.2127`},{-5.8707`,54.2256`},{-5.89435`,54.233`},{-5.91105`,54.2266`},{-5.92075`,54.2108`},{-5.9124`,54.1664`},{-5.9138`,54.1312`},{-5.9541`,54.0859`},{-5.9986`,54.0572`},{-6.0459`,54.0479`},{-6.09035`,54.0433`},{-6.1045`,54.0384`},{-6.1154`,54.0566`},{-6.1187`,54.0985`},{-6.1297`,54.108`},{-6.14845`,54.1117`},{-6.23875`,54.1109`},{-6.2762`,54.1227`},{-6.31145`,54.1308`},{-6.46625`,54.1316`},{-6.587`,54.1139`},{-6.64225`,54.1193`},{-6.68935`,54.136`},{-6.85285`,54.2744`},{-6.88375`,54.3245`},{-6.94635`,54.3957`},{-7.01115`,54.432`},{-7.0745`,54.4448`},{-7.16135`,54.4359`},{-7.1923`,54.4104`},{-7.22765`,54.3515`},{-7.24755`,54.2813`},{-7.27405`,54.2371`},{-7.34325`,54.1919`},{-7.40955`,54.1664`},{-7.51855`,54.1536`},{-7.58185`,54.1595`},{-7.7284`,54.2219`},{-7.7564`,54.2356`},{-7.81825`,54.2455`},{-7.88895`,54.3044`},{-7.9714`,54.3604`},{-8.10175`,54.4374`},{-8.12385`,54.4698`},{-8.115`,54.5013`},{-8.0664`,54.5258`},{-7.92795`,54.5494`},{-7.8322`,54.571`},{-7.77845`,54.6048`},{-7.77255`,54.6235`},{-7.78875`,54.6402`},{-7.8462`,54.6598`},{-7.85505`,54.6765`},{-7.83735`,54.6942`},{-7.67385`,54.759`},{-7.64295`,54.7835`},{-7.5951`,54.8616`},{-7.55385`,54.9745`},{-7.5229`,55.028`},{-7.47285`,55.0585`},{-7.3948`,55.082`},{-7.20035`,55.1095`},{-7.1481`,55.1193`}},{{-6.4991`,57.5306`},{-6.40405`,57.517`},{-6.37285`,57.5197`},{-6.3599`,57.5247`},{-6.3545`,57.5364`},{-6.3708`,57.5437`},{-6.39795`,57.5663`},{-6.40065`,57.5799`},{-6.38845`,57.5998`},{-6.3871`,57.6125`},{-6.4129`,57.646`},{-6.4509`,57.6904`},{-6.45905`,57.7175`},{-6.457`,57.7297`},{-6.4217`,57.7487`},{-6.40405`,57.7505`},{-6.3239`,57.7288`},{-6.2859`,57.7116`},{-6.20035`,57.6609`},{-6.1623`,57.6256`},{-6.15145`,57.5912`},{-6.17385`,57.5147`},{-6.19015`,57.4948`},{-6.23225`,57.4712`},{-6.2363`,57.4595`},{-6.23495`,57.4423`},{-6.22135`,57.4359`},{-6.19555`,57.4278`},{-6.1752`,57.4124`},{-6.1752`,57.3798`},{-6.18405`,57.3703`},{-6.2085`,57.3676`},{-6.218`,57.3567`},{-6.2153`,57.3422`},{-6.20305`,57.3422`},{-6.1732`,57.3468`},{-6.15145`,57.3422`},{-6.13925`,57.3314`},{-6.1365`,57.3178`},{-6.1243`,57.3105`},{-6.03605`,57.3223`},{-6.0116`,57.3178`},{-5.98305`,57.2933`},{-5.9654`,57.2897`},{-5.8948`,57.3006`},{-5.8391`,57.297`},{-5.80855`,57.2857`},{-5.79365`,57.2757`},{-5.7909`,57.2467`},{-5.814`,57.2313`},{-5.8534`,57.2123`},{-5.8697`,57.1987`},{-5.8656`,57.1661`},{-5.88055`,57.1535`},{-5.8982`,57.1417`},{-5.91585`,57.1417`},{-5.93895`,57.1354`},{-5.962`,57.1236`},{-5.98375`,57.1001`},{-6.0285`,57.0883`},{-6.08145`,57.0973`},{-6.10255`,57.1159`},{-6.08625`,57.1512`},{-6.0428`,57.182`},{-5.998`,57.2055`},{-5.9749`,57.2218`},{-5.97895`,57.2354`},{-6.02105`,57.2418`},{-6.10255`,57.2463`},{-6.1243`,57.2399`},{-6.15825`,57.2137`},{-6.17995`,57.1739`},{-6.19355`,57.163`},{-6.2207`,57.1612`},{-6.2329`,57.1693`},{-6.218`,57.2101`},{-6.22615`,57.2173`},{-6.2424`,57.2155`},{-6.256`,57.2055`},{-6.27365`,57.1766`},{-6.28315`,57.1621`},{-6.3001`,57.1553`},{-6.387`,57.1489`},{-6.3979`,57.1535`},{-6.4196`,57.1761`},{-6.41415`,57.187`},{-6.36935`,57.2096`},{-6.3585`,57.2232`},{-6.3612`,57.2349`},{-6.3707`,57.2395`},{-6.4427`,57.2368`},{-6.4644`,57.2404`},{-6.474`,57.2531`},{-6.4726`,57.3074`},{-6.4638`,57.3232`},{-6.4448`,57.3269`},{-6.39725`,57.3232`},{-6.3823`,57.3278`},{-6.37145`,57.3477`},{-6.37415`,57.3567`},{-6.438`,57.3884`},{-6.45835`,57.4138`},{-6.47875`,57.4274`},{-6.49775`,57.4283`},{-6.50995`,57.4228`},{-6.51135`,57.4056`},{-6.5032`,57.3758`},{-6.5127`,57.3694`},{-6.53035`,57.3794`},{-6.5833`,57.4102`},{-6.5996`,57.412`},{-6.61725`,57.4092`},{-6.64035`,57.393`},{-6.6906`,57.3966`},{-6.72455`,57.4083`},{-6.7612`,57.4292`},{-6.806`,57.4283`},{-6.83115`,57.4351`},{-6.85695`,57.4532`},{-6.8624`,57.4767`},{-6.84745`,57.4867`},{-6.80535`,57.4939`},{-6.7741`,57.493`},{-6.73065`,57.4803`},{-6.6804`,57.4622`},{-6.6641`,57.4595`},{-6.62475`,57.4604`},{-6.6071`,57.4686`},{-6.59895`,57.4803`},{-6.6003`,57.5011`},{-6.6166`,57.5183`},{-6.67905`,57.5935`},{-6.68855`,57.6152`},{-6.6736`,57.6388`},{-6.64445`,57.6591`},{-6.61865`,57.6655`},{-6.6064`,57.6646`},{-6.5942`,57.6546`},{-6.58195`,57.5867`},{-6.57515`,57.5659`},{-6.54935`,57.5478`},{-6.4991`,57.5306`}},{{-6.3334`,56.6393`},{-6.2689`,56.6379`},{-6.24175`,56.647`},{-6.2214`,56.6678`},{-6.1956`,56.6777`},{-6.1535`,56.6732`},{-6.01905`,56.6135`},{-5.9287`,56.5777`},{-5.86355`,56.5668`},{-5.78615`,56.5424`},{-5.72365`,56.5343`},{-5.6992`,56.5252`},{-5.68225`,56.5039`},{-5.6809`,56.4876`},{-5.6972`,56.4713`},{-5.71755`,56.4659`},{-5.73385`,56.4713`},{-5.7542`,56.4813`},{-5.7651`,56.4804`},{-5.7841`,56.465`},{-5.8031`,56.4614`},{-5.8398`,56.4559`},{-5.84655`,56.4478`},{-5.8452`,56.436`},{-5.76235`,56.4324`},{-5.7556`,56.4252`},{-5.761`,56.4152`},{-5.8235`,56.3844`},{-5.9077`,56.3609`},{-6.05975`,56.3627`},{-6.1324`,56.3613`},{-6.1446`,56.3523`},{-6.21115`,56.3188`},{-6.28175`,56.3043`},{-6.3782`,56.3016`},{-6.4142`,56.3066`},{-6.43595`,56.3211`},{-6.43595`,56.3328`},{-6.4251`,56.3518`},{-6.3694`,56.3663`},{-6.2825`,56.3727`},{-6.1942`,56.3872`},{-6.1752`,56.3935`},{-6.163`,56.4053`},{-6.1616`,56.4161`},{-6.1793`,56.4243`},{-6.22`,56.4161`},{-6.2458`,56.4197`},{-6.273`,56.4406`},{-6.27435`,56.4523`},{-6.22275`,56.4831`},{-6.1657`,56.4949`},{-6.12905`,56.4985`},{-6.11885`,56.5026`},{-6.1175`,56.518`},{-6.14055`,56.5379`},{-6.16365`,56.5469`},{-6.25055`,56.5397`},{-6.3008`,56.5406`},{-6.3361`,56.5506`},{-6.3565`,56.5714`},{-6.3619`,56.6003`},{-6.347`,56.632`},{-6.3334`,56.6393`}},{{-4.572`,53.4313`},{-4.52985`,53.4442`},{-4.4596`,53.4383`},{-4.39815`,53.4348`},{-4.356`,53.4383`},{-4.3314`,53.4372`},{-4.31385`,53.4266`},{-4.3033`,53.4044`},{-4.27345`,53.3821`},{-4.26645`,53.3657`},{-4.25765`,53.3494`},{-4.21375`,53.3388`},{-4.1751`,53.3353`},{-4.15755`,53.3224`},{-4.15755`,53.3107`},{-4.17335`,53.2885`},{-4.2032`,53.2733`},{-4.219`,53.2686`},{-4.2401`,53.2534`},{-4.2524`,53.2264`},{-4.284`,53.1995`},{-4.3156`,53.1936`},{-4.33315`,53.1878`},{-4.34545`,53.1831`},{-4.3525`,53.1644`},{-4.3718`,53.1574`},{-4.4122`,53.1562`},{-4.42975`,53.1632`},{-4.4315`,53.1749`},{-4.435`,53.1936`},{-4.4438`,53.2042`},{-4.46485`,53.2054`},{-4.48945`,53.2018`},{-4.52455`,53.189`},{-4.5439`,53.1936`},{-4.59305`,53.2276`},{-4.6194`,53.2335`},{-4.6721`,53.2534`},{-4.7072`,53.2803`},{-4.71245`,53.2978`},{-4.7107`,53.3119`},{-4.69845`,53.3177`},{-4.68085`,53.3154`},{-4.65275`,53.2908`},{-4.62645`,53.2744`},{-4.60885`,53.2733`},{-4.59655`,53.2826`},{-4.59655`,53.3014`},{-4.6071`,53.3154`},{-4.62115`,53.3564`},{-4.61415`,53.4079`},{-4.59305`,53.4231`},{-4.572`,53.4313`}},{{-6.37`,55.9297`},{-6.3404`,55.9297`},{-6.32825`,55.9239`},{-6.32475`,55.9065`},{-6.3413`,55.8874`},{-6.35`,55.8688`},{-6.3378`,55.8595`},{-6.31345`,55.8618`},{-6.2717`,55.8816`},{-6.216`,55.9326`},{-6.1899`,55.9477`},{-6.1725`,55.9454`},{-6.16205`,55.9384`},{-6.1603`,55.8723`},{-6.14985`,55.8282`},{-6.10985`,55.7725`},{-6.1029`,55.7226`},{-6.1133`,55.6959`},{-6.14985`,55.6727`},{-6.21775`,55.6553`},{-6.26125`,55.646`},{-6.30215`,55.6501`},{-6.33175`,55.6582`},{-6.3387`,55.6675`},{-6.33`,55.6779`},{-6.31955`,55.6977`},{-6.32305`,55.7081`},{-6.35955`,55.7267`},{-6.3648`,55.7394`},{-6.35435`,55.751`},{-6.3126`,55.7615`},{-6.2865`,55.7766`},{-6.2795`,55.7951`},{-6.2865`,55.8044`},{-6.3091`,55.809`},{-6.35955`,55.8044`},{-6.3961`,55.7847`},{-6.43615`,55.7464`},{-6.4692`,55.7093`},{-6.4866`,55.6988`},{-6.5075`,55.6942`},{-6.5249`,55.6965`},{-6.54575`,55.7104`},{-6.5597`,55.7383`},{-6.54925`,55.7615`},{-6.5179`,55.7858`},{-6.5127`,55.7974`},{-6.51965`,55.8276`},{-6.51445`,55.8427`},{-6.4918`,55.8578`},{-6.457`,55.8705`},{-6.4222`,55.881`},{-6.4048`,55.8949`},{-6.3874`,55.9181`},{-6.37`,55.9297`}},{{-5.33985`,55.7406`},{-5.2998`,55.736`},{-5.2476`,55.7162`},{-5.2215`,55.7012`},{-5.21105`,55.6663`},{-5.2128`,55.5875`},{-5.2041`,55.5643`},{-5.1658`,55.5457`},{-5.1519`,55.5271`},{-5.15365`,55.5062`},{-5.1693`,55.4912`},{-5.17975`,55.4726`},{-5.1919`,55.4668`},{-5.2215`,55.4714`},{-5.2528`,55.4784`},{-5.2772`,55.4784`},{-5.2998`,55.4738`},{-5.3172`,55.468`},{-5.33985`,55.4714`},{-5.36595`,55.4877`},{-5.37985`,55.5097`},{-5.38335`,55.5364`},{-5.399`,55.5608`},{-5.4251`,55.5898`},{-5.4425`,55.6107`},{-5.44075`,55.6478`},{-5.42335`,55.6687`},{-5.39725`,55.6861`},{-5.38335`,55.7139`},{-5.36595`,55.7302`},{-5.35375`,55.7394`},{-5.33985`,55.7406`}},{{-5.9767`,56.0788`},{-5.841`,56.1554`},{-5.8027`,56.1635`},{-5.76615`,56.167`},{-5.74875`,56.1577`},{-5.747`,56.1333`},{-5.76615`,56.1055`},{-5.7888`,56.0834`},{-5.86185`,56.0347`},{-5.9054`,55.972`},{-5.9367`,55.9303`},{-5.96105`,55.9094`},{-6.0011`,55.8816`},{-6.03065`,55.8734`},{-6.0846`,55.8758`},{-6.11245`,55.8839`},{-6.12985`,55.9048`},{-6.1281`,55.9187`},{-6.1055`,55.9384`},{-6.02195`,55.9987`},{-6.0011`,56.0045`},{-5.9889`,56.015`},{-5.9837`,56.0347`},{-5.98195`,56.0602`},{-5.9802`,56.0741`},{-5.9767`,56.0788`}},{{-1.44235`,50.6447`},{-1.31185`,50.7097`},{-1.2579`,50.7282`},{-1.1796`,50.7271`},{-1.1639`,50.7201`},{-1.103`,50.6807`},{-1.0891`,50.6552`},{-1.103`,50.6354`},{-1.14305`,50.596`},{-1.16045`,50.567`},{-1.17435`,50.56`},{-1.24745`,50.5531`},{-1.27705`,50.5542`},{-1.29095`,50.56`},{-1.3449`,50.5821`},{-1.3954`,50.5925`},{-1.4441`,50.5995`},{-1.46675`,50.6064`},{-1.4737`,50.6192`},{-1.45805`,50.632`},{-1.44235`,50.6447`}}}];
gflag=;
ukflag=;
sph[v_]:={Cos[v[[1]] Degree]Cos[v[[2]] Degree],Cos[v[[1]]Degree]Sin[v[[2]]Degree],Sin[v[[1]]Degree]};
geoDist[a_,b_]:=N[2ArcSin[Norm[sph[a[[2]]]-sph[b[[2]]]]/2]];
Needs["Combinatorica`"];
geoMST[cnt_]:=Module[{cts, ctsT,names,flag,poly,edges,gWeight, mst,col},
If[cnt=="Germany",cts=germCitiesCoord;names=germCitiesNames;flag=gflag;col=LightOrange;poly=germPoly,cts=ukCitiesCoord;names=ukCitiesNames;flag=ukflag;poly=ukPolygon;col=LightGray];
edges=Edges[CompleteGraph[Length[cts]],All];
gWeight=SetEdgeWeights[Graph[edges,cts],WeightingFunction->geoDist];
mst=Edges[MinimumSpanningTree[gWeight]];
ctsT=Reverse/@ Flatten[cts,1];
Graphics[{col,EdgeForm[Black],poly,Thick, Green,MapThread[Line[{#1,#2}]&,{ctsT[[#[[1]]]]&/@mst,ctsT[[#[[2]]]]&/@mst}],PointSize[Medium],Red,
MapThread[Tooltip[Point[#1],#2]&,{ctsT,names}],
Inset[flag,{Right,Top},{Right,Top},2]}]
];
GraphicsRow[geoMST[#]&/@{"Germany","UnitedKingdom"}]

3...  Пример оптимизационной задачи: задача коммивояжера

Также очень популярной является так называемая задача коммивояжера, состоящая в том, чтобы найти замкнутый маршрут наименьшего веса, проходящий через все вершины данного взвешенного графа. Одним из ее естественных приложений является поиск оптимального маршрута бродячего торговца (коммивояжера), которому надо объехать данный набор городов и вернуться домой, оптимизируя расходы на дорогу. В настоящее время не известен эффективный точный алгоритм поиска решения этой задачи (вероятнее всего, такого алгоритма не существует).  В Mathematica реализован ряд приближенных методов решения задачи о коммивояжере, дающих точный ответ для малого числа вершин. Соответствующая функция называется FindShortestTour. По умолчанию весовая функция – евклидово расстояние, а граф – полный.

Manipulate[Graphics [ Line[p[[#~Join~{#[[1]]}& @ Last[FindShortestTour[p]]]]],PlotRange->{{-2,2},{-2,2}}],{{p,{{0,1},{1,0},{1,1}}},Locator,LocatorAutoCreate->True}]

Снова пользуясь географическими базами данных можно получить, например, такую картирнку, описывающую оптимальный маршрут посещения всех стран мира.

3...  Задача о ближайших соседях и триангуляция Делоне

С помощью триангуляции Делоне и диаграммы Вороного также  легко решается, например, известная задача о ближайших соседях. А именно, ближайшими соседями точки (Subscript[m, i]) из подмножества M={(Subscript[m, 1]),...,(Subscript[m, n])} метрического пространства называются такие точки (Subscript[m, j]), что ρ((Subscript[m, i]),(Subscript[m, j]))≤ρ((Subscript[m, i]),(Subscript[m, k])) для всех k≠i. Можно определить ориентированный граф ближайших соседей, в котором ориентированные ребра, выходящие из вершины (Subscript[m, i]), приходят в ближайших соседей (Subscript[m, j]) точки (Subscript[m, i]). Этот граф, очевидно, также является подграфом триангудяции Делоне. Граф ближайших соседей используется, например, в задачах кластеризации, т.е. разбиения точек множества  M на подмножества, составленные, в некотором смысле, из "близких" точек. Один из подходов состоит в выделении слабых связных компонент графа ближайших соседей.

DynamicModule[{pts,pts0,neibs},
pts0={{-1,-1},{1,0},{0,0},{0,1},{1,1}};
Manipulate[neibs=FromOrderedPairs[adLists[pts]];
Show[showOrGr[neibs,pts],PlotRange->{{-2,2},{-2,2}}],{{pts,pts0},Locator,LocatorAutoCreate->True}],Initialization:>(Needs["Combinatorica`"];Needs["ComputationalGeometry`"];
showOrGr[g_,v_]:=Module[{cmp},cmp=WeaklyConnectedComponents[g];Graphics[GraphicsComplex[v,
{ColorData[3,"ColorList"][[ Mod[Position[cmp,#[[1]]][[1,1]],10]+1]],Arrow[#]}&/@Edges[g] ]]];
nearNeib[pts_,i_]:=Module[{delauney,min,dist},
delauney=#[[2]]&/@ DelaunayTriangulation[pts];
dist=Norm[pts[[i]]-pts[[#]]]&/@delauney[[i]];
min=Min[dist];delauney[[i,Flatten[Position[dist,min]]]] ];
adLists[pts_]:=Module[{nb,f},nb=nearNeib[pts,#]&/@Range[Length[pts]];f[x_,y_]:={x,#}&/@y;Flatten[MapThread[f,{Range[Length[pts]],nb}],1]]
)
]

3...  Минимальные деревья Штейнера

Еще один пример оптимизационной задачи – знаменитая проблема Штейнера. На практике такая задача возникает при проектировании коммуникационных сетей, например, сети дорог, связывающей данные населенные пункты, или сети проводников, соединяющих различные элементы микросхемы. Обычно требуется, чтобы полученная сеть была оптимальна, скажем, имела наименьшую возможную длину. Похожую задачу мы уже разбирали, говоря о минимальном остовном дереве, однако теперь разрешается добавлять промежуточные развилки, обычно называемые точками Торричелли или точками Штейнера, что существенно осложняет дело.

Кратчайшая сеть дорог, соединяющих 532 города в США.

Пример расположения проводников, соединяющих элементы микросхемы.

Простейший вариант проблемы Штейнера известен как задача Ферма: построить на евклидовой плоскости такую точку, чтобы суммарное расстояние от нее до заданных трех точек, называемых терминалами, была наименьшей возможной. Ниже приведена визуалзация решения этой задачи, причем терминалы задаются локаторами. Поэксперименторуйте с положением локаторов и попробуйте сформулировать определяющее свойство полученной сети.

Manipulate[Module[{x,y,s},
s={x,y}/.Last@Quiet@FindMinimum[Plus@@(Norm[{x,y}-#]&/@p),{{x,First@Mean[p]},{y,Last@Mean[p]}},Method->"PrincipalAxis"];
Graphics[Line[{s,#}]&/@p,PlotRange->{{-2,2},{-2,2}},AspectRatio->Automatic]],
{{p,{{-1,0},{1,0},{0,1}}},Locator}]

Внимательное изучение поведения сети показывает, что пока все три отрезка невырождены, углы между ними равны между собой и, значит, равны (120^⋄), а когда один из отрезков вырождается, то угол между оставшимися отрезками не становится меньше, т.е. остается больше или равен (120^⋄). Кроме того, дополнительные вершины не могут иметь степень 1 или 2. На самом деле, это действительно так, причем даже в общем случае. Ниже приведен пример кратчайшей сети для четырех терминалов, как на плоскости, так и в трехмерном пространстве.

Manipulate[Module[{g1,g2,g3,g,x1,y1,x2,y2,min,res,res1,gr,sub,v,e,st,dist,MyShowGraph},
dist[v_,w_]:=(Sqrt[(v-w).(v-w)]);
st[g_,ls_]:=Quiet@Module[{vv,ee,len},vv=Vertices[g]; ee=Edges[g];len=Plus@@(dist@@vv[[#]]&/@ee);FindMinimum[len,{#,RandomReal[]}&/@Flatten[vv[[ls]]],Method->"PrincipalAxis"]~Join~{g}];
MyShowGraph[g_,opts:OptionsPattern[Graphics]]:=Module[{vv,ee},vv=Vertices[g];ee=Edges[g];Graphics[Line[vv[[#]]]&/@ee,opts]];
g1 = Graph[{{{1, 5}}, {{2, 5}}, {{5, 6}}, {{6, 3}}, {{6, 4}}},({#}&/@p)~Join~{{{x1,y1}},{{x2,y2}}}];
g2 = Graph[{{{1, 5}}, {{3, 5}}, {{5, 6}}, {{6, 2}}, {{6, 4}}},({#}&/@p)~Join~{{{x1,y1}},{{x2,y2}}}];
g3 = Graph[{{{1, 5}}, {{4, 5}}, {{5, 6}}, {{6, 3}}, {{6, 2}}},({#}&/@p)~Join~{{{x1,y1}},{{x2,y2}}}];
g={g1,g2,g3};
res=st[#,{5,6}]&/@g;
min=Min[#[[1]]&/@res];
res1=Select[res,#[[1]]==min&]//First;
gr=res1//Last;
sub=res1[[2]];
v=Vertices[gr]/.sub;
e=Edges[gr];
MyShowGraph[AddEdges[AddVertices[EmptyGraph[0],v],e],PlotRange->{{-2,2},{-2,2}}]
],
{{p,{{-1,1},{-1,-1},{1,-1},{1,1}}},Locator},
Initialization:>( 
Needs["Combinatorica`"];
)
]

Замечание об управлении. При наведении курсора на граничную (красную) вершину сети (см. ниже), вершина становится желтой. Чтобы выделить граничную вершину сети, позиционируйте курсор на этой вершине и нажмите ctrl. Вершина станет зеленой, "прикрепится" к курсору мыши и будет следовать за ним. Чтобы отпустить вершину, нажмите shift. ВЕршина вновь станет красной. Нажимая левую клавишу мыши при курсоре, позиционированном на картинке, и двигая курсор, Вы будете вращать картинку. Обратите на скачкообразные перестройки структуры сети (бифуркации).

DynamicModule[{pp,Locator3D,MyMean,testPoint,st,net4},
Locator3D[pts0_,f_:Line]:=
DynamicModule[{pts,ppp,cur,c=False,covered=False,g,msAlt,bds,bm=-1,bM=1,ptsAlt,j=1,testIn=2},
pts=pts0;
ptsAlt={0,0,0};msAlt={{1.3,-2.4,2.},{-1.3,2.4,-2.}};
cur=Dynamic[MousePosition["Graphics3DBoxIntercepts",msAlt]];
g=Graphics3D[Map[{Red,Sphere[#,0.05]}&,
If[c,Drop[pts,{j}],pts]]~Join~
Table[
If[CurrentValue["ControlKey"]&&covered,c=True;msAlt=#;ptsAlt=pts[[j]]];
If[CurrentValue["ShiftKey"],c=False];
testIn=Length[CurrentValue[{"MousePosition","GraphicsImageScaled"}]];
If[c,
If[testIn<2,pts[[j]]=ptsAlt];
bds= Transpose[AbsoluteOptions[g,PlotRange][[1,2]]];
bm=0.7bds[[1]];bM=0.7bds[[2]];
ppp=MyMean[pts[[j]],#];pts[[j]]=MapThread[Max[Min[#1,#3],#2]&,{ppp,bm,bM}];ptsAlt=pts[[j]];msAlt=#
];
If[c,If[i==j,{Green,Sphere[pts[[i]],0.07]},{}],
If[(testIn≥2)&&(testPoint[pts[[i]],#]<0.01 ),covered=True;j=i;{Yellow,Sphere[pts[[i]],0.07]},covered=False;{}
]
],
{i,1,Length[pts]}]~Join~{f[pts]}& /@ cur,
Boxed->True,PlotRange-> {{-1.3,1.3},{-1.3,1.3},{-1.3,1.3}}],Initialization:>(
MyMean[p_,ms_]:=ms[[1]] + (ms[[2]]-ms[[1]])(((ms[[2]]-ms[[1]]).(p-ms[[1]]))/((ms[[2]]-ms[[1]]).(ms[[2]]-ms[[1]])));
testPoint[p_,ms_]:=Module[{v},v=p-ms[[1]] - (ms[[2]]-ms[[1]])(((ms[[2]]-ms[[1]]).(p-ms[[1]]))/((ms[[2]]-ms[[1]]).(ms[[2]]-ms[[1]])));v.v];
)
];
st[g_,ls_]:=Quiet@Module[{vv,ee,len},vv=First@g; ee=Last@g;len=Plus@@(EuclideanDistance@@vv[[#]]&/@ee);FindMinimum[len,{#,RandomReal[]}&/@Flatten[vv[[ls]]],Method->"PrincipalAxis"]~Join~{g}];
net4[p_]:=Module[{g1,g2,g3,gg,res,min,res1,gr,sub,v,e,x1,y1,z1,x2,y2,z2},
g1 = {(#&/@p)~Join~{{x1,y1,z1},{x2,y2,z2}},{{1, 5}, {2, 5}, {5, 6}, {6, 3}, {6, 4}}};
g2 = {(#&/@p)~Join~{{x1,y1,z1},{x2,y2,z2}},{{1, 5}, {3, 5}, {5, 6}, {6, 2}, {6, 4}}};
g3 = {(#&/@p)~Join~{{x1,y1,z1},{x2,y2,z2}},{{1, 5}, {4, 5}, {5, 6}, {6, 3}, {6, 2}}};
gg={g1,g2,g3};
res=st[#,{5,6}]&/@gg;
min=Min[#[[1]]&/@res];
res1=Select[res,#[[1]]==min&]//First;
gr=res1//Last;
sub=res1[[2]];
v=First@gr/.sub;
e=Last@gr;
Line[v[[#]]]&/@e
];
pp={{-1,0,-1},{-1,0,0},{-1,1,0},{1/2,1/2,1/2}};

pp={{-1,0,-1},{-1,0,0},{-1,1,0},{1/2,1/2,1/2}};
Locator3D[pp,net4]
]

Из сказанного выше следует, что каждая кратчайшая сеть является деревом с терминалами степени не выше трех и дополнительными вершинами степени три. Отсюда вытекает, что если n – число терминалов, то дополнительных вершин может быть не больше n-2 (проверьте). Тем самым, имеется конечное, хотя и экспоненциально растущее с ростом n, число комбинатронхых структур кратчайших сетей. Доказано, что проблема Штейнера на евклидовой плоскости является NP-трудной, т.е. скорее всего не существует полиномиального по n алгоритма построения кратчайшей сети.

Тем не менее, в последнее время разработаны достаточно быстрые алгоритмы, позволяющие строить кратчайшие сети для сотен точек. Приведем визуализацию одного свойства решения задачи Ферма, лежащего в основе всех точных алгоритмов.

Если на сторонах треугольника построить правильные треугольники, пересекающие исходный только по его сторонам, то три окружности (изображенные красным цветом), описанные вокруг построенных треугольников, пересекутся в одной точке. В той же точке пересекутся и три отрезка (изображенные синим цветом), каждый из которых соединяет добавленную вершину построенного правильного треугольника с противоположной ей вершиной исходного.

Если в треугольнике, построенном на терминалах, все углы не превосходят (120^⋄), то общая точка пересечения красных окружностей и синих отрезков совпадает с решением задачи Ферма. Если же некоторый угол больше или равен (120^⋄), то решение задачи Ферма – вершина этого угла.

Manipulate[Module[{pc,pp,i,sign,pt3={},tri={},seg={},c,r,circ={},dist,vec},
dist[v_,w_]:=(Sqrt[(v-w).(v-w)]);
vec[v_]:={Re[v],Im[v]};
pp=p;
For[i=1,i≤3,i++,
pc=Complex@@#&/@pp;
sign=Sign[Det[{pp[[3]]-pp[[1]],pp[[2]]-pp[[1]]}]];
If[sign≠0,
pt3=pc[[1]](E^(-sign  I(π/3)))+pc[[2]](E^(sign I (π/3)));
c=Mean[{pp[[1]],pp[[2]],vec@pt3}];
r=dist[c,pp[[1]]];
tri=tri~Join~{{pp[[1]],pp[[2]],vec@pt3,pp[[1]]}};
seg=seg~Join~{{vec@pt3,pp[[3]]}};
circ=circ~Join~{{c,r}};
];
pp=RotateLeft[pp];
] ;
Graphics[{{Dashed}~Join~(Line/@tri)}~Join~{Blue}~Join~(Line/@seg)~Join~{Red}~Join~(Circle@@#&/@circ),PlotRange->{{-2,2},{-2,2}},AspectRatio->Automatic]
],
{{p,{{-1,0},{1,0},{0,1}}},Locator}]

Если замениить евклидово расстояние на манхеттенское, порожденное нормой ‖{x,y}‖ = |x| + |y|, то соответствующие кратчайшие сети используются при проектировки микросхем.

Поэкспериментируйте с примером, приведенным ниже, и постарайтесь сформулировать правило, описывающее направление отрезков.

Manipulate[Module[{x,y,s,distManhat},
distManhat[v_,w_]:=Plus@@Abs@(v-w);
s={x,y}/.Last@Quiet@FindMinimum[Plus@@(distManhat[{x,y},#]&/@p),{{x,First@Mean[p]},{y,Last@Mean[p]}},Method->"PrincipalAxis"];
Graphics[Line[{s,#}]&/@p,PlotRange->{{-2,2},{-2,2}},AspectRatio->Automatic]],
{{p,{{-1,0},{1,0},{0,1}}},Locator}
]

Ниже приведена реализация кратчайшей сети на манхеттенской плоскости в случае четырех терминалов. Обратите внимание на скачкообразное изменение кратчайшей сети при смещении терминалов. Эта особенность поведения сети объясняется неоднозначностью решения, в отличие от евклидова случая.

Manipulate[Module[{g1,g2,g3,x1,y1,x2,y2,min,res,res1,gr,sub,v,e,distManhat,st,MyShowGraph},
distManhat[v_,w_]:=Plus@@Abs@(v-w);
st[g_,ls_]:=Quiet@Module[{vv,ee,len},vv=Vertices[g]; ee=Edges[g];len=Plus@@(distManhat@@vv[[#]]&/@ee);FindMinimum[len,{#,RandomReal[]}&/@Flatten[vv[[ls]]],Method->"Newton"]~Join~{g}];
MyShowGraph[g_,opts:OptionsPattern[Graphics]]:=Module[{vv,ee},vv=Vertices[g];ee=Edges[g];Graphics[Line[vv[[#]]]&/@ee,opts]];
g1 = Graph[{{{1, 5}}, {{2, 5}}, {{5, 6}}, {{6, 3}}, {{6, 4}}},({#}&/@p)~Join~{{{x1,y1}},{{x2,y2}}}];
g2 = Graph[{{{1, 5}}, {{3, 5}}, {{5, 6}}, {{6, 2}}, {{6, 4}}},({#}&/@p)~Join~{{{x1,y1}},{{x2,y2}}}];
g3 = Graph[{{{1, 5}}, {{4, 5}}, {{5, 6}}, {{6, 3}}, {{6, 2}}},({#}&/@p)~Join~{{{x1,y1}},{{x2,y2}}}];
g={g1,g2,g3};
res=st[#,{5,6}]&/@g;
min=Min[#[[1]]&/@res];
res1=Select[res,#[[1]]==min&]//First;
gr=res1//Last;
sub=res1[[2]];
v=Vertices[gr]/.sub;
e=Edges[gr];
MyShowGraph[AddEdges[AddVertices[EmptyGraph[0],v],e],PlotRange->{{-2,2},{-2,2}}]
],
{{p,{{-1,1},{-1,-1},{1,-1},{1,1}}},Locator},
Initialization:>( 
Needs["Combinatorica`"];
)]

Отметим, что единичная окружность на манхеттонской плоскости является квадратом, диагонали которого лежат на координатных осях. Обобщением манхеттенской метрики являются так называемые λ-нормы, для которых единичная окружность – правильный 2λ-угольник. Ниже приводится визуализация кратчайших сетей на λ-нормированной плоскости в случае трех терминалов. При λ > 2 вновь отмечается скачкообразное поведение сетей при cмещении терминальных точек, что опять же объясняется неоднозначностью решения.

Manipulate[Module[{x,y,s,lin,vec,nr,norm,cr,len,res,gsol,distNorm},
vec[v_]:={Re[v],Im[v]};
nr = vec@#&/@Table[(E^(I (π/λ)(k+(1/2)))),{k,0,λ-1}];
norm[v_]:=((Max@@( Abs[#.v]&/@nr))/(nr[[1]].{1,0}));
distNorm[v_,w_]:=norm[v-w];
cr=ParametricPlot[(({Cos[φ],Sin[φ]})/(norm[{Cos[φ],Sin[φ]}])),{φ,0,2π},PlotStyle->{Red}];
len=Plus@@(distNorm[{x,y},#]&/@p);
res=Quiet@FindMinimum[len,{{x,RandomReal[]},{y,RandomReal[]}},Method->"Newton"];
s={x,y}/.Last@res;
Show[{Graphics[Line[{s,#}]&/@p,PlotRange->{{-2,2},{-2,2}},AspectRatio->Automatic],cr}]
],
{{λ,3},Rest@Range[20]},
{{p,{{-1,0},{1,0},{0,1}}},Locator}
]