Оптимизация графа (сокращение числа вершин)

[akj]

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

Вершина 0 — корень, вершины с 10 по 18 вкл. — листья, остальные вершины составляют неопределённое ядро.
У каждого из девяти листьев может быть ровно по два истока, причём веса дуг (для которых листья являются стоком) могут принимать значения либо $+1$, либо $-1$.
На дуги между вершинами, относящимися к ядру, распространяется условие: любая из вершин ядра не может быть стоком для более, чем двух, дуг.

Каждой вершине соответствует некоторое значение:

• корню соответствует значение 1;
• каждому стоку соответствует значение, являющееся взвешенной суммой истоков (т. е. сумма произведений веса дуги на значение соответствующего истока), причём по абсолютному значению сумма не должна превосходить любое из слагаемых более, чем в 15 раз;
• листьям соответствуют следующие неизменные значения (номер вершины — значение): 10—58, 11—60, 12—63, 13—66, 14—68, 15—70, 16—71, 17—73, 18—76.

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

Начальное приближение (см. вот такой граф):

• содержит в ядре вершины со следующими значениями: 1—4, 2—10, 3—14, 4—16, 5—17, 6—54, 7—64, 8—80, 9—90 (могут быть также определены через веса дуг);
• веса дуг ($w_{\text{исток},\text{сток}}=\text{вес}$): $w_{0,1}=4$, $w_{0,2}=10$, $w_{0,5}=1$, $w_{1,3}=1$, $w_{1,4}=4$, $w_{1,10}=1$, $w_{1,11}=-1$, $w_{1,13}=1$, $w_{2,3}=1$, $w_{2,6}=1$, $w_{2,9}=1$, $w_{3,13}=-1$, $w_{3,18}=-1$, $w_{4,5}=1$, $w_{4,7}=4$, $w_{4,8}=1$, $w_{4,15}=1$, $w_{5,12}=-1$, $w_{5,16}=1$, $w_{5,17}=-1$, $w_{6,10}=1$, $w_{6,15}=1$, $w_{6,16}=1$, $w_{7,11}=1$, $w_{7,14}=1$, $w_{8,12}=1$, $w_{8,13}=1$, $w_{9,17}=1$, $w_{9,18}=1$.

Есть какие-нибудь предложения по решению такой задачи? Или рекомендации по формулированию в матричном виде оптимизационной задач для matlab или octave?
Буду весьма признателен.

[akj]

Существенное дополнение.
Веса дуг должны быть целыми.