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

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

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

i j


1


5


6


7


8


9


di


5


4


M


0(1)


1


2


3


1


6


3


0(1)


M


0(0)


0(0)


0(0)


0


7


2


1


0(0)


M


0(0)


0(0)


0


8


1


2


0(0)


0(0)


M


0(0)


0


9


0(1)


3


0(0)


0(0)


0(0)


M


0


10


M


4


0(0)


0(0)


0(0)


0(0)


0


dj


1


1


0


0


0


0


0


d(1,3) = 1 + 0 = 1; d(2,2) = 0 + 1 = 1; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 0 = 0; d(2,6) = 0 + 0 = 0; d(3,3) = 0 + 0 = 0; d(3,5) = 0 + 0 = 0; d(3,6) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(4,4) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,1) = 0 + 1 = 1; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0; d(5,5) = 0 + 0 = 0; d(6,3) = 0 + 0 = 0; d(6,4) = 0 + 0 = 0; d(6,5) = 0 + 0 = 0; d(6,6) = 0 + 0 = 0;

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

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

H(5*,6*) = 3 + 1 = 4

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

i j


1


5


6


7


8


9


di


5


4


M


M


1


2


3


1


6


3


0


M


0


0


0


0


7


2


1


0


M


0


0


0


8


1


2


0


0


M


0


0


9


0


3


0


0


0


M


0


10


M


4


0


0


0


0


0


dj


0


0


0


0


0


0


1


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

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

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

i j


1


5


7


8


9


di


6


3


M


0


0


0


0


7


2


1


M


0


0


0


8


1


2


0


M


0


0


9


0


3


0


0


M


0


10


M


4


0


0


0


0


dj


0


1


0


0


0


1


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

H(5,6) = 3 + 1 = 4 < 4

Щоб виключити підцикли, заборонимо наступні переходи: (10,1), (10,2), (10,3),

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

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

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

i j


1


5


7


8


9


di


6


3


M


0(0)


0(0)


0(0)


0


7


2


0(1)


M


0(0)


0(0)


0


8


1


1


0(0)


M


0(0)


0


9


0(1)


2


0(0)


0(0)


M


0


10


M


3


0(0)


0(0)


0(0)


0


dj


1


1


0


0


0


0


d(1,3) = 0 + 0 = 0; d(1,4) = 0 + 0 = 0; d(1,5) = 0 + 0 = 0; d(2,2) = 0 + 1 = 1; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 0 = 0; d(3,3) = 0 + 0 = 0; d(3,5) = 0 + 0 = 0; d(4,1) = 0 + 1 = 1; d(4,3) = 0 + 0 = 0; d(4,4) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0; d(5,5) = 0 + 0 = 0;

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

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

H(7*,5*) = 4 + 1 = 5

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

i j


1


5


7


8


9


di


6


3


M


0


0


0


0


7


2


M


M


0


0


0


8


1


1


0


M


0


0


9


0


2


0


0


M


0


10


M


3


0


0


0


0


dj


0


1


0


0


0


1


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

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

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

i j


1


7


8


9


di


6


3


0


0


0


0


8


1


0


M


0


0


9


0


0


0


M


0


10


M


0


0


0


0


dj


0


0


0


0


0


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

H(7,5) = 4 + 0 = 4 < 5

Щоб виключити підцикли, заборонимо наступні переходи: (10,1), (10,2), (10,3), (6,7),

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



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