Град 14452 шифр 01. На территории города имеется три телефонных станции А, б и В. Незадействованные емкости станций составляют на станции а q

• Название: На территории города имеется три телефонных станции А, б и В. Незадействованные емкости станций составляют на станции а q
• Дата: 13.10.2022
• Размер: 207.93 Kb.
• Имя файла: Град 14452 шифр 01.docx
• Тип: Задача; #731545
• страница: 3 из 4

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. После операции приведения матрица примет вид:

i j	1	2	3	5	6	di
1	М	1	0	5	1	0
2	2	М	1	0	6	0
3	0	1	М	6	0	0
4	8	11	12	М	6	6
6	3	7	0	6	М	0
dj	0	1	0	0	0

i j	1	2	3	5	6	di
1	М	0	0	5	1	0
2	2	М	1	0	6	0
3	0	0	М	6	0	0
4	2	4	6	М	0	0
6	3	6	0	6	М	0
dj	0	0	0	0	0

Чтобы исключить подциклы, запретим следующие переходы: (4,5).

Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*,4*), то ребро (5,4) включаем в маршрут.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j	1	2	3	5	6	di
1	М	0(0)	0(0)	5	1	0
2	2	М	1	0(6)	6	1
3	0(2)	0(0)	М	6	0(0)	0
4	2	4	6	М	0(2)	2
6	3	6	0(3)	6	М	3
dj	2	0	0	5	0

Наибольшая сумма констант приведения равна (5+1) = 6 для ребра (2,5), следовательно, множество разбивается на два подмножества (2,5) и (2*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:

i j	1	2	3	5	6	di
1	М	0	0	5	1	0
2	2	М	1	М	6	1
3	0	0	М	6	0	0
4	2	4	6	М	0	0
6	3	6	0	6	М	0
dj	0	0	0	5	0

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

После операции приведения сокращенная матрица будет иметь вид:

i j	1	2	3	6	di
1	М	0	0	1	0
3	0	М	М	0	0
4	2	4	М	0	0
6	3	6	0	М	0
dj	0	0	0	0

Чтобы исключить подциклы, запретим следующие переходы: (3,2), (4,3)

Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*,5*), то ребро (2,5) включаем в маршрут.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j	1	2	3	6	di
1	М	0(4)	0(0)	1	0
3	0(2)	М	М	0(0)	0
4	2	4	М	0(2)	2
6	3	6	0(3)	М	3
dj	2	4	0	0