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

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

• n=|V| − размер графа (количество вершин);
• m=|E| − мощность графа (количество рёбер);
• A − бинарная (состоящая из нулей и единиц) матрица инцидентности размером n×m; каждый её элемент a_ik=1, если i-я вершина инцидентна k-му ребру; и a_ik=0 в противоположном случае; в каждом столбце такой матрицы ровно две единицы, а остальные нули;
• v − бинарный вектор-столбец длины n; каждый его элемент v_i=1, если i-я вершина включается в максимальное взвешенное независимое множество вершин, и v_i=0, если нет;
• d − вектор-столбец весов вершин длины n;
• 1 − вектор-столбец из единиц нужной длины;
• z − целевая функция: суммарный вес вершин, включённых в максимальное взвешенное независимое множество вершин.

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

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

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

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

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