Page 60 - 4386

При розгляді шляху M(e , e ,…, e ), за його вагу (або
m
1
2
довжину, або вартість) беруть число L(M), рівне сумі ваг всіх дуг,
m
c для всіх e ∈M.
що входять в шлях, тобто L( M ) = ∑ i m
= i 1

6.2 Алгоритми побудови кістякових дерев

Розглянемо неорієнтований граф G=(V, E). Припустимо, що

кожному ребру (v, w) графа G приписана вага с(v, w). Визначимо

вагу дерева як суму ваг ребер, що входять до нього.

Суть алгоритму побудови кістякового дерева полягає в

перегляді в довільному порядку ребер вхідного графа. При

кожному перегляді у відношенні відповідного ребра приймається

рішення про те, буде або не буде воно включене в кістякове

дерево. Алгоритм можна представити як процес зафарбовування

ребер. При цьому, зелений колір використовується для

зафарбування ребер, що включаються в кістякове дерево, а

жовтий – для зафарбування ребер, що не включаються в це

дерево.

В алгоритмі при розгляді ребра здійснюється тільки

перевірка того, не чи утворює дане ребро в сукупності з ребрами,

уже включеними в дерево (зеленими ребрами), цикл. Якщо

результат перевірки є позитивним, то розглянуте ребро не

включається в дерево (зафарбовується в жовтий колір). В іншому

випадку це ребро включається в дерево (зафарбовується в

зелений колір).

Перевірка того, чи утворює ребро, що розглядається, цикл у

сукупності з ребрами, уже включеними в дерево (зеленими

ребрами), здійснюється так. Ребра, включені в дерево, утворюють

граф, що має один або декілька зв'язних компонент. Вершини, що

59