Page 134 - 6197

 Переходимо до розв’язання задачі 2 4,  , для якої
забороненими є переходи (1,2) і (2,4). Після вилучення ребер
(1,2) і (2,4) із початкового 1-дерева T (рис. 2.8) і з’єднання
1
вершини 4 з вершинами 1 і 6, отримуємо 1-дерева T у
1

вигляді циклу i  1 3 2 5 6 4 1, , , , , , (рис. 2.15), довжина якого
L   11i  .

Рисунок 2.14 – 1-дерево T після вилучення ребер (1,2) і
1
(2,3)
L
Оскільки значення   i співпадає зі значенням рекорду,
який отриманий раніше, то задача 2 4,  не підлягає
подальшому розгалуженню.
 Наступна задача, яку необхідно розв’язати це задача
2 5, . Тут забороненими є переходи (1,2) і (2,5). Із
початкового 1-дерева T (рис. 2.8) вилучаємо ребра (1,2) і (2,5)
1
і з’єднуємо між собою вершини 4 і 5 та 1 і 6. У результаті

отримаємо 1-дерево у вигляді циклу i  1 3 2 4 5 6 1, , , , , , (рис.
2.16), довжина якого   11L i  . Знову отримали значення

L   i , яке співпадає зі значенням рекорду. Тому задача 2 5, 
не підлягає розгалуженню.

134