Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Минимальное (взвешенное) вершинное покрытие". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу: там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же задача о взвешенном минимальном вершинном покрытии решается путём сведения к задаче бинарного линейного программирования.
Введём обозначения:
- n=|V| − размер графа (количество вершин);
- m=|E| − мощность графа (количество рёбер);
-
A − бинарная (состоящая из нулей и единиц) матрица инцидентности размером
n×m; каждый её элементaik=1, если i-я вершина инцидентна k-му ребру; иaik=0 в противоположном случае; в каждом столбце такой матрицы ровно две единицы, а остальные нули; -
v − бинарный вектор-столбец длины n; каждый его элемент
vi=1, если i-я вершина включается в минимальное взвешенное вершинное покрытие, иvi=0, если нет; - d − вектор-столбец весов вершин длины n;
- 1 − вектор-столбец из единиц нужной длины;
- t − целевая функция: суммарный вес вершин, включённых в миниимальное взвешенное вершинное покрытие.
Тогда задача о минимальном взвешенном вершином покрытии может быть сформулирована как задача бинарного линейного программирования:
Минимизируется общий вес вершин, включённых в минимальное взвешенное вершинное покрытие (1). При этом каждому ребру должно быть инцидентно не менее одной такой вершины (2), а каждая вершина может или включаться в вершинное покрытие, или нет (3).
Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script. Включите их.
Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести
координаты вершин для рисования графа и веса вершин. Координаты вершин задаются в левой части. Они задаются
в виде матрицы
Следующая область ввода − обязательная для заполнения. В ней определяется структура графа.
Каждое ребро в графе соединяет две вершины. Номера этих вершин задаются в виде матрицы
x (пробел) y | Вес |
v1 (пробел) v2 |