This page is hosted for free by zzz.com.ua, if you are owner of this page, you can remove this message and gain access to many additional features by upgrading your hosting to PRO or VIP for just 32.50 UAH.
Do you want to support owner of this site? Click here and donate to his account some amount, he will be able to use it to pay for any of our services, including removing this ad.

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

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

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

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

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

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

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

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

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

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