Page 107 - 4496

Проведемо розкладання для всіх ступенів вершин.
Побудуємо дві розбивки вершин: розбивка на k класів по l
елементів =( 1, 2,…, k) і розбивка на l класів по k елементів
=( 1,  2, …,  l), n=kl, щоб добутком цих розбивок була
розбивка на одноелементні множини.
В один клас  потраплять вершини а й b, якщо для них
у розкладанні r a=r b і p a=p b.
В один клас  потраплять вершини а й b, якщо в
розкладаннях t a=t b і q a=q b.
Якщо такі розбивки побудувати можна, то їм
зіставляється перестановка елементів за наступним правилом.
Зафіксуємо порядок блоків у розбивках  і . Зіставимо цьому
порядку перестановку: спочатку старшинство визначається по
розбивці , потім усередині цих блоків - по розбивці .
Розглянемо метод на прикладі. Нехай граф описується
матрицею табл. 3.7, розкладання s і t наведені в цій таблиці.
Значення ступеня, що рівне 0, представляється добутком 0 на
довільне число, яке позначається як х. Першим завданням є
завдання вибору серед розкладань тих, які приведуть до
розбивок вершин по ступенях результату й заходу.
При виборі розкладань будемо враховувати наступне.
Для вершини 4 вибираємо розбивку 22, тому що
вершині зі співмножником 4 у пару не знайти. У розкладання
 вершини 4 і 5 повинні бути в різних блоках, тому що в них
обидві компоненти по s різні. Те ж саме стосовно t для
вершин 3 і 4. Отже, 3 і 5 будуть в одному блоці. Вершини 3 і 6
повинні бути в одному блоці по t і в різних блоках по s, 1 і 5 –
у різних блоках по t, щоб по першому компоненту їх можна
було об'єднати в розкладанні . Курсивом виділені розбивки.
У підсумку одержуємо розкладання ={{1,4,6}, {2,3,5}}.

104