OK-metodichka-2010-part1 (1132792), страница 6
Текст из файла (страница 6)
. . , xi−1 , xi , xi+1 , . . . , xn ) çàâèñèò îò xi ìîíîòîííî(ñîîòâåòñòâåííî êîíúþíêòèâíî, äèçúþíêòèâíî). Î÷åâèäíî,÷òî âñå îñîáåííîñòè ÄÍÔ, õàðàêòåðíûå äëÿ ÔÀË ñ òîé èëèèíîé ìîíîòîííîé çàâèñèìîñòüþ îò ÁÏ ðàñïðîñòðàíÿþòñÿ íàÔÀË ñ àíàëîãè÷íîé èíìîíîòîííîé çàâèñèìîñòüþ ïîñëå èíâåðòèðîâàíèÿ ñîîòâåòñòâóþùèõ ÁÏ.Ñîïîñòàâèì êàæäîìó íàáîðó β èç B n , ìîíîòîííóþ ÝÊ+Kβ îò ÁÏ X (n), ñîñòîÿùóþ èç òåõ è òîëüêî òåõ áóêâ xj ,j ∈ [1, n], äëÿ êîòîðûõ β hji = 1, è çàìåòèì, ÷òî êàæäàÿ ìîíîòîííàÿ ÝÊ îò ÁÏ X (n) ìîæåò áûòü ïðåäñòàâëåíà â óêàçàííîì âèäå. Ëåãêî âèäåòü òàêæå, ÷òî ãðàíü, ñîîòâåòñòâóþ-êîíúþíêòèâíàÿ äèçúþíêòèâíàÿèíêîíúþíêòèâíî èíäèçúþíêòèâíîèíìîíîòîííî5.Ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔ39ùàÿ ÝÊ Kβ+ , ãäå β = (β1 , .
. . , βn ) ∈ B n , èìååò âèä Γγ , ãäåγ = (2 − β1 , . . . , 2 − βn ). Íàáîð α, α ∈ B n , íàçûâàåòñÿìîíîòîííîé ÔÀË f , f ∈ P2 (n), åñëè α ∈ Nfè f (β) = 0 äëÿ ëþáîãî îòëè÷íîãî îò α íàáîðà β òàêîãî, ÷òîβ 6 α. Ìíîæåñòâî âñåõ íèæíèõ åäèíèö ìîíîòîííîé ÔÀË fáóäåì îáîçíà÷àòü ÷åðåç Nf+ . ñèëó ââåäåííûõ îïðåäåëåíèé, Kβ+ (α) = 1 òîãäà è òîëüêî òîãäà, êîãäà α > β , îòêóäà ñëåäóåò, ÷òî íàáîð β ÿâëÿåòñÿåäèíñòâåííîé íèæíåé åäèíèöåé ÝÊ Kβ+ è ÷òî ÝÊ Kβ+0 èìïëèöèðóåò ÝÊ Kβ+00 òîãäà è òîëüêî òîãäà, êîãäà β 0 > β 00 .Îòñþäà âûòåêàåò òàêæå, ÷òî ÝÊ Kβ+ ÿâëÿåòñÿ ïðîñòîé èìïëèêàíòîé ìîíîòîííîé ÔÀË f òîãäà è òîëüêî òîãäà, êîãäàβ ∈ Nf+ , è ÷òî íàáîð β ÿâëÿåòñÿ ïðè ýòîì ÿäðîâîé òî÷êîéÔÀË f . Òàêèì îáðàçîì, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.íèæ-íåé åäèíèöåéÑîêðàùåííàÿ ÄÍÔ A ìîíîòîííîé ÔÀË f , f ∈ P2 (n),ÿâëÿåòñÿ åäèíñòâåííîé òóïèêîâîé ÄÍÔ ýòîé ÔÀË è èìååò âèä:Ëåììà 5.1.A (x1 , .
. . , xn ) =_Kβ+ (x1 , . . . , xn ) .β∈Nf+Ïðè ýòîì âñå íàáîðû èç Nf+ ÿâëÿþòñÿ ÿäðîâûìè òî÷êàìèÔÀË f .Ìîíîòîííàÿ ÔÀË ÿâëÿåòñÿ ÿäðîâîé ÔÀË.Ñëåäñòâèå.Íàïîìíèì, ÷òî ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ, ñîêðàùåííàÿ ÄÍÔ ÔÀË f èç P2 (n) ïðåäñòàâëÿåò ñîáîé ïîêðûòèåìíîæåñòâà Nf âñåìè ìàêñèìàëüíûìè ãðàíÿìè, à òóïèêîâàÿÄÍÔ ñîîòâåòñòâóåò òóïèêîâîìó ïîäïîêðûòèþ, âûäåëÿåìîìó èç ýòîãî ïîêðûòèÿ. Ðàññìîòðèì ñíà÷àëà ìåòîä âûäåëåíèÿ èç çàäàííîãî ïîêðûòèÿ êîíå÷íîãî ìíîæåñòâà âñåõ åãîòóïèêîâûõ ïîäïîêðûòèé, îñíîâàííûé íà ïîñòðîåíèè ñîêðàùåííîé ÄÍÔ äëÿ ñïåöèàëüíîé ìîíîòîííîé ÔÀË, ñâÿçàííîéñ èñõîäíûì ïîêðûòèåì.40Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÏóñòü N = {α1 , .
. . , αs } êîíå÷íîå ìíîæåñòâî, à N == (N1 , . . . , Np ) ñèñòåìà åãî ïîäìíîæåñòâ, îáðàçóþùèõ ïîêðûòèå ìíîæåñòâà N. Ñîïîñòàâèì ïàðå (N, N) ìàòðèöó M, M ∈B p,s , äëÿ êîòîðîé M hi, ji = 1 òîãäà è òîëüêî òîãäà, êîãäàNi 3 αj . Çàìåòèì, ÷òî ìàòðèöà M íå èìååò íóëåâûõ ñòîëáöîâ, òàê êàê ñèñòåìà N îáðàçóåò ïîêðûòèå ìíîæåñòâà N.Áóäåì ñ÷èòàòü, ÷òî i-ÿ ñòðîêà (j -é ñòîëáåö) ìàòðèöû M ñîîòâåòñòâóåò ïîäìíîæåñòâó Ni ñèñòåìû N (ýëåìåíòó αj ìíîæåñòâà N) è íå áóäåì äåëàòü ìåæäó íèìè ñóùåñòâåííûõðàçëè÷èé. Òàê, áóäåì ãîâîðèòü, ÷òî i-ÿ ñòðîêà ìàòðèöû Måå j -é ñòîëáåö, åñëè M hi, ji = 1, òî åñòü Ni 3 αj ,è ÷òî ñèñòåìà ñòðîê ñ íîìåðàìè èç I, I ⊆ [1, p], îáðàçóåòM , åñëè êàæäûé åå ñòîëáåö ïîêðûâàåòñÿ õîòÿ áû îäíîé ñòðîêîé ñ íîìåðîì èç I , òî åñòü ñèñòåìàïîäìíîæåñòâ {Ni }i∈I çàäàåò ïîêðûòèå ìíîæåñòâà N.
Àíàëîãè÷íûì îáðàçîì ïîíèìàåòñÿ ïîêðûòèå îäíîãî ìíîæåñòâàñòðîê ìàòðèöû M äðóãèì ìíîæåñòâîì åå ñòðîê è ò. ï.Ïîêðûòèå ìàòðèöû M , â êîòîðîì íè îäíà ñòðîêà íå ïîêðûâàåòñÿ äðóãîé ñòðîêîé, ñ÷èòàåòñÿ, à ïîêðûòèå, íå èìåþùåå ñîáñòâåííûõ ïîäïîêðûòèé, íàçûâàåòñÿè ò. ï. Çàìåòèì, ÷òî çàäà÷à âûäåëåíèÿ âñåõòóïèêîâûõ ïîäïîêðûòèé èç ïîêðûòèÿ N ìíîæåñòâà N ýêâèâàëåíòíà çàäà÷å ïîñòðîåíèÿ âñåõ òóïèêîâûõ ïîêðûòèé ìàòðèöû M , ñîîòâåòñòâóþùåé ïàðå (N, N). Äëÿ ðåøåíèÿ ýòîéçàäà÷è ïî àíàëîãèè ñ ÄÍÔ ìîæíî ââåñòè ïîíÿòèå ÿäðîâîãî è ðåãóëÿðíîãî ñòîëáöîâ, à òàêæå ÿäðîâîé è ðåãóëÿðíîéñòðîêè, äëÿ êîòîðûõ áóäóò ñïðàâåäëèâû óòâåðæäåíèÿ, àíàëîãè÷íûå ëåììå 4.1 è òåîðåìå 4.1.Ïóñòü M, M ∈ B p,s ìàòðèöà áåç íóëåâûõ ñòîëáöîâ.Ñîïîñòàâèì i-é ñòðîêå, i ∈ [1, p], ìàòðèöû M ÁÏ yi , à êàæäîìó íàáîðó β, β ∈ B p , çíà÷åíèé ýòèõ ïåðåìåííûõ y =(y1 , . .
. , yp ), ìíîæåñòâî ñòðîê ìàòðèöû M ñ íîìåðàìè èçìíîæåñòâà I = I (β) ⊆ [1, p], ãäå i ∈ I (β) òîãäà è òîëüêîòîãäà, êîãäà β hii = 1. Ðàññìîòðèì ÔÀË F (y), äëÿ êîòîðîéïîêðûâàåòïîêðûòèå ìàòðèöûíåïðèâîäèìûìòóïèêîâûì5.41Ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔF (β) = 1 òîãäà è òîëüêî òîãäà, êîãäà ñèñòåìà ñòðîê ìàòðèöû M ñ íîìåðàìè èç I (β) îáðàçóåò åå ïîêðûòèå, è áóäåìíàçûâàòü ýòó ÔÀËìàòðèöû M . Çàìåòèì, ÷òî ÔÀË ïîêðûòèÿ F (y) ÿâëÿåòñÿ ìîíîòîííîé ÔÀË, àåå ¾íèæíèå åäèíèöû¿ ñîîòâåòñòâóþò òóïèêîâûì ïîêðûòèÿììàòðèöû M .
Äåéñòâèòåëüíî, èç íåðàâåíñòâà β 0 6 β 00 âûòåêàåò, ÷òî I (β 0 ) ⊆ I (β 00 ) è ïîòîìó F (β 0 ) 6 F (β 00 ), òî åñòü ÔÀËF ÿâëÿåòñÿ ìîíîòîííîé. Èç îïðåäåëåíèé ñëåäóåò òàêæå, ÷òîíàáîð β, β ∈ B p , ÿâëÿþùèéñÿ ¾íèæíåé åäèíèöåé¿ ÔÀË F ,ñîîòâåòñòâóåò ìíîæåñòâó I (β), êîòîðîå çàäàåò òóïèêîâîå ïîêðûòèå ìàòðèöû M , è îáðàòíî. Òàêèì îáðàçîì, â ñèëó ëåììû 5.1, êàæäàÿ ïðîñòàÿ èìïëèêàíòà âèäà K = yi1 yi2 · · · yir ,ãäå 1 6 i1 < · · · < ir 6 p, ÔÀË ïîêðûòèÿ F (y) ñîîòâåòñòâóåò òóïèêîâîìó ïîêðûòèþ ìàòðèöû M , ñîñòîÿùåìó èç ñòðîêñ íîìåðàìè èç ìíîæåñòâà I = {i1 , . . . , ir }, è îáðàòíî.ôóíêöèåé ïîêðûòèÿÔóíêöèÿ ïîêðûòèÿ F (y1, .
. . , yp) ìàòðèöû M, M ∈, áåç íóëåâûõ ñòîëáöîâ çàäàåòñÿ ÊÍÔ âèäà:Ëåììà 5.2.B p,sF (y1 , . . . , yp ) =s ^j=1_yi .(5.1)16i6pM hi,ji=1Äîêàçàòåëüñòâî. Äëÿ êàæäîãî j, j ∈ [1, s], ïîëîæèìJj (y) =_yi ,16i6pM hi,ji=1ãäå y = (y1 , . . . , yp ). Ëåãêî âèäåòü, ÷òî Jj (β) = 1 äëÿ ïðîèçâîëüíîãî íàáîðà β , β ∈ B p , òîãäà è òîëüêî òîãäà, êîãäàìíîæåñòâî ñòðîê ñ íîìåðàìè èç I (β) ïîêðûâàåò j -é ñòîëáåöìàòðèöû M, j ∈ [1, s]. Îòñþäà ñëåäóåò, ÷òî ÊÍÔ â ïðàâîé ÷àñòè (5.1) îáðàùàåòñÿ â 1 íà íàáîðå β òîãäà è òîëüêîòîãäà, êîãäà ìíîæåñòâî ñòðîê ñ íîìåðàìè èç I(β) îáðàçóåò42Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûïîêðûòèå ìàòðèöû M , òî åñòü òîãäà è òîëüêî òîãäà, êîãäàF (β) = 1.Ëåììà äîêàçàíà. ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ èç ÊÍÔ (5.1) ìîæíî ïîëó÷èòü ñîêðàùåííóþÄÍÔ ÔÀË F (y), ïðîñòûå èìïëèêàíòû êîòîðîé âçàèìíîîäíîçíà÷íî ñîîòâåòñòâóþò òóïèêîâûì ïîêðûòèÿì ìàòðèöû M .Ñëåäñòâèå.Çàäà÷à ïîñòðîåíèÿ âñåõ òóïèêîâûõ ÄÍÔ ÔÀË f èç P2 (n)íà îñíîâå åå ñîêðàùåííîé ÄÍÔ ñâîäèòñÿ ê ðàññìîòðåííîéâûøå çàäà÷å î ïîêðûòèè, åñëè â êà÷åñòâå ìíîæåñòâà N âçÿòüìíîæåñòâî Nf , à â êà÷åñòâå åãî ïîêðûòèÿ N ñèñòåìó âñåõìàêñèìàëüíûõ ãðàíåé ÔÀË f .
Ìàòðèöà M , ñîîòâåòñòâóþùàÿ óêàçàííîé ïàðå (N, N), íàçûâàåòñÿ, îáû÷íî,ÔÀË f . Çàìåòèì, ÷òî ÿäðîâîé ñòîëáåö (ñòðîêà) òàáëèöû Êâàéíà ñâÿçàí ñ ÿäðîâîé òî÷êîé (ñîîòâåòñòâåííî ãðàíüþ) ÔÀË f , ÷òî ðåãóëÿðíûé ñòîëáåö (ñòðîêà) ýòîé òàáëèöû çàäàåò ðåãóëÿðíóþ òî÷êó (ñîîòâåòñòâåííî ãðàíü) ÔÀË f ,÷òî ñòðîêà, ïîêðûâàåìàÿ ÿäðîâûìè ñòðîêàìè, ñîîòâåòñòâóåò ãðàíè, ïîêðûâàåìîé ÿäðîì è ò. ï.Ðàññìîòðèì, äëÿ ïðèìåðà, çàäà÷ó ïîñòðîåíèÿ âñåõ òóïèêîâûõ ÄÍÔ äëÿ ÔÀË g (x1 , x2 , x3 ) èç åå ñîêðàùåííîé ÄÍÔ,ïîëàãàÿ (ñì.
ðèñ. 2.1a, (2.10), (4.1) è (4.2)), ÷òîòàáëèöåéÊâàéíàNg = {α1 = (100) , α2 = (110) , α3 = (010) ,α4 = (011) , α5 = (001) , α6 = (101)},N = {N1 , . . . , N6 } ,ãäå Ni = NKi = {αi , αi+1 } äëÿ âñåõ i, i ∈ [1, 6], ïðè÷åìα7 = α1 = (100). Ïàðå (Ng , N) óêàçàííûì âûøå ñïîñîáîì5.43Ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔñîïîñòàâèì òàáëèöó Êâàéíà1 10 10 0M =0 00 01 0011000001100000110000,011ÔÀË ïîêðûòèÿ êîòîðîé â ñîîòâåòñòâèè ñ (5.1) çàäàåòñÿ ñëåäóþùåé ÊÍÔ îò ïåðåìåííûõ y = (y1 , . . .
, y6 ):F (y) = (y6 ∨ y1 ) (y1 ∨ y2 ) (y2 ∨ y3 ) (y3 ∨ y4 ) (y4 ∨ y5 ) (y5 ∨ y6 ) .Ðàñêðûâàÿ â ýòîé ÊÍÔ ñêîáêè è ïðèâîäÿ ïîäîáíûå, ïîëó÷èì ñîêðàùåííóþ ÄÍÔ ÔÀË F (y) âèäàF (y) = y1 y3 y5 ∨ y2 y4 y6 ∨ y1 y2 y4 y5 ∨ y2 y3 y5 y6 ∨ y1 y3 y4 y6 ,ñëàãàåìûå êîòîðîé âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþò òóïèêîâûì ÄÍÔ ÔÀË g (ñì.
(4.1), (4.2)). îáùåì ñëó÷àå ïðè ïîñòðîåíèè âñåõ òóïèêîâûõ ÄÍÔÔÀË f , f ∈ P2 (n), ñ ïîìîùüþ ëåììû5.2 íà îñíîâå åå ñîêðàùåííîé ÄÍÔ èñïîëüçóþò, îáû÷íî, ñëåäóþùóþ ìîäèôèêàöèþ ðàññìîòðåííîãî âûøå ïîäõîäà, êîòîðàÿ ïîçâîëÿåò óìåíüøàòü ðàçìåðû ìàòðèöû M . Ïóñòü NK1 , . . .
, NKq âñå ìàêñèìàëüíûå ãðàíè ÔÀË f , ïðè÷åì ãðàíè NKp+1 , . . . , NKt , ãäå1 6 p 6 t 6 q , ÿâëÿþòñÿ ÿäðîâûìè, à ãðàíè NKt+1 , . . .. . . , NKq ðåãóëÿðíûìè ãðàíÿìè ÔÀË f , è ïóñòü ìíîæåb ñîñòîèò èç âñåõ ÿäðîâûõ è ðåãóëÿðíûõ òî÷åê ÔÀËñòâî Nf . ÏîëîæèìbN = Nf \ N,N = {N1 , . . .
, Np } ,b ïðè âñåõ i, i ∈ [1, p], è çàìåòèì, ÷òî çàäàãäå Ni = NKi \ N÷à ïîñòðîåíèÿ âñåõ òóïèêîâûõ ÄÍÔ ÔÀË f ýêâèâàëåíòíà44Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûçàäà÷å âûäåëåíèÿ âñåõ òóïèêîâûõ ïîäïîêðûòèé èç ïîêðûòèÿ N ìíîæåñòâà N. Äåéñòâèòåëüíî, åñëè ñèñòåìà ïîäìíîæåñòâ Ni1 , . . . , Nir , ãäå 1 6 i1 < · · · < ir 6 p, ÿâëÿåòñÿ òóïèêîâûì ïîêðûòèåì ìíîæåñòâà N, òî ñèñòåìà ìàêñèìàëüíûõ ãðàíåé NKi1 , .
. . , NKir , NKp+1 , . . . , NKt çàäàåò òóïèêîâîåïîêðûòèå ìíîæåñòâà Nf , òî åñòü ñîîòâåòñòâóåò òóïèêîâîéÄÍÔ ÔÀË f , è îáðàòíî.Òàê, ïðèìåíÿÿ óêàçàííóþ ìîäèôèêàöèþ ê ÔÀË g 0 èçP2 (4), ïîêàçàííîé íà ðèñ. 3.1 (ñì. òàêæå (3.1) è (4.3)), ïîëó÷èì òðèâèàëüíóþ çàäà÷ó î ïîêðûòèè ìíîæåñòâà N == {(1000)} äâóìÿ ñîâïàäàþùèìè ñ íèì ïîäìíîæåñòâàìè N1è N2 .6Ãðàäèåíòíûé àëãîðèòì è îöåíêà äëèíû ãðàäèåíòíîãî ïîêðûòèÿÂûäåëåíèå âñåõ òóïèêîâûõ ïîäïîêðûòèé èç çàäàííîãî ïîêðûòèÿ è, â ÷àñòíîñòè, ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔÿâëÿåòñÿ òðóäîåìêîé çàäà÷åé.  ñâÿçè ñ ýòèì, âìåñòî òîãî, ÷òîáû ñòðîèòü âñå òóïèêîâûå ÄÍÔ è âûáèðàòü ñðåäèíèõ, íàïðèìåð, êðàò÷àéøóþ, ÷àñòî èñïîëüçóþò ýâðèñòè÷åñêèå àëãîðèòìû, ïîçâîëÿþùèå ïîëó÷àòü íå î÷åíü ¾äëèííûå¿ ÄÍÔ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
