OK-metodichka-2010-part2 (1132793), страница 12
Текст из файла (страница 12)
Âýòîì ñëó÷àå íåðàâåíñòâî (9.2) èìååò âèä F > Fb00 , ãäå ìàòðèöà Fb 00 ïîëó÷àåòñÿ èç ìàòðèöû F 00 â ðåçóëüòàòå ïîðàçðÿäíîé äèçúþíêöèè ñòðîê, ñîîòâåòñòâóþùèõ îòîæäåñòâëÿåìûìâõîäàì ÊÑ Σ00 , è ïî-ïðåæíåìó ïåðåõîäèò â ðàâåíñòâî, åñëèÊÑ Σ00 ðàçäåëèòåëüíà ïî âõîäàì.  ïîñëåäíåì ñëó÷àå, êðîe 00 ,ìå òîãî, èç àíàëîãè÷íîãî ðàâåíñòâà, ñâÿçàííîãî ñ ÊÑ Σ00êîòîðàÿ ïîëó÷àåòñÿ èç ÊÑ Σ â ðåçóëüòàòå îáúÿâëåíèÿ ååe 00 , ñëåäóåò ðàçâõîäîâ âõîäàìè è, îäíîâðåìåííî, âûõîäàìè Σäåëèòåëüíîñòü ÊÑ Σ ïî âõîäàì.Çàìåòèì, íàêîíåö, ÷òî ñòûêîâêà îáùåãî âèäà Σ = Σ00 (Σ0 )ñâîäèòñÿ ê ïîñëåäîâàòåëüíîìóâûïîëíåíèþ îòîæäåñòâëåíèÿb 00 = Σ00 Σ̌00 è áåñïîâòîðíîé ñòûêîâêè âèäàâõîäîâ âèäà Σb 00 (Σb 0 ), ãäå ÊÑ Σ̌00 ñîñòîèò èç ïðîâîäÿùåé çâåçäû è òîæΣ=Σb 0 ïîëó÷àåòñÿ èç ÊÑ Σ0 ñíÿòèåìäåñòâåííûõ âåðøèí, à ÊÑ Σíåêîòîðûõ âûõîäîâ.
Ïðè ýòîì íåðàâåíñòâî (â ñëó÷àå ðàçäåëèòåëüíîñòè ÊÑ Σ00 ïî âõîäàì ðàâåíñòâî) (9.2) äëÿ ÊÑ Σ,Σ0 , Σ00 âûòåêàåò èç óñòàíîâëåííûõ âûøå àíàëîãè÷íûõ ñîîòb 00 , Σ̌00 , Σ00 è ÊÑ Σ, Σb 0, Σb 00 â ñèëó àññîöèíîøåíèé äëÿ ÊÑ Σàòèâíîñòè ïðîèçâåäåíèÿ ìàòðèö. Ñëó÷àé ðàçäåëèòåëüíîñòèÊÑ Σ0 ïî âûõîäàì ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Ëåììà äîêàçàíà. ñëó÷àå ðàçäåëèòåëüíîñòè ÊÑ Σ00 ïî âõîäàì â êàæäîé âåðøèíå ÊÑ Σ, Σ = Σ00 (Σ), êîòîðàÿ ñîîòâåòñòâóåò âûõîäó ÊÑ Σ0, ðåàëèçóåòñÿ òîò æå ñàìûé ñòîëáåöÔÀË, ÷òî è â ÊÑ Σ0, òî åñòü ðàññìàòðèâàåìàÿ ñóïåðïîçèöèÿ ÿâëÿåòñÿ êîððåêòíîé.Ñëåäñòâèå 1.Äåéñòâèòåëüíî, ïîëàãàÿ v 0 = a0i è v 00 = aj , ãäå i ∈ [1, p],à j ∈ [1, q], èç (9.4) ïîëó÷èì òðåáóåìîå ðàâåíñòâî f = fj0 .Ñëó÷àé ñòûêîâêè îáùåãî âèäà ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Ðàâåíñòâî (9.2) âûïîëíÿåòñÿ íà ëþáîì íàáîðå çíà÷åíèé ÁÏ, íà êîòîðîì ÊÑ Σ00 ðàçäåëèòåëüíà ïî âõîÑëåäñòâèå 2.10.Íåêîòîðûå ìîäèôèêàöèè îñíîâíûõ êëàññîâ ñõåì87äàì èëè ÊÑ Σ0 ðàçäåëèòåëüíà ïî âûõîäàì.10Íåêîòîðûå ìîäèôèêàöèè è ÷àñòíûå ñëó÷àèîñíîâíûõ êëàññîâ ñõåì (êàñêàäíûå ñõåìû,BDD, âû÷èñëÿþùèå ïðîãðàììû)Ðàññìîòðèì ñíà÷àëà ñïåöèàëüíûé ÷àñòíûé ñëó÷àé êîððåêòíîé ñóïåðïîçèöèè ÊÑ (ñì.
9) îïåðàöèþ ïðèñîåäèíåíèÿîäíîãî èëè äâóõ ïðîòèâîïîëîæíûõ êîíòàêòîâ, êîòîðàÿ çàêëþ÷àåòñÿ â ñëåäóþùåì. Ïóñòü (1, m)-ÊÑ Σ ïîëó÷àåòñÿ èç(1, m̌)-ÊÑ Σ̌ â ðåçóëüòàòå äîáàâëåíèÿ íîâîé âûõîäíîé âåðøèíû v , êîòîðàÿ ñîåäèíÿåòñÿ ñ âûõîäíûìè âåðøèíàìè v0 èv1 ÊÑ Σ̌ êîíòàêòàìè xi è xi ñîîòâåòñòâåííî (ñì. ðèñ. 10.1a).Òîãäà â âåðøèíàõ v0 è v1 ÊÑ Σ â ñèëó ðàçäåëèòåëüíîñòè ïîâõîäàì ïðèñîåäèíÿåìîé (2, 1)-ÊÑ ðåàëèçóþòñÿ òå æå ñàìûåÔÀË g0 è g1 , ÷òî è â ÊÑ Σ̌, à â âåðøèíå v ÔÀË g âèäàg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 .(10.1)Àíàëîãè÷íûå ñîîòíîøåíèÿ áóäóò ñïðàâåäëèâû è òîãäà,êîãäà âåðøèíà v ÊÑ Σ ñâÿçàíà ñ âåðøèíîé v òîëüêî îäíèìêîíòàêòîì âèäà xσi , σ ∈ {0, 1}, ñîåäèíÿþùèì åå ñ âåðøèíîé vσ (ñì.
ðèñ. 10.1b).  ýòîì ñëó÷àå â âåðøèíå v ÊÑ Σðåàëèçóåòñÿ ÔÀËg = xσi gσ .(10.2)Îïèñàííûå âûøå îïåðàöèè ïðèñîåäèíåíèÿ îäíîãî èëèäâóõ ïðîòèâîïîëîæåííûõ êîíòàêòîâ î÷åâèäíûì îáðàçîì ðàñïðîñòðàíÿþòñÿ íà ñëó÷àé ÊÑ ñ íåñêîëüêèìè âõîäàìè. Êðîìåòîãî, îíè äîïóñêàþò ìîäåëèðîâàíèå â êëàññå ÑÔÝ â áàçèñåÁ0 . Òàê, ïåðåõîä îò ÑÔÝ Ǔ , Ǔ ∈ UC , êîòîðàÿ ðåàëèçóåò ââûõîäíûõ âåðøèíàõ v0 è v1 ÔÀË g0 è g1 ñîîòâåòñòâåííî, êÑÔÝ U, U ∈ UC , êîòîðàÿ ðåàëèçóåò ÔÀË g , óäîâëåòâîðÿþùóþ (10.1) ((10.2)), ïîêàçàí íà ðèñ.
10.2a (ñîîòâåòñòâåííî88Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìqqqqq •QvQ0qqQQQxiqQQQqqq1 •qMMMM Σ̌mmm• vmMMMmm ximmMMM •MM v1qqqqqqqqxσiqqq•v1 •MqMMM Σ̌ • vσMMMMMMMMa)b)Ðèñ. 10.1: ïðèñîåäèíåíèå îäíîãî èëè äâóõ ïðîòèâîïîëîæíûõêîíòàêòîâ10.2b). Çàìåòèì, ÷òî ïðè ýòîì ðàçëîæåíèå (10.1) â ñëó÷àågσ ≡ 1 ýêâèâàëåíòíî ïðåäñòàâëåíèþg = xσi ∨ gσ ,ñõåìíàÿ ðåàëèçàöèÿ êîòîðîãî ïîêàçàíà íà ðèñ. 10.2c.Îïðåäåëèì, äàëåå,ÊÑ êàê ïðèâåäåííóþ ÊÑáåç èçîëèðîâàííûõ ïîëþñîâ, êîòîðàÿ ìîæåò áûòü ïîëó÷åíàèç ñèñòåìû òîæäåñòâåííûõ âåðøèí â ðåçóëüòàòå ðÿäà îïåðàöèé ïðèñîåäèíåíèÿ îäíîãî èëè äâóõ ïðîòèâîïîëîæíûõ êîíòàêòîâ è îïåðàöèé ïåðåèìåíîâàíèÿ âûõîäîâ.
Êàñêàäíàÿ ÊÑ(ÊÊÑ) ñ÷èòàåòñÿ, åñëè îíà áûëà ïîñòðîåíà áåç èñïîëüçîâàíèÿ îïåðàöèè ïðèñîåäèíåíèÿ îäíîãî êîíòàêòà. Òàê,íàïðèìåð, ÊÑ, ïîêàçàííàÿ íà ðèñ. 6.3c, ÿâëÿåòñÿ ïîëíîéÊÊÑ, åñëè å¼ âõîäàìè ñ÷èòàòü âåðøèíû a1 è v , à âûõîäàìè âåðøèíû a2 è a3 , èëè íàîáîðîò. Ê ÷èñëó ÊÊÑ îòíîñÿòñÿ òàêæå êîíòàêòíûå äåðåâüÿ, ïîêàçàííûå íà ðèñ. 6.4,ïðè÷åì (2n , 1)-ÊÄ ÿâëÿåòñÿ ïîëíîé ÊÊÑ.Çàìåòèì, äàëåå, ÷òî, â ñèëó êîððåêòíîñòè ðàññìàòðèâàåìûõ îïåðàöèé ïðèñîåäèíåíèÿ êîíòàêòîâ, ÊÊÑ ÿâëÿåòñÿ ðàçäåëèòåëüíîé ïî âõîäàì ÊÑ. Îòñþäà ñëåäóåò, ÷òî â êàæäîéâåðøèíå ÊÊÑ ðåàëèçóåòñÿ ñòîëáåö, â êîòîðîì íèêàêèå äâåÔÀË íå îáðàùàþòñÿ â åäèíèöó îäíîâðåìåííî, ïðè÷åì â ñëó÷àå ïîëíîé ÊÊÑ äèçúþíêöèÿ âñåõ ÔÀË ýòîãî ñòîëáöà äàåòêàñêàäíóþïîëíîé10.Íåêîòîðûå ìîäèôèêàöèè îñíîâíûõ êëàññîâ ñõåìxi••...
...••xi • ¬Ǔ•&v1 v0'z QQ•QQxσi•... ...89•Ǔ•vσ&•&•v(vl•$wQQQ∨ lllllv•l(va)b)•xσi•... ...•Ǔvσ•∨•v(vc)Ðèñ. 10.2: ê ìîäåëèðîâàíèþ îïåðàöèé ïðèñîåäèíåíèÿ êîíòàêòîâ â êëàññå ÑÔÝ90Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì1. Òàê, â ÷àñòíîñòè, â êàæäîé âåðøèíå ïîëíîé ÊÊÑ ñ äâóìÿ âõîäàìè ðåàëèçóåòñÿ ñòîëáåö èç äâóõ ïðîòèâîïîëîæíûõÔÀË.Âåðøèíà ÊÊÑ, ââåäåííàÿ â íåå ñ ïîìîùüþ îïåðàöèèïðèñîåäèíåíèÿ îäíîãî êîíòàêòà, íàçûâàåòñÿýòîé ÊÊÑ. Áóäåì ãîâîðèòü, ÷òî ÊÊÑ Σ00 ÿâëÿåòñÿíåïîëíîé ÊÊÑ Σ0 , åñëè îíà ïîëó÷àåòñÿ â ðåçóëüòàòå ñîåäèíåíèÿ âñåõ íåïîëíûõ âåðøèí Σ0 îòñóòñòâóþùèìè â íèõ êîíòàêòàìè ñ íîâûì âõîäîì, óäàëåíèÿ âñåõ¾ñòàðûõ¿ âõîäîâ è ïåðåõîäà ê ñîîòâåòñòâóþùåé ïðèâåäåííîé ÊÑ. Ïðè ýòîì, î÷åâèäíî,L Σ00 6 2L Σ0 ,(10.3)øèíîéäîïîëíåíèåìíåïîëíîé âåð-à îáúåäèíåíèå Σ0 è Σ00 ÿâëÿåòñÿ ïîëíîé ÊÊÑ.
ÄîïîëíåíèåΣ00 ê ïîëíîé ÊÊÑ Σ ñ 1 âõîäîì áóäåì íàçûâàòüΣ0 ÊÊÑ. Çàìåòèì, ÷òî ÊÊÑ Σ00 , â ñèëó îòìå÷åííûõ âûøå0ñâîéñòâ ïîëíûõ ÊÊÑ, ðåàëèçóåò ñèñòåìó ÔÀË F , åñëè ÊÊÑΣ0 ðåàëèçóåò ñèñòåìó ÔÀË F 0 . Òàêèì îáðàçîì, â ñèëó (10.3)ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèåêèíâåðñíîéÅñëè (1, m)-ÊÊÑ Σ0 ðåàëèçóåò ñèñòåìó ÔÀË0 ), òî ñóùåñòâóåò (1, m)-ÊÊÑ Σ00 , êîòîðàÿF 0 = (f10 , . . . , fmðåàëèçóåò ñèñòåìó ÔÀË F 0 = f 01, . . .
, f 0m è äëÿ êîòîðîéL (Σ00 ) 6 2L (Σ0 ).Ëåììà 10.1. ïîñëåäíèå ãîäû àêòèâíî èçó÷àåòñÿ (ñì., íàïðèìåð, [33])îäèí ñïåöèàëüíûé êëàññ îðèåíòèðîâàííûõ ÊÑ ò. í. äâîè÷íûå ðåøàþùèå äèàãðàììû (BDD), êîòîðûå ïðåäñòàâëÿþò ñîáîé, ïî ñóùåñòâó, ÷àñòíûé ñëó÷àé ÊÊÑ. Ñõåìà Σ ñîäíèì âõîäîì a è äâóìÿ âûõîäàìè a0 , a1 , íàçûâàåòñÿ, åñëè îíà ñîñòîèò èç îðèåíòèðîâàííûõ êîíòàêòîâ è íå èìååò (îðèåíòèðîâàííûõ) öèêëîâ,à èç êàæäîé åå âåðøèíû v , îòëè÷íîé îò âûõîäîâ, èñõîäÿòäâå äóãè ñ ïðîòèâîïîëîæíûìè ïîìåòêàìè âèäà xi , xi (ñì.è÷íîé ðåøàþùåé äèàãðàììîéäâî-10.a Íåêîòîðûå ìîäèôèêàöèè îñíîâíûõ êëàññîâ ñõåì a0a xi lll•5 v0lllv •RlRlRRRRxi RR)•v11 a1a) 0ll•5 v0xi lRlllll•Rv RRRRRR091•)v1 1b)Ðèñ. 10.3: ê îïðåäåëåíèþ BDDðèñ. 10.3a).
Ïðè ýòîì âåðøèíå v (a0 , a1 ), îáû÷íî, ñîïîñòàâëÿþò ïîìåòêó xi (ñîîòâåòñòâåííî 0, 1), à ïîìåòêè xi è xió èñõîäÿùèõ èç v ðåáåð çàìåíÿþò ïîìåòêàìè 0 è 1 ñîîòâåòñòâåííî (ñì. ðèñ. 10.3b). Çàìåòèì, ÷òî BDD Σ óêàçàííîãî âèäà îò ÁÏ x1 , . . . , xn ïîëó÷àåòñÿ èç íåêîòîðîé ïîëíîéb =Σb (x1 , . .
. , xn ; a0 , a1 ; a) ââåäåíèåì îðèåíòàöèè(2, 1)-ÊÊÑ Σb ïî íàïðàâëåíèþ äâèæåíèÿ ïðîõîäÿùèõêàæäîãî êîíòàêòà Σb , èäóùèõ îò a ê a0 ,a1 . Ïðè÷åðåç íåãî ïðîâîäÿùèõ öåïåé Σbýòîì, î÷åâèäíî, ñõåìû Σ è Σ ðåàëèçóþò ìåæäó âåðøèíàìèa è a1 íåêîòîðóþ ÔÀË f (x1 , . . . , xn ), ìåæäó âåðøèíàìè aè a0 ÔÀË f (x1 , . . .
, xn ), à ÔÀË ïðîâîäèìîñòè îò a0 ê a1è îáðàòíî ðàâíà 0.  òàêîì ñëó÷àå, îáû÷íî, ñ÷èòàåòñÿ, ÷òîΣ ðåàëèçóåò ÔÀË f . Òàê, íàïðèìåð, BDD Σ, ïîêàçàííàÿ íàðèñ. 10.4 (ñð. ñ ðèñ. 6.3c), ðåàëèçóåò ÔÀË x1 ⊕ x2 ⊕ x3 .Çàìåòèì, ÷òî BDD ìîæíî èíòåðïðåòèðîâàòü êàê àäðåñóþùèå áèíàðíûå ïðîãðàììû (ñì., íàïðèìåð, [11]). Äåéñòâèòåëüíî, ñîïîñòàâèì êàæäîé îòëè÷íîé îò âûõîäà âåðøèíå vBDD Σ (ñì. ðèñ. 10.3b) êîìàíäó óñëîâíîãî ïåðåõîäà íà êîìàíäó, ñîïîñòàâëåííóþ âåðøèíå vσ , σ ∈ B , åñëè xi = σ , àâûõîäíîé âåðøèíå ñ ïîìåòêîé σ , σ ∈ B , êîìàíäó ïðèñâîåíèÿ âû÷èñëÿåìîé ÔÀË çíà÷åíèÿ σ .
Ïîëó÷åííàÿ òàêèì92Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìx2x3/? a0;?•/????ww• ???w?w??w?w?wwx2 ?? x3 ??????a GwGG ? ?GGx ???x2 ???GGx1 G ?? 3? G•#/ a• /x1x2x31Ðèñ. 10.4: BDD äëÿ `3îáðàçîì ïðîãðàììà íà÷èíàåò ñâîþ ðàáîòó ñ êîìàíäû, ñîïîñòàâëåííîé âõîäó Σ, è âû÷èñëÿåò òó æå ñàìóþ ÔÀË, ÷òî èBDD Σ.Ñõåìà Σ, Σ ∈ UCÁ , ñ ìîíîòîííîé íóìåðàöèåé âåðøèí(ñì. 1), íàçûâàåòñÿÁ (ñì., íàïðèìåð, [11]). Ïóñòü Σ = Σ(x1 , .
. . , xn ; z1 , . . . , zm ),è ïóñòü, äëÿ îïðåäåëåííîñòè, vi , i ∈ [1, p], ãäå p = |V (Σ)|, âåðøèíà ñ íîìåðîì i, ïðè÷åì âåðøèíû v1 , . . . , vn èìåþò ïîìåòêè x1 , . . . , xn , à âåðøèíû vj1 , . . . , vjm ïîìåòêè z1 , . . . , zmñîîòâåòñòâåííî. Ñîïîñòàâèì âåðøèíå vi , i ∈ [1, p], ¾âíóòðåííþþ¿ ÁÏ ui è áóäåì ñ÷èòàòü, ÷òî vi âûïîëíÿåò êîìàíäó ñíîìåðîì i, êîòîðàÿ ÿâëÿåòñÿ:çèñîìâû÷èñëÿþùåé ïðîãðàììîé (ÂÏ) íàä áà-a) êîìàíäîé ââîäà ui = xi , åñëè i ∈ [1, n];(i)(i) b) âû÷èñëÿþùåé êîìàíäîé ui = ϕ(i) u1 , .
. . , uk(i) , ãäåϕ(i) ÔÑ îò k (i) ÁÏ, ïðèïèñàííûé âåðøèíå vi â Σ,(i)à uj , j = 1, . . . , k (i) , ÁÏ, ñîïîñòàâëåííàÿ íà÷àëüíîé âåðøèíå äóãè ñ íîìåðîì j , âõîäÿùåé â vi , åñëèi ∈ (n, p].Êðîìå òîãî, áóäåì ñ÷èòàòü, ÷òî êàæäîé âåðøèíå vji , i ∈ [1, m],ñîîòâåòñòâóåò êîìàíäà ñ íîìåðîì (p + i), ÿâëÿþùàÿñÿ êîìàíäîé âûâîäà zi = uji .Ïðåäïîëàãàåòñÿ, ÷òî êîìàíäû ÂÏ Σ âûïîëíÿþòñÿ ïîñëåäîâàòåëüíî â ñîîòâåòñòâèè ñ èõ íîìåðàìè â ìîìåíòû âðå-10.Íåêîòîðûå ìîäèôèêàöèè îñíîâíûõ êëàññîâ ñõåì93ìåíè 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
