ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 114
Скачиваний: 0
не будет полным склеиванием, так как кубы-операнды отмечены раз ными операторами, хотя и отличаются одной координатой.
Два отмеченных куба crYl — (аи . . . , ап) Yt и csYm = (blt . . . , bn) Ym назовем противоположными гранями отмеченного куба cpY q, если сг и cs суть противоположные грани ср (все их координаты кроме
одной, например і, совпадают, |
а в /-координате сг и cs принимают |
про |
||||||
тивоположное значение), |
а |
Y q = XiY[Ym, если |
щ = 1, |
Ь{ = |
0, и |
|||
Yq = xtYmYh если |
щ = |
0, Ь{ = |
1. |
|
|
|
|
|
Определим отношение покрытия для пары одинаково отмеченных |
||||||||
кубов crYm и cpYm. Будем говорить, что c Y m покрывает |
<? |
Ym, |
или |
|||||
cpYm покрывается |
кубом |
сгYт |
(срYт С с Ym), |
если с |
покрывает |
|||
ср (ср С сг) [17], т. |
е. (? |
является гранью сг. Очевидно, |
что отноше |
|||||
ние покрытия рефлексивно, транзитивно и антисимметрично: |
|
|||||||
|
|
|
й С а; |
|
|
|
|
|
|
(а С Ь) и (Ь С с) -ä- а С с; |
|
|
|
|
|||
аС1 |
Ь - + Ь ф а |
(кроме случая а — Ь). |
|
|
|
|||
Изложим теперь алгоритм получения некоторого множества равно сильных подграфов ГСА, из которых в дальнейшем решением задачи покрытия определенного вида найдется подграф ГСА с минимальным числом условных вершин. Заранее оговоримся, что будем работать в классе граф-схем, у которых в одном пути вида (7-1) невстрётятся ус ловные вершины с одинаковыми логическими условиями. Причина введения такого ограничения очевидна, поскольку каждому пути вида (7-1) ставится в соответствие некоторый отмеченный куб, у которого одна координата соответствует одному логическому условию. Алго ритм будем иллюстрировать примером для подграфа Г на рис. 7-3 или покрытием D (У4), см. формулу (7-3), т. е. сначала рассмотрим ча стный случай с одним исходящим оператором, а затем перейдем к ми нимизации подграфов с несколькими исходящими операторами.
Предварительно в покрытий (7-3) произведем всевозможные пол ные склеивания. В нашем примере возможна лишь одна такая опера ция:
ѵ 001 КL
Л000 Y t
OCk Yj_'
После этого к покрытию (7-3) добавляем полученные в результате полного склеивания кубы и производим операцию поглощения, за ключающуюся в удалении всех кубов, которые покрываются другими кубами. В результате получаем некоторое покрытие D 0 (И4), или просто D 0, так как рассматривается, подграф с одним исходящим опе-
139
ратором (У4):
ОГѵ Y 2 100 у 2
|
о |
|
|
|
О |
Уг |
|
и х |
||
Y з |
||
101 |
У1 2 |
(7-6)
Будем такое покрытие изображать следующим образом:
ОГѵ 2 |
|
100 |
2 |
00х |
1 |
1 \х |
3 |
101 |
12 |
Первичные операторы, отмечающие кубы в покрытии |
D 0, обозна |
чим через G„. Для покрытия (7-6) G0 = (1Д, Y«, Ya, |
K12].- Если |
D 0 = D (Yj) — случай одной формулы перехода, то G0 — входящие операторы для Yf (при разбиении ГСА на подграфы они обозначались через В (Yf).
Алгоритм получения равносильных подграфов ГСА содержит не более п шагов, где а — размерность входящих в покрытие кубов.
Первый шаг. |
К каждой паре кубов {cYi„ |
csF,„ö) из |
D t) |
применим |
||
операцию х . В результате получим множество кубов |
— D 0 |
X Dg. 1 |
||||
|
0,ѵ,ѵ |
20 |
|
|
|
|
|
X \х |
21 |
|
|
|
|
|
*00 |
22 |
|
|
|
|
|
1 jcO |
23 |
|
|
|
|
|
10х |
24 |
|
|
|
|
|
xOl |
25 |
|
|
|
|
|
\ х \ |
26 |
|
|
|
|
Производные |
операторы (Y = x . Y f Y ^ |
записываем |
в |
отдель |
||
ную таблицу (табл. 7-2), где в первый столбец помещаем индекс qlt
Таблица 7-2
Производные операторы на первом шаге
20 |
х2 |
2 |
|
21 |
А 'і |
3 |
|
22 |
•Ѵ1 |
2 |
2 |
23 |
Л’2 |
3 |
|
24 |
*3 |
12 |
2 |
25 |
*1 |
12 |
1 |
26 |
Хг, |
3 |
12 |
в0 ВТ0Р°й — переменную xit по которой произошло склеивание, в тре
тий и четвертый — индексы операто ров /0 и т 0 соответственно:
IX; I/„ I т 01.
В каждом кубе H3 D X подчеркнем ту координату, по которой про-
1 Нумерация производных кубов начата с 2.0.
140
изошло склеивание при получении этого куба. Например:
01* У2
00* ѵ
*оУ.Уі>
0 X X } 20
или, что то лее самое,
0**| 20; 201л:312 I 1.
К множеству D 1 добавляем кубы D'QС D0, имеющие ранг не ниже единицы:
01* 2
D'o = 00* 1
11* 3
Получаем множество D 1 = D x U D0
01* 2
00* 1
11* 3
о** 20
* 1* 21
22 ‘
1*0 23
10* 24
*o7 25
i* i 26
В D 1 делаем всевозможные поглощения (здесь их нет). Табл. 7-2 задает некоторую функцию /у, определенную в множестве троек (*., Yt , Y т ) и принимающую значения в множестве производных опе
раторов бі> отмечающих кубы в D l t (*(. |
£ X; Y ^ Y nh |
£ |
G0). |
Каж |
|
дому элементу У £ Gx соответствует |
подграф |
ГСА, |
аналогичный |
||
рис. 7-4 и содержащий одну условную вершину. |
|
|
|
|
|
Если G0 и Gx — множества операторов, отмечающих кубы в покры |
|||||
тиях D0 и Dx соответственно, то Gx = Gx U Go- |
2, . . . , |
п) первым |
|||
Замечание. На последующих р шагах (р = |
|||||
действием на каждом шаге будет операция D |
, X Dp_ r |
При |
этом |
||
запретим выполнение этой операции над такими парами кубов d Y t х ,
сяУШр_і из D j, у которых в одном из них і-координата равна под черкнутому * (*), а в другом она равна 0 или 1 (связана). Например,
на втором шаге не будет выполняться операция X над парой кубов 11* |3 и 0**| 20. Очевидно, что после такого замечания мы будем ра
141
ботать в классе граф-схем, у которых в одном и том же пути между двумя операторными вершинами не могут встретиться две или более условные вершины с одинаковыми логическими условиями, что было уже оговорено выше.
Выполнив на 2-м шаге операцию D x X D lt получим D 2 = D x X X D x, D j = D s U D[ (Di — множество кубов из D x ранга не ниже 2),
G2 = |
G2 и Gi и таблицу |
функции |
/ 2, |
заданную |
в множестве троек |
|||||
(лх, |
Y !, Y т ) |
и принимающую |
значения |
в множестве G2. После этого |
||||||
в D 2 |
делаем всевозможные поглощения. |
Для нашего примера имеем: |
||||||||
|
|
|
|
|
|
|
|
|
Oxx |
20 |
|
|
0 хх |
20 |
|
|
|
|
|
xlx |
21 |
|
|
|
|
|
|
|
xxO |
27.29 |
||
|
|
X \х |
21 |
|
|
|
|
|
||
|
|
|
|
|
|
|
XX1 |
28.30 |
||
|
D2 = |
х.ѵО |
27,29 |
|
Oxx |
20 |
Do = |
|||
|
хх 1 |
28,30 ’ |
Dl = xlx |
21 |
xOx |
31.33 • |
||||
|
|
X0.г 31,33 |
|
|
|
|
|
\xx |
32.34 |
|
|
|
1XX |
32,34 |
|
|
|
|
|
Oxx |
20 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
x\x |
21 |
После поглощения в D.,: |
|
|
|
|
|
|
||||
|
|
|
|
|
Oxx |
20 |
|
|
|
|
|
|
|
|
|
xlx |
21 |
|
|
|
|
|
|
|
D ,= |
xxO |
27,29 |
|
|
|||
|
|
|
XX1 |
28,30' |
|
|
||||
|
|
|
|
|
xOx |
31,33 |
|
|
||
|
|
|
|
|
Ixx |
32,34 |
|
|
||
|
|
28, 29, |
30, |
|
|
|
ö 2 = D2 U ö i ; G2 = G2 U Gr. |
/2 задана |
табл 7-3. |
|
|||
Продолжая аналогично на /г-м шаге (h = |
1, |
. . . , Я; Я<7г), |
по |
|||
лучим Dh, |
Gh и таблицу функции fk, |
заданную |
в множестве троек |
|||
|Х;, Yih_ v |
Y mh_ l’) |
и принимающую значение в множестве Gh. |
|
|||
Очевидно, что спустя Я шагов (Я |
/г) D H |
будет содержать только |
||||
■. |
/г-кубы |
(хх . . . х). Это следует |
из |
т |
= I |
|
отмеченные |
того, что \ / aft |
|||||
[см. формулу (7-2)], и из утверждения (доказательство опущено), что1
1 В множествах Gl. 6 2 и т. п. вместо У; записываем индекс і. В множестве D2 кубы J Y іг и âYmr при cr— cs записываются в виде cr\lr, тг.
142
на h-м шаге Dh содержит все отмеченные Л-кубы или их Сограни. Ясно, что алгоритм содержит не более п шагов.
Продолжая пример, на третьем (последнем) шаге получим:
Ьз = \ххх \ 35, 36, 37, 38, 39, 40, 41, 42; D2 = 0 ', D3 = D3,
/з приведена в табл. 7-4.
|
|
Таблица 7-3 |
|
|
|
Таблица 7-4 |
||
Производные операторы |
Производные операторы |
|||||||
|
на втором шаге |
|
|
на третьем |
шаге |
|
||
20 |
Ч |
2 |
|
35 |
*3 |
|
28 |
27 |
2 |
36 |
Ч |
|
30 |
27 |
|||
21 |
Ч |
3 |
37 |
Ч |
|
28 |
29 |
|
27 |
хі |
23 |
20 |
38 |
ч |
. |
30 |
29 |
28 |
хі |
26 |
20 |
39 |
ч |
21 |
31 |
|
29 |
*2 |
21 |
22 |
40 |
ч |
|
21 |
33 |
30 |
*2 |
21 |
25 |
41 |
ч |
|
32 |
20 |
31 |
х3 |
25 |
22 |
42 |
|
|
34 |
20 |
32 |
х3 |
26 |
23 |
ч |
|
|||
33 |
Х1 |
24 |
1 |
|
|
|
|
|
34 |
Ч |
3 |
24 |
|
|
|
|
|
На последнем, Я-м, шаге имеем покрытие DH, кубы которого от мечены операторами из множества GH. Пусть
Y h ). Как и ранее,
(*<• г , я _ „ П ,„ _ ,) 'д г „ .
Поскольку в DH входят только кубы размерности п (хх . . . х), очевидно, что из Yf (исходящая Операторная вершина — в нашем примере Y4) в операторы GH ведет путь, содержащий
пустое множество условных вершин, т. е. имеет место совпадение Yf с каждым из операторов, входя
щих в GH. Представляя оператор YrH в виде хгК,я_ і;
Утн-і |
(функция fH), придем к рис. |
7-5. Раскрывая |
|
|
|
||||||||
У і н - Ѵ |
|
Y mH - l |
И т - Д- С П О М О Щ Ь Ю ф у Н К Ц И Й /я _,, |
|
|
|
|||||||
fн |
21 |
• |
• • > /і> |
спустя |
не |
более |
Я |
шагов |
придем |
|
|
|
|
к первичным операторам из множества G0. В ре |
Рис. 7-5. Иллю |
||||||||||||
зультате получим один вариант реализации подграфа |
|||||||||||||
ГСА, |
определяемого покрытием Ь 0 |
{Yf). Так |
как GH |
страция совпа |
|||||||||
содержит R элементов, |
проделав подобную процедуру |
дения операто |
|||||||||||
ров |
Yf и |
Угң |
|||||||||||
R |
раз для каждого из Y lH, . |
. . , Уң, можно построить |
|||||||||||
|
|
|
|||||||||||
R |
равносильных подграфов. |
Например, начав с Y 3e в табл. |
7-4, |
при |
|||||||||
дем к ГСА, изображенной на рис. 7-6. |
Так как в D 3 всего 8 кубов, от |
||||||||||||
меченных операторами У35—Y42, возможны 8 вариантов граф-схем, |
|||||||||||||
реализующих |
покрытие D 0 |
(Y4). Эти |
варианты сведены в табл. |
7-5, |
|||||||||
каждый столбец которой получен последовательным раскрытием опе раторов с помощью функций /з, / 2 и /у. Первичные операторы в таб лицу вариантов не включаются.
143