Page 129 - 6197

5
( n  ), то для її розв’язання доцільно використати алгоритм
1
*
Краскала, який включає у себе такі кроки.
St1. Упорядкувати ребра графа у порядку зменшення їх
ваг.
St2. Починаючи з першого ребра в такому списку,
добавляли ребра до каркасного графа T за умови, що така
процедура не приведе до появи циклів у T .
St3. Повторювати крок St2. до тих пір, поки не
вичерпається вся множина ребер.
Використовуючи табл. 2.9 упорядкуємо ребра графа у
порядку зростання їх ваг, враховуючи при цьому, що c  c .
ij ji
Отже, маємо таку упорядковану множину ребер:
  2 3,  2 4, ,  2 5, ,  5 6, ,  3 4, ,  3 5, ,  3 6, ,  4 6, ,  5 4, ,  6 2, ,  .
Будуємо каркасний граф, починаючи з ребра (2,3).
Наступним ребром, яке слід долучити до T буде ребро (2,4).
Потім послідовно додаємо до T ребра (2,5) і (5,6). Інші дуги
не долучаємо до T , оскільки як неважко переконатись їх
доручення приводить до появи циклів у T .
До дерева T добавляємо два ребра, які інцидентні вершині
1. У результаті отримуємо 1-дерево T (рис. 2.8), довжина
1
якого
1
L T 1 L   3,  L   2,  L 3 2,  L 2 4,  L 2 5,  L 5 6,   .
  
1
 2 2 1 1 1 1 8      .
L T
Значення   визначає нижню оцінку маршруту
1
комівояжера. Отже, оптимальний маршрут комівояжера буде
L T
знаходитись між значеннями   і  
L i
1 0
*
8 L   13i  .

*
Кристофидес Н. Теория графов. Алгоритмический подход / Н.
Кристофидес; пер. с англ. – М.: Мир, 1978. – 432 с.

129