Мінімальне (зважене) вершинне покриття

Ця сторінка призначена для студентів, що вивчають курс дискретної математики та (або) теорії графів. Безпосередньо з неї ви можете виконати своє ІДЗ, навіть якщо у вас немає на комп’ютері MATLAB. Якщо ж у вас є MATLAB, перейдіть на цю сторінку: там у вас є можливість втрутитися у сценарій (програму) обчислень. А на цій сторінці задача про мінімальне (зважене) вершинне покриття розв’язується шляхом зведення до задачі бінарного лінійного програмування.

Нехай G(VE) − граф, де V − множина вершин, а E − множина ребер. Мінімальним (зваженим) вершинним покриттям називається мінімальна за потужністю або загальною вагою підмножина вершин V1V, які є інцидентними до всіх ребер графа. Введемо позначення:

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

Мінімізується загальна вага вершин, включених у мінімальне зважене вершинне покриття (1). При цьому кожному ребру повинна бути інцидентна хоча б одна така вершина (2), а кожна вершина може або включатися у вершинне покриття, або ні (3). Докладніше див. тут, стор. 36.

Для правильної роботи з цією сторінкою ваш браузер повинен підтримувати сценарії Java Script. Увімкніть їх.

Введіть вхідні дані в області введення нижче. У першій області треба (точніше, можна) ввести координати вершин для малювання графа та ваги вершин. Координати вершин задаються у лівій частині першої області. Вони задаються у вигляді матриці n×2: у першому стовпці − x координати, у другому − y-і. Числа можна задавати цілі, з десятичною точкою або в експоненційній формі. Числа розділяйте пробілами. Загальна кількість рядків у цій області введення визначає розмір графа n − кількість вершин. Ці вхідні дані (координати вершин) не є обов’язковими: якщо їх не задати, то граф буде малюватися у вигляді правильного n-кутника, а кількість вершин буде визначатися максимальним номером вершини у наступній області введення. Ваги вершин задаються у правій частині першої області введення у вигляді вектора довжиною n. Якщо ваги вершин не будуть задані, то вважається, що все вони одинакові − одиничні, і в цьому випадку буде розв’язуватися задача про мінімальне вершинне покриття (незважене).

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

Координати вершин та їхні ваги
x   (пробіл)   y Вага

Ребра
v1  (пробіл)  v2