| Home / lib / M_Mathematics / | ||
Doklady Odesskogo seminara po diskretnoj matematike, vyp.1 (Astroprint, 2004)(ru)(KA)(600dpi)(T)(57s)_M_.djvu |
|
Size 0.7Mb Date Feb 3, 2004 |
подается специальный граф S = S(G) = (С/, К), в котором вершины
первой доли перенумерованы индексом q=l9 2, ..., L19 т.е...
С учетом дольности под-
подграфа Sq таблица Tq естественным образом разбивается на час-
части Tq,k = l> 2, ..., 771, где часть Т£ состоит из всех таких строк,
которые соответствуют вершинам одной и той же доли JJI тп-
дольного подграфа Sq...
Условимся, что
термин "пересечение МС строк i9 у" означает новую строку,
состоящую из т множеств (TlknTJk), для каждого fe = 1, 2, ...,
т...
Аналогично
необходимое условие 2 не выполняется для строки 7 в
таб.2...
Нетрудно видеть, что трудоемкость алгоритма ах ог-
ограничена сверху полиномом от размерности подграфа Sq...
Если на подэтапе (t + 1) алгоритма
ах строка i = t + 2 вошла в состав тупиковой таблицы МС Т ,
то это означает, что в каждой из остальных частей Tk для
нее существует хотя бы одна строка у, имеющая непустое пе-
пересечение МС со строкой i, т.е...
В процессе построения тупиково-
тупикового подграфа SQ для каждой строки таблицы осуществляется
не более
Uq
операции поэлементарного сравнения и вычер-
вычеркивания в таблице Tq некоторых строк...
На выходе алгоритма ос2 формируется множество клик
размерности ттг, которое определяет собой МДР X = X(G) за-
задачи о совершенных сочетаниях на гиперграфе...
Из множества Щ+2 пос-
последовательно выбираются клики геа+2 = {ejj7, ..., eqr, ..., е89+2}, в
каждой их которых имеется по одному представителю от
каждой из последних (s + 2) долей, т...
Для принятого терм-множества
С/ = {#, С, В} теоретически возможное количество различных
^-конфигураций, £=*19 2, ..., L, составляет Z3 = 3 + З2 + З3+
34 + З5 + .....
Для фиксированного
£е {1, 2, ..., L) элементы множества Ме всех ^-конфигураций
в ЛВР A) нумеруем индексом г= 1, 2, ..., Ni9 Nt = |М^|, а эле-
элементы терм-множества U = {и} нумеруем индексом s = l, 2,
..., Л^о, iV0=|C/|...
Рассматри-
Рассматривая последовательность (9), обнаруживаем в ней такое наи-
наименьшее значение £ = L0, для которого звезда ZrL имеет
лишь одну дугу е° = (rL0, s°)g £L ненулевого веса w(e°)^0
(остальные No- 1 дуг этой звезды имеют нулевой вес)...
| © 2007 eKnigu | ||