asyan.org
добавить свой файл
  1 2 3 ... 6 7

Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*).

З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.

i j


1


2


3


4


5


6


7


8


9


10


di


1


M


0(2)


1


2


3


4


5


6


7


8


1


2


7


M


0(1)


1


2


3


4


5


6


7


1


3


7


8


M


0(1)


1


2


3


4


5


6


1


4


6


7


6


M


5


4


3


2


1


0(1)


1


5


5


6


5


0(0)


M


0(0)


1


2


3


4


0


6


4


5


4


1


0(1)


M


0(0)


0(0)


0(0)


0(0)


0


7


3


4


3


2


1


0(0)


M


0(0)


0(0)


0(0)


0


8


2


3


2


3


2


0(0)


0(0)


M


0(0)


0(0)


0


9


1


2


1


4


3


0(0)


0(0)


0(0)


M


0(0)


0


10


0(1)


1


0(0)


5


4


0(0)


0(0)


0(0)


0(0)


M


0


dj


1


1


0


0


1


0


0


0


0


0


0


d(1,2) = 1 + 1 = 2; d(2,3) = 1 + 0 = 1; d(3,4) = 1 + 0 = 1; d(4,10) = 1 + 0 = 1; d(5,4) = 0 + 0 = 0; d(5,6) = 0 + 0 = 0; d(6,5) = 0 + 1 = 1; d(6,7) = 0 + 0 = 0; d(6,8) = 0 + 0 = 0; d(6,9) = 0 + 0 = 0; d(6,10) = 0 + 0 = 0; d(7,6) = 0 + 0 = 0; d(7,8) = 0 + 0 = 0; d(7,9) = 0 + 0 = 0; d(7,10) = 0 + 0 = 0; d(8,6) = 0 + 0 = 0; d(8,7) = 0 + 0 = 0; d(8,9) = 0 + 0 = 0; d(8,10) = 0 + 0 = 0; d(9,6) = 0 + 0 = 0; d(9,7) = 0 + 0 = 0; d(9,8) = 0 + 0 = 0; d(9,10) = 0 + 0 = 0; d(10,1) = 0 + 1 = 1; d(10,3) = 0 + 0 = 0; d(10,6) = 0 + 0 = 0; d(10,7) = 0 + 0 = 0; d(10,8) = 0 + 0 = 0; d(10,9) = 0 + 0 = 0;

Найбільша сума констант приведення дорівнює (1 + 1) = 2 для ребра (1,2), отже, безліч розбивається на дві підмножини (1,2) i (1*,2*).

Нижня межа гамільтонових циклів цього підмножини:

H(1*,2*) = 3 + 2 = 5

Виняток ребра (1,2) проводимо шляхом заміни елемента d12 = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (1*,2*), в результаті отримаємо скороченої матрицю.

i j


1


2


3


4


5


6


7


8


9


10


di


1


M


M


1


2


3


4


5


6


7


8


1


2


7


M


0


1


2


3


4


5


6


7


0


3


7


8


M


0


1


2


3


4


5


6


0


4


6


7


6


M


5


4


3


2


1


0


0


5


5


6


5


0


M


0


1


2


3


4


0


6


4


5


4


1


0


M


0


0


0


0


0


7


3


4


3


2


1


0


M


0


0


0


0


8


2


3


2


3


2


0


0


M


0


0


0


9


1


2


1


4


3


0


0


0


M


0


0


10


0


1


0


5


4


0


0


0


0


M


0


dj


0


1


0


0


0


0


0


0


0


0


2


Включення ребра (1,2) проводиться шляхом виключення всіх елементів 1-ої строки і 2-го стовпця, в якій елемент d21 замінюємо на М, для запобігання утворенню негамільтонова циклу.

В результаті отримаємо іншу скорочену матрицю (9 x 9), яка підлягає операції приведення.

Сума констант приведення скороченою матриці:
Після операції приведення скорочена матриця буде мати вигляд:

i j


1


3


4


5


6


7


8


9


10


di


2


M


0


1


2


3


4


5


6


7


0


3


7


M


0


1


2


3


4


5


6


0


4


6


6


M


5


4


3


2


1


0


0


5


5


5


0


M


0


1


2


3


4


0


6


4


4


1


0


M


0


0


0


0


0


7


3


3


2


1


0


M


0


0


0


0


8


2


2


3


2


0


0


M


0


0


0


9


1


1


4


3


0


0


0


M


0


0


10


0


0


5


4


0


0


0


0


M


0


dj


0


0


0


0


0


0


0


0


0


0


Нижня межа підмножини (1,2) дорівнює:

H(1,2) = 3 + 0 = 3 < 5

Оскільки нижня межа цієї підмножини (1,2) менше, ніж підмножини (1*,2*), то ребро (1,2) включаємо в маршрут.



<< предыдущая страница   следующая страница >>