Page 116 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

1. Вибираємо ще не розглянуте ребро мінімальної довжини. У нашому ви-

падку це ребро d 5,9= 5,7. Обводимо кружечком дане число у матриці ві-

дстаней (помічаємо розглянуте ребро). Сполучаємо на схемі (рис. 8.4.)

відповідні вершини.

2. Вибираємо ще не розглянуте ребро мінімальної довжини d 4,7 = 7,1 (цикл

не утворює)

3. Вибираємо не розглянуте ребро мінімальної довжини d 1,4 = 9,1 (цикл не

утворює).

4. Далі маємо два ребра мінімальної довжини d 4,8 = d 7,9 = 11,2 (цикл не

утворює).

5. Ребро d 1,8 = 12,2 утворює цикл, тому його не розглядаємо.

6. Далі йдуть ребра d 2,6 = 14,0, d 2,3 = 14,8 (цикл не утворюють)

7. Ребро d 1,7 = 15,2 утворює цикл, тому вибираємо ребро d 2,7 = 17,0.

Рисунок 8.4. Схема найдешевшої дорожньої мережі

115