j i | 1 | 2 | 3 | 4 | 5 | 6 |
1 | ∞ | 5 | 14 | 19 | 0 | 15 |
2 | 0 | ∞ | 8 | 2 | 30 | 10 |
3 | 22 | 0 | ∞ | 28 | 14 | 6 |
4 | 3 | 0 | 17 | ∞ | 23 | 2 |
5 | 7 | 0 | 17 | 12 | ∞ | 49 |
6 | 37 | 12 | 0 | 4 | 18 | ∞ |
Vj | 0 | 0 | 0 | 2 | 0 | 2 |
3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.
Табл.2
j i | 1 | 2 | 3 | 4 | 5 | 6 |
1 | ∞ | 5 | 14 | 17 | 019 | 13 |
2 | 03 | ∞ | 8 | 02 | 30 | 8 |
3 | 22 | 04 | ∞ | 26 | 14 | 4 |
4 | 3 | 00 | 17 | ∞ | 23 | 04 |
5 | 7 | 07 | 17 | 10 | ∞ | 47 |
6 | 37 | 12 | 08 | 2 | 18 | ∞ |
4) Находим константу приведения
Таким образом, нижней границей множества всех гамильтоновых контуров будет число
5) Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак «∞» и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых 
.
6) Определяем максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким образом, претендентом на включение в гамильтонов контур является дуга (1;5).
7) Разбиваем множество всех гамильтоновых контуров 
на два: 
и 
. Матрицу с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «∞».
j i | 1 | 2 | 3 | 4 | 6 |
2 | 0 | ∞ | 8 | 0 | 8 |
3 | 22 | 0 | ∞ | 26 | 4 |
4 | 3 | 0 | 17 | ∞ | 0 |
5 | ∞ | 0 | 17 | 10 | 47 |
6 | 37 | 12 | 0 | 2 | ∞ |
8) Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента (1;5) на знак «∞».
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
