Page 48 - 2577

C  G  min C :  G ,

G X
якщо
 deg    Mv 2
V V  
G
deg  Vv   2G .
Нехай c ij – вага, що співвіднесена до ребра, яке інцидентне вершинам i та j.
Для розв’язку цієї задачі можна використати такий алгоритм:
К1. Сортування рядків матриці С з елементами c ij. Елементи матриці С сортуються за

порядком зростання вартостей. Таким чином, для кожного вузла і в і – ому рядку матриці C
вміщуються вартості з’єднання і – го вузла з іншими вузлами в порядку збільшення. Коли
відповідні вузли не з’єднані між собою, то c   .
ij

К1. Для кожного рядка матриці C вибрати перші два елементи, тобто обчислити
N 2
*
1 
c  c .
ij
i 1 j 1

2
К2. Інші N – 2N елементи матриці C розмістити в порядку зростання їх вартостей,
тобто із елементів, що залишились, сформувати вектор c    : c  c при i < j.
c
i
r
j
К3. Вибрати перші 2М – 2N елементів вектора c , тобто обчислити
 2 M N 
*
c   c .
2 r
r 1
К4. Обчислити нижню оцінку вартості мережі з М ребрами
*
c  c *
*
c  1 2 .
2
К5. Останов.
Число ребер зазвичай невідомо. Тому для отримання нижньої оцінки вартості мережі
необхідно визначити границю числа ребер, при якій виконуються умови (3.2) – (3.4). Нижче
розглядається задача визначення числа ребер, виходячи із обмежень (3.2) – (3.4).
Розглянемо граф G = G(V,E), який має N  V вершин і M  E ребер. Позначимо
V
через  ,dNR ,d  клас графів, для яких   dGD  , GD  x  d , GD  e  d , де x ;
1 2 1 2 3
e E , а через M  ,dN ,d  - мінімальне число ребер в графі G  R  ,dN ,d . Граф G, на
1 2 1 2
якому досягається цей мінімум називається екстремальним. Для екстремальних графів
виконується умова d  d . На практиці d  3. Клас графів для яких d  d  3 позначимо
1 2 2 1 2
R  ,N  3 . Має місце така теорема. Для екстремальних графів класу  ,NR  3 :
M  2N  4 при 4  N  7 ;
M  2N  5 при 8  N  23 ;
M  2N  6 при N  24 .
Вказана теорема дає можливість обчислити нижню межу числа ребер.
Наступний етап в розв’язку задачі – генерація каркасних двозв’язних підграфів
заданого графа.
Допустимо, що заданий граф G 0 з заданим числом ребер М, для якого d  3. Введемо
1
вектор x   1 2 M  , де x i = 0, якщо ребро e не належить розв’язку і x  в
x ,x ,...,x
1
i
i
0
протилежному випадку. Нехай розв’язком задачі є граф, який поданий вектором
  1
x  x ,x ,...,x  , що складається тільки з одиниць. Для пошуку нового розв’язку із графа
i  i 1 2 i M i
вилучається ребро e , додаються ребра з векторами від i  1 до ? і розглядається вектор
M i M
x   2  x ,x ,...,x ,x ,...,x  . Якщо вектор x   2 задає граф, який не задовольняє обмежень
i  i 1 2 i M i 1  M i 1  M i 0 i
45