Введение в прикладную комбинаторику, Кофман А. (984071), страница 38
Текст из файла (страница 38)
256. Здесь нара дуг заменена двойной стрелкой. Рнс. 257. 301 Е решений, которое берется в качестве корня прадерева (см, стр. 299). В) Выбираем дугу (Ха, Х~), для которой 0 (Ха, Х,) = гпах у (Хн Х ), (54.1) н! где у(Х,, Х;) — сумма наименыиего элемента 1-й строки (исключая о'(Хь Х,)) и наименыиего элемента 1-го столбца (исключая о'(Хь Х,)), которая вычисляется для 1 и 1' с о'(Х;, Х,) = О.
Рассмотрим свойство Уц. «контур не использует дуги (ХьХ,)», которое будет применяться к дугам с о'(Хь Хз) = О; оно позволяет осуществить нужные нам разбиения (ем. стр. 299). Если гамильтонов контур не использует такой дуги (Хь Х„), то он должен использовать некоторые две дуги (Х;, Х,), з Ф1, и (Х„, Х,), г М( (иначе он не проходил бы по крайней мере через одну из вершин Х;, Х;; см. рис. 258).
Г) Вычисляем 0(Хы Х~) по Формуле (54.1) и прибавляем его к границе, соответствующей вершине прадерева, исходя из которой производится разбиение. Эта сумма будет границей для новой вершины, определяемой свойством Уаь которую соединяем дугой, идущей в нее из укаэанной выше вершиньи Д) Аналогично Г) присоединяем к прадереву вершину, определяемую свойством Яы. «контур использует дугу (Ха, Х~)». Удалилг из матрицы й-ю строку и 1-й столбец и заменим на оо.
значения тех дуг, используя которые, получают контуры длины, меньшей и. Е) Действуем, как в А), с матрицей, получающейся в результате Д), Ж) Действуем, как в Б), с матрицей, получающейся в результате Е), Прибавляя полученную сумму к границе для предыдущей вершины, получаем границу для вершины из Д). 3) Если в результате Д) получают матрицу порядка 1, то процесс заканчивается. В противном случае переходим к И). И) Среди висячих вершин уже построенного прадерева выбираем вершину с наименьшей границей (если таковых несколько, выбираем произвольно). Риа 258.
К) Если выбранная по И) вершина соответствует свойству УО, то переходим к В). В противном случае переходим к Л), Л) Значение в клетке (й 1) матрицы, соответствующей висячей вершине, всчбранной в К), заменяем на со, В 1-й строке, а также в 1'-м столбце находим наименьший элемент и вычитаем его из всех элементов этой строки (столбца). Затем переходим к В).
П р и м е р. Опишем построение прадерева на рис. 259, дающего минимальный гамильтонов контур графа па рис. 256, согласно алгоритму, изложенному выше. А) Из элементов строк Хь Хь Хм Х,, Хм Хы Хт матрицы на рис. 257 вычитаем соответственно нх наименьшие элементы: 3, 2, 1, 2, 2, 2, 1, а также вычитаем 2 из всех элементов столбца Хь Получаем на рис. 260 матрицу. Б) Вычисляем сумму: 3+ 2+ 1+ 2+ 2+ 2+ 1+ 2 = 15. Получаем для Е на рис. 259 границу, равную 15. В) Рассмотрим все пулевые элементы матрицы на рис. 260 (воспроизведенной также на рис. 261 — выкладки для вершины 2 прадерева). Возьмем 0 в клетке (1, 5). Если исключить его, то 2 — наименьший элемент строки Хь а также столбца Хы Имеем у(Хь Хэ) = 2+ 2 = 4.
Это значение записываем в клетке (1, 5) курсивом, чтобы отличить от ом. Берем затем 0 в клетке (Хм Х,). Если исключить элемент в этой клетке, то 3 — наименьший элемент в строке Хм а ! — в столбце Х,. Имеем у(Хт, Х,) = 3+ 1 = 4 302 Х1 Ха Хз Хт Хз Ха Хт Х1 Хх Хз Ха Хз Ха Хт х, 3 х, 2 Хз 1 Хз 2 Хт 2 Хз 2 Ха Хт Ха Хз Х4 Ха Хт Сумма 1Б Рис 26!. Рис 260. Рис. 259 Порядок, в котором строились вершины, указывают цифры в круаы ка х 1, 2, 2', 3, 3', ..., ! О, ! О'. Аналогичззо У(Ха, Х4) = — О+ О = О, У(Ху, Хз) = 2+ О = 2. Выбираем дугу (Хм Ху), так как у(Х„Ху) максимально.
Это значение у(Хм Ху) записываем полужирным шрифтом в соответствующей клетке. Г) Изображаем вершину Ез, прадерева (рис. 259) и приписываем ей значение 15+ 4 = 19. Х~ Хз Хз Х4 Хз Хз Х, х, Х, Хг Хз Х4 зе еХ Ху Рис 262. Д) Изображаем вершину Езу. Исключая строку Х, и столбец Х, в матрице на рис. 261, получаем матрицу на рис. 262. Рассматривая уже выбранные дуги (в нашем случае дугу с (Хм Ху)), видим, что иуз надо заменить на оо, так как иначе получился бы контур (Х,, Хь Хз).
Х1 Хз Хз Х4 Хз Хз Хз Хз Х4 Хз Зз Х, Хз Х„ Х, Х, Хз 2 Ху Сумма 2 Рис. 264. Рис. 263. 304 Е) Рассматривая матрицу на рис. 262, видим, что нужно только вычесть 2 из строки Ху, что приводит к матрице на рис. 263 (выкладки для вершины 2' прадерева). Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 2. Следовательно, для вершины Езу имеем границу: 15+ 2 = 17. 3) Имеем лзатрицу порядка 6, поэтому переходим к И). И) Висячая вершина с наилзеньшим значением, равным 17, есть Езу К) Е„получалась с помощью йдсь Переходим к В). В) Рассматривая матрицу на рис. 264 и вычисляя у(Хь Х,) пля нулевых элементов этой матрицы, получаем, что 0(Хь Хз) = = 4 (на рисунке выкладки для вершины 3 прадерева).
Г) Строим вершину Ем П Епь которой отвечает граница 17 + 4 = 21. Х ХсХиХиХс Х4 Хи х, Рис. 266. Х1 Хс Хз Х4 Хс Х~ Хс Хс Х4 Хс х Хс Х7 1 Х, Рис 266. Рис. 267. Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 1. Следовательно, для вершины Ем П Еы имеем границу !7+ 1 = 18.
3) Имеем матрицу порядка 5, поэтому переходим к И). И) Висячая вершнна с наименьшим значением, равным 18, есть Ем П Ем К) Е,„Г) Еы получалась с помощью Ум Переходим к В). В) Рассматривая матрицу на рис. 267 н вычисляя у(Хь Х,) для нулевых элементов этой матрицы, получаем, что О(Хм Х,)=4. 606 Д) Строим вершину Ем П Епи Вычеркивая строку Х1 и столбец Хс матрицы на рис.
264, приходим к матрице на рис. 265, в клетку (Хм Х1) которой ставим ос, чтобы не получить контура (х,х,х). Е) Рассматривая матрицу на рис. 265, видим, что из всех элементов столбца Х, нужно только вычесть 1, что приводит к матрице на рис. 266 (выкладки для вершины 3' прадерева). Г) Строим вершину Ем П Е~ь П Еев которой отвечает граница 18+ 4 = 22. Д) Строим вершину Ем Й Ем П Еь,, Вычеркивая строку Хь и столбеп Хз матрицы на рис.
267 (выкладки для вершины 4 прадерева), приходим к матрице на рис. 268, в клетку (Ху, Хь) которой ставим ос, чтобы пе получить контура (Х,, Хз, Х,, Хь), Х~ Хз Хь Хь Х, Х~ Хз Хь Хь Хз Х з Х4 Хь Хь Ху Ху 2 Рис 269. Рис. 266 Е) Рассматривая матрицу на рис. 268, видим, что нужно только вычесть 2 из всех элементов столбца Хь что приводит к следующей матрице на рис. 269 (выкладки для вершины 4 прадерева). Ж Хз Хз Х4 Хз Хь Ху Х~ Ху Хз Хь Хз Хь Ху х, Хз х, Хз Хз х„ х, Хь Хь Ху Хь Ху Рис 271.
Рис. 270. Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 2. Следовательно, для вершины Е„П Е~ь П Еьз имеем границу 18 + 2 = 20. 3) Имеем матрицу порядка 4, поэтому переходим к И). И) Висячая вершина с наименьшим значением, равным !9, есть Езу, К) Ез, получалась с помощью Узу. Переходим к Л). Л) В клетку (Хь Ху) матрицы на рис. 261 ставим сс, что приводит к матрице на рис 270. Затем вычитаем 3 из всех элемен- 306 тов строки Хз и 1 из всех элементов столбца Хь что приводит к матрице на рнс. 271.
В) Рассматривая матрицу на рис, 271 и вычисляя у(Хн Х;) для нулевых элементов этой матрицы, получаем, что О(Хм Хз) = = 2 (клетки (Хь Хз) и (Х,, Хз) также дают это значение). Г) Строим вершину Е„П Ееп которой отвечает граница 19+ 2 = 21. Х~ Хз Хз Хз Хз Хт хз Хт Х б ФХ ХБ б Хз '1би "з Хт Рис. 272. Д) Строим вершину Езт П Ееи Вычеркивая строку Х» и столбец Х, матрицы на рис.
271, приходим к матрице на рис. 272, в клетку (Х,, Х4) которой ставим со. Е) Рассматривая матрицу на рис. 272, видим, что в каждой ее строке и каждом столбце есть по крайней мере один нулевой элемент, Х1 Хз Хз Х4 Хз Хт Х| Хз Хз Хз Хт х 'зг Хз Х1 Хз Хз 'Хз Хз Хз Хз Хт Хт Рис. 273.
Рис 274. Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна О. Следовательно, для вершины Езт П Е4, имеем границу 19 + О = 19. 3) Имеем матрицу порядка б, поэтому переходим к И). И) Висячая вершина с наименьшим значением, равным 19, есть Езт П Езз. К) Езт () Е„, получалась с помощью Узз, Переходим к В). 307 В) Рассматривая матрицу на рнс. 273 и вычисляя у(Хь Х;) аля нулевых элементов этой матрицы, получаем, что 0(Хь Х,) = = 2 (клетка (Х,, Хз) дает то же значение). Г) Строим вершину Е„Д Етая Егя которой отвечает граница 19+ 2 = 21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
