Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Минимальное (взвешенное) доминирующее множество рёбер", или "Минимальное (взвешенное) внешне устойчивое множество рёбер". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу: там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же задача о взвешенном минимальном доминирующем (внешне устойчивом) множестве рёбер решается путём сведения к задаче бинарного линейного программирования.

Введём обозначения:

• n=|V| − размер графа (количество вершин);
• m=|E| − мощность графа (количество рёбер);
• C − бинарная (состоящая из нулей и единиц) матрица смежности рёбер графа размером m×m; каждый её элемент c_kl=1, если k-е ребро смежно с l-м; и c_kl=0 в противоположном случае; на главной диагонали ставим единицы;
• e − бинарный вектор-столбец длины m; каждый его элемент e_k=1, если k-е ребро включается в минимальное доминирующее множество рёбер, и e_k=0, если нет;
• w − вектор-столбец весов рёбер длины m;
• 1 − вектор-столбец из единиц нужной длины;
• t − целевая функция: суммарный вес рёбер, включённых в миниимальное взвешенное доминирующее множество рёбер.

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

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

Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script. Включите их.

Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести координаты вершин для рисования графа. Они задаются в виде матрицы n×2: в первом столбце − x-е координаты, во втором − y-е. Числа можно задавать целые, с десятичной точкой или в экспоненциальной форме. Числа разделяйте пробелами. Общее количество строк в этой области ввода определяет размер графа n − количество вершин. Эти исходные данные (координаты вершин) не являются обязательными: если их не задать, то граф будет рисоваться в виде правильного n-угольника, а количество вершин будет определяться максимальным номером вершины в следующей области ввода.

В следующей области ввода левая часть − обязательная для заполнения. В ней определяется структура графа. Каждое ребро в графе соединяет две вершины. Номера этих вершин задаются в виде матрицы m×2 в левой части второй области ввода. Какую вершину считать первой, а какую второй − не имеет значения. В этих столбцах должны быть натуральные числа от 1 до n включительно. Числа разделяйте пробелами. В правой части задаются веса рёбер − действительные числа. Если этот столбец не задан, все веса считаются одинаковыми (единичными), в этом случае решается задача об обычном (невзвешенном) максимальном паросочетании. Общее количество чисел в каждом из этих столбцов определяет мощность графа m − количество рёбер.