Практикум по дисциплине «Дискретная математика»
жүктеу/скачать 0,98 Mb.
|
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)
- Бұл бет үшін навигация:
- Матрица С
Сумма констант приведения матрицы С1,1 здесь равна 1, поэтому (Г{(1,4)})={1,4}=14+1=15. Сопоставим результат (Г{(i,j)}) множеству Г{(i,j)}, (в нашем случае Г{(1,4)}). Множеству  (в нашем случае  ), в свою очередь, соответствует другая матрица – С1,2, полученная заменой на элемент с1,4 в матрице С1:
Сумма констант последнего приведения равна 4, так что  .
Теперь выберем между множествами  и  то, на котором минимальна функция . В нашем случае из множеств, которому соответствует меньшее из чисел (Г{(1,4)})=15 и  . Поэтому дальнейшей разработке подвергнется множество Г{(1,4)}.
Итак, выделена определенная дуга (1,4) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл (цикл коммивояжёра), если данная ветвь будет продолжена до конца и иметь минимальный вес. В матрице С1,1 подсчитаем веса нулей (веса нулей указаны в скобках):
Самым тяжёлым является нуль с номером (4,3), так что теперь следует рассматривать множества  и  .
Обратимся к первому из них. Поскольку, вычеркнув строку 4 и столбец 3 в матрице С1,1, нужно также заменить на числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (3,1) надо поставить символ . Получим матрицу С1,1,1:
жүктеу/скачать 0,98 Mb. Достарыңызбен бөлісу:
|