Мінімальна правильна розфарбовка вершин графа

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

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

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

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

Якщо для вашого графа алгоритм (1-6) буде працювати довго (кілька хвилин), можна скористатися наближеним алгоритмом, який дає правильну розфарбовку, але не завжди мінімальну. Цей алгоритм заснований на поступовому виключенні максимальних незалежних множин вершин та інцидентних до них ребер.

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

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

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

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

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