Методы дискретной оптимизации. 2 вариант

На плоскости задано конечное множество Р списком {{x, Уг), ..., (Х, Ус}} координат своих точек, точки занумерованы по порядку. Бинарные деревья заданы списками смежности
G1={[7), (7], (8), (8], (9], (9}, (1, 2, 10], (3, 4, 10], (5, 6, 10], (7, 8, 9]] (1ая вершина смежна с 7ой, Гая вершина смежна с 7ой, ..., 10ая - с 7ой, 8ой и 9ой)
G2={[7}, (7], (8), (10], (10], (9], {1, 2, 8], (3, 7, 9], (6, 8, 10], (4, 5, 9]
С помощью алгоритма Мелзака или Венга-Мелзака выяснить, существуют ли соответствующие локально минимальные бинарные деревья, соединяющие Р. Если дерево существует, построить одну из линий Симпсона и найти длину локально минимального дерева. Если дерево не существует - обосновать с помощью правил Венга выбор одного из двух правильных треугольников на каждом шаге алгоритма. Если существуют оба дерева - сравнить их длины.