Page 115 - 6109

яким винні задовольняти відповідні мітки, записані поряд з ребрами. Основна
ідея полягає в звуженні множини можливих міток для кожної з вершин,
спираючись на задані обмеження.

n 1 {1,3,4,5,6}

l 1 + l 2 = 8 l 1  l 3

l 2  l 3
{3,4,5,6,7} n 2 n 3 {1,3,5,6}

l 4  l 3
l 2 – l 4 = 1

n 4 {1,3,4,5}

Рисунок 12.2 – Злагоджена розмітка вузлів графа

Розглянемо множину сумісних міток для вершин n 1 і n 2 при обмеженні
l 1 + l 2 = 8. Спочатку при заданій множині L 1 = {1, 3, 4, 5, 6} видалимо з L 2 всі
мітки, що не задовольняють вказаній умові. В даному випадку відношення
виконується для всіх міток з L 2, за винятком мітки 6. Отже, дана мітка
видаляється, і L 2 = {3, 4, 5, 7}. Потім відношення B 12 використовується для
перевірки множини міток L 1. В цьому випадку з L 1 також видаляється мітка 6, і
множина L 1 складатиметься з міток {1, 3, 4, 5}. Таким чином, ми спочатку
розповсюдили обмеження b 12 з вершини n 1 у вершину n 2, а потім назад з n 2 в n 1,
видаляючи відповідні мітки з множин L 2 і L 1 Мітки, що входять в множини L 2 і
L 1, тепер злагоджені.
На наступному кроці для аналізу вибирається вершина, яка пов'язана з
найбільшим числом вершин, вже розглянутих до поточного моменту. В даному
випадку це вершина n 3. Розповсюдивши обмеження від n 1 до n 3 і від n 2 до n 3,
одержимо L 3={1, 3, 5}. Потім відповідні обмеження розповсюджуються у
зворотний бік. При цьому множини L 2 і L 1 не змінюються. Нарешті, аналогічні
операції виконуються з вершиною n 4. У результаті L 4 = {3, 4}, L 2 = {4, 5},
L 3={3, 5}. Потім обмеження розповсюджуються між n 2 і n 3 (це дає L 3 = {3}), а
також від n 2 і n 3 до n 1. Одержуємо L 1 = {3, 4}. Поширюючи обмеження назад від
n 1 до n 2, n 3 і n 4, одержуємо остаточний результат: l 1 = 4 l 2 = 4, l 3 = 3, l 4 = 2.
Розповсюдження обмежень продовжується до тих пір, поки на множині міток
відбуваються зміни.
В загальному випадку вершина може мати декілька міток. При цьому
довільно комбінувати мітки для різних вершин не можна. Необхідно
враховувати існуючі обмеження. Очевидно, в цьому випадку задача має
декілька рішень.

115