Lectionc1 (1132950), страница 7
Текст из файла (страница 7)
ðèñ. 5.2) è ïðèìåíèì ê íåéîïèñàííûå âûøå ïîñòðîåíèÿ.Òåîðåìà äîêàçàíà.Çàìå÷àíèå 1. Èç òåîðåìû ñëåäóåò, ÷òî êðèòåðèé âõîæäåíèÿÝÊ â ÄÍÔ M íå èìååò òàêîãî ëîêàëüíîãî õàðàêòåðà, êàêêðèòåðèé âõîæäåíèÿ ÝÊ â ÄÍÔ T (ñðàâíèòå ñ òåîðåìîé 4.1).Çàìå÷àíèå 2.
Èçâåñòíî [7], ÷òî ïðè n > 14 â P2 (n) èìååòñÿöåïíàÿ ÔÀË ÷åòíîé äëèíû t; t > 2n 11 4, íà îñíîâå êîòîðîéñïðàâåäëèâîñòü òåîðåìû ìîæíî óñòàíîâèòü äëÿ îêðåñòíîñòèïîðÿäêà 2t 2 (ñì. äîêàçàòåëüñòâî).6Ôóíêöèÿ ïîêðûòèÿ, òàáëèöà Êâàéíà è ïîñòðîåíèåâñåõ òóïèêîâûõ ÄÍÔ. Ãðàäèåíòíûé àëãîðèòìè îöåíêà äëèíû ãðàäèåíòíîãî ïîêðûòèÿ ìèíèìèçàöèèÄÍÔÍàïîìíèì, ÷òî ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ, ñîêðàùåííàÿÄÍÔ ÔÀË f èç P2 (n) ïðåäñòàâëÿåò ñîáîé ïîêðûòèå ìíîæåñòâàNf âñåìè ìàêñèìàëüíûìè ãðàíÿìè, à òóïèêîâàÿ ÄÍÔ ñîîòâåòñòâóåòòóïèêîâîìó ïîäïîêðûòèþ, âûäåëÿåìîìó èç ýòîãî ïîêðûòèÿ.Ðàññìîòðèì ñíà÷àëà ìåòîä âûäåëåíèÿ èç çàäàííîãî ïîêðûòèÿêîíå÷íîãî ìíîæåñòâà âñåõ åãî òóïèêîâûõ ïîäïîêðûòèé, îñíîâàííûéíà ïîñòðîåíèè ñîêðàùåííîé ÄÍÔ äëÿ ñïåöèàëüíîé ìîíîòîííîéÔÀË, ñâÿçàííîé ñ èñõîäíûì ïîêðûòèåì.Ïóñòü N = f1 ; : : : ; s g êîíå÷íîå ìíîæåñòâî, à N == (N1 ; : : : ; Np ) ñèñòåìà åãî ïîäìíîæåñòâ, îáðàçóþùèõ ïîêðûòèå44Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûìíîæåñòâà N.
Ñîïîñòàâèì ïàðå (N; N) ìàòðèöó M; M 2B p;s , äëÿ êîòîðîé M hi; j i = 1 òîãäà è òîëüêî òîãäà, êîãäàNi 3 j . Çàìåòèì, ÷òî ìàòðèöà M íå èìååò íóëåâûõ ñòîëáöîâ,òàê êàê ñèñòåìà N îáðàçóåò ïîêðûòèå ìíîæåñòâà N. Áóäåìñ÷èòàòü, ÷òî i-ÿ ñòðîêà (j -é ñòîëáåö) ìàòðèöû M ñîîòâåòñòâóåòïîäìíîæåñòâó Ni ñèñòåìû N (ýëåìåíòó j ìíîæåñòâà N)è íå áóäåì äåëàòü ìåæäó íèìè ñóùåñòâåííûõ ðàçëè÷èé.Òàê, áóäåì ãîâîðèòü, ÷òî i-ÿ ñòðîêà ìàòðèöû Måå j -é ñòîëáåö, åñëè M hi; j i = 1, òî åñòü Ni 3 j , è ÷òîñèñòåìà ñòðîê ñ íîìåðàìè èç I; I [1; p], îáðàçóåòM , åñëè êàæäûé åå ñòîëáåö ïîêðûâàåòñÿ õîòÿ áûîäíîé ñòðîêîé ñ íîìåðîì èç I , òî åñòü ñèñòåìà ïîäìíîæåñòâfNigi2I çàäàåò ïîêðûòèå ìíîæåñòâà N.
Àíàëîãè÷íûì îáðàçîìïîíèìàåòñÿ ïîêðûòèå îäíîãî ìíîæåñòâà ñòðîê ìàòðèöû Mäðóãèì ìíîæåñòâîì åå ñòðîê è ò. ï.Ïîêðûòèå ìàòðèöû M , â êîòîðîì íè îäíà ñòðîêà íå ïîêðûâàåòñÿäðóãîé ñòðîêîé, ñ÷èòàåòñÿ, à ïîêðûòèå, íåèìåþùåå ñîáñòâåííûõ ïîäïîêðûòèé, íàçûâàåòñÿè ò. ï. Çàìåòèì, ÷òî çàäà÷à âûäåëåíèÿ âñåõ òóïèêîâûõ ïîäïîêðûòèéèç ïîêðûòèÿ N ìíîæåñòâà N ýêâèâàëåíòíà çàäà÷å ïîñòðîåíèÿâñåõ òóïèêîâûõ ïîêðûòèé ìàòðèöû M , ñîîòâåòñòâóþùåé ïàðå(N; N).
Äëÿ ðåøåíèÿ ýòîé çàäà÷è ïî àíàëîãèè ñ ÄÍÔ ìîæíîââåñòè ïîíÿòèå ÿäðîâîãî è ðåãóëÿðíîãî ñòîëáöîâ, à òàêæåÿäðîâîé è ðåãóëÿðíîé ñòðîêè, äëÿ êîòîðûõ áóäóò ñïðàâåäëèâûóòâåðæäåíèÿ, àíàëîãè÷íûå ëåììå 4.1 è òåîðåìå 4.1.Ïóñòü M; M 2 B p;s ìàòðèöà áåç íóëåâûõ ñòîëáöîâ.Ñîïîñòàâèì i-é ñòðîêå, i 2 [1; p], ìàòðèöû M ÁÏ yi , à êàæäîìóíàáîðó ; 2 B p , çíà÷åíèé ýòèõ ïåðåìåííûõ y = (y1 ; : : : ; yp ), ìíîæåñòâî ñòðîê ìàòðèöû M ñ íîìåðàìè èç ìíîæåñòâàI = I ( ) [1; p], ãäå i 2 I ( ) òîãäà è òîëüêî òîãäà, êîãäà hii = 1. Ðàññìîòðèì ÔÀË F (y), äëÿ êîòîðîé F ( ) = 1òîãäà è òîëüêî òîãäà, êîãäà ñèñòåìà ñòðîê ìàòðèöû M ñíîìåðàìè èç I ( ) îáðàçóåò åå ïîêðûòèå, è áóäåì íàçûâàòüýòó ÔÀËìàòðèöû M .
Çàìåòèì, ÷òîïîêðûâàåòïîêðûòèåìàòðèöûíåïðèâîäèìûìôóíêöèåé ïîêðûòèÿòóïèêîâûì6.Ôóíêöèÿ ïîêðûòèÿ. Ãðàäèåíòíîå ïîêðûòèå45ÔÀË ïîêðûòèÿ F (y ) ÿâëÿåòñÿ ìîíîòîííîé ÔÀË, à åå ¾íèæíèååäèíèöû¿ ñîîòâåòñòâóþò òóïèêîâûì ïîêðûòèÿì ìàòðèöûM . Äåéñòâèòåëüíî, èç íåðàâåíñòâà 0 6 00 âûòåêàåò, ÷òîI ( 0 ) I ( 00 ) è ïîòîìó F ( 0 ) 6 F ( 00 ), òî åñòü ÔÀË Fÿâëÿåòñÿ ìîíîòîííîé. Èç îïðåäåëåíèé ñëåäóåò òàêæå, ÷òîíàáîð ; 2 B p , ÿâëÿþùèéñÿ ¾íèæíåé åäèíèöåé¿ ÔÀËF , ñîîòâåòñòâóåò ìíîæåñòâó I ( ), êîòîðîå çàäàåò òóïèêîâîåïîêðûòèå ìàòðèöû M , è îáðàòíî. Òàêèì îáðàçîì, â ñèëóëåììû 5.2, êàæäàÿ ïðîñòàÿ èìïëèêàíòà âèäà K = yi1 yi2 yir ,ãäå 1 6 i1 < < ir 6 p, ÔÀË ïîêðûòèÿ F (y ) ñîîòâåòñòâóåòòóïèêîâîìó ïîêðûòèþ ìàòðèöû M , ñîñòîÿùåìó èç ñòðîê ñíîìåðàìè èç ìíîæåñòâà I = fi1 ; : : : ; ir g, è îáðàòíî.Ôóíêöèÿ ïîêðûòèÿ F (y1; : : : ; yp) ìàòðèöû M; M 2, áåç íóëåâûõ ñòîëáöîâ çàäàåòñÿ ÊÍÔ âèäà:Ëåììà 6.1.B p;sF (y 1 ; : : : ; y p ) =Äîêàçàòåëüñòâî.s^_yi :16i6pM hi;j i=1Äëÿ êàæäîãî j; j 2 [1; s], ïîëîæèìJj (y) =j =1_16i6pM hi;j i=1(6.1)yi ;ãäå y = (y1 ; : : : ; yp ).
Ëåãêî âèäåòü, ÷òî Jj ( ) = 1 äëÿ ïðîèçâîëüíîãîíàáîðà , 2 B p , òîãäà è òîëüêî òîãäà, êîãäà ìíîæåñòâîñòðîê ñ íîìåðàìè èç I ( ) ïîêðûâàåò j -é ñòîëáåö ìàòðèöûM; j 2 [1; s]. Îòñþäà ñëåäóåò, ÷òî ÊÍÔ â ïðàâîé ÷àñòè (6.1)îáðàùàåòñÿ â 1 íà íàáîðå òîãäà è òîëüêî òîãäà, êîãäàìíîæåñòâî ñòðîê ñ íîìåðàìè èç I ( ) îáðàçóåò ïîêðûòèå ìàòðèöûM , òî åñòü òîãäà è òîëüêî òîãäà, êîãäà F ( ) = 1.Ëåììà äîêàçàíà. ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ èç ÊÍÔ (6.1) ìîæíî ïîëó÷èòü ñîêðàùåííóþ ÄÍÔÑëåäñòâèå.46Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÔÀË F (y), ïðîñòûå èìïëèêàíòû êîòîðîé âçàèìíî îäíîçíà÷íîñîîòâåòñòâóþò òóïèêîâûì ïîêðûòèÿì ìàòðèöû M .Çàäà÷à ïîñòðîåíèÿ âñåõ òóïèêîâûõ ÄÍÔ ÔÀË f èç P2 (n)íà îñíîâå åå ñîêðàùåííîé ÄÍÔ ñâîäèòñÿ ê ðàññìîòðåííîéâûøå çàäà÷å î ïîêðûòèè, åñëè â êà÷åñòâå ìíîæåñòâà N âçÿòüìíîæåñòâî Nf , à â êà÷åñòâå åãî ïîêðûòèÿ N ñèñòåìó âñåõìàêñèìàëüíûõ ãðàíåé ÔÀË f .
Ìàòðèöà M , ñîîòâåòñòâóþùàÿóêàçàííîé ïàðå (N; N), íàçûâàåòñÿ, îáû÷íî,ÔÀË f . Çàìåòèì, ÷òî ÿäðîâîé ñòîëáåö (ñòðîêà) òàáëèöûÊâàéíà ñâÿçàí ñ ÿäðîâîé òî÷êîé (ñîîòâåòñòâåííî ãðàíüþ)ÔÀË f , ÷òî ðåãóëÿðíûé ñòîëáåö (ñòðîêà) ýòîé òàáëèöû çàäàåòðåãóëÿðíóþ òî÷êó (ñîîòâåòñòâåííî ãðàíü) ÔÀË f , ÷òî ñòðîêà,ïîêðûâàåìàÿ ÿäðîâûìè ñòðîêàìè, ñîîòâåòñòâóåò ãðàíè, ïîêðûâàåìîéÿäðîì è ò. ï.Ðàññìîòðèì, äëÿ ïðèìåðà, çàäà÷ó ïîñòðîåíèÿ âñåõ òóïèêîâûõf1;2g èç åå ñîêðàùåííîé ÄÍÔ,ÄÍÔ äëÿ ÔÀË g (x1 ; x2 ; x3 ) = s3ïîëàãàÿ (ñì. ðèñ.
2.1a, (3.5), (4.1) è (4.2)), ÷òîòàáëèöåé ÊâàéíàNg = f1 = (100) ; 2 = (110) ; 3 = (010) ;4 = (011) ; 5 = (001) ; 6 = (101)g;N = fN1 ; : : : ; N6 g ;Ni = NKi = fi ; i+1 g äëÿ âñåõ i; i 2 [1; 6], ïðè÷åì7 = 1 = (100). Ïàðå (Ng ; N) óêàçàííûì âûøå ñïîñîáîìãäåñîïîñòàâèì òàáëèöó Êâàéíà2160660M =660640111000001100000110000011030077077;077151ÔÀË ïîêðûòèÿ êîòîðîé â ñîîòâåòñòâèè ñ (6.1) çàäàåòñÿ ñëåäóþùåé6.Ôóíêöèÿ ïîêðûòèÿ. Ãðàäèåíòíîå ïîêðûòèåÊÍÔ îò ïåðåìåííûõ47y = (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 2 P2 (n), ñ ïîìîùüþ ëåììû 6.1 íà îñíîâå ååñîêðàùåííîé ÄÍÔ èñïîëüçóþò, îáû÷íî, ñëåäóþùóþ ìîäèôèêàöèþðàññìîòðåííîãî âûøå ïîäõîäà, êîòîðàÿ ïîçâîëÿåò óìåíüøàòüðàçìåðû ìàòðèöû M . Ïóñòü NK1 ; : : : ; NKq âñå ìàêñèìàëüíûåãðàíè ÔÀË f , ïðè÷åì ãðàíè NKp+1 ; : : : ; NKt , ãäå 1 6 p 6 t 6q,ÿâëÿþòñÿÿäðîâûìè,àãðàíèNKt+1 ; : : :: : : ; NKq ðåãóëÿðíûìè ãðàíÿìè ÔÀË f , è ïóñòü ìíîæåñòâîb ñîñòîèò èç âñåõ ÿäðîâûõ è ðåãóëÿðíûõ òî÷åê ÔÀË f .NÏîëîæèìb ; N = fN1 ; : : : ; Np g ;N = Nf n Nb ïðè âñåõ i; i 2 [1; p], è çàìåòèì, ÷òî çàäà÷àãäå Ni = NKi n Nïîñòðîåíèÿ âñåõ òóïèêîâûõ ÄÍÔ ÔÀË f ýêâèâàëåíòíà çàäà÷åâûäåëåíèÿ âñåõ òóïèêîâûõ ïîäïîêðûòèé èç ïîêðûòèÿ 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.6) è (4.3)), ïîëó÷èìòðèâèàëüíóþ çàäà÷ó î ïîêðûòèè ìíîæåñòâà N=48Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû= f(1000)g äâóìÿ ñîâïàäàþùèìè ñ íèì ïîäìíîæåñòâàìè N1è N2 .Âûäåëåíèå âñåõ òóïèêîâûõ ïîäïîêðûòèé èç çàäàííîãîïîêðûòèÿ è, â ÷àñòíîñòè, ïîñòðîåíèå âñåõ òóïèêîâûõ ÄÍÔÿâëÿåòñÿ òðóäîåìêîé çàäà÷åé.
 ñâÿçè ñ ýòèì, âìåñòî òîãî,÷òîáû ñòðîèòü âñå òóïèêîâûå ÄÍÔ è âûáèðàòü ñðåäè íèõ,íàïðèìåð, êðàò÷àéøóþ, ÷àñòî èñïîëüçóþò ýâðèñòè÷åñêèå àëãîðèòìû,ïîçâîëÿþùèå ïîëó÷àòü íå î÷åíü ¾äëèííûå¿ ÄÍÔ. Ê ÷èñëóòàêèõ àëãîðèòìîâ îòíîñèòñÿ è ãðàäèåíòíûé àëãîðèòì, îðèåíòèðîâàííûéíà âûäåëåíèå èç çàäàííîãî ïîêðûòèÿ äîñòàòî÷íî ¾êîðîòêèõ¿ïîäïîêðûòèé, èëè, èíà÷å, íà ïîñòðîåíèå äîñòàòî÷íî ¾êîðîòêèõ¿ïîêðûòèé äëÿ çàäàííîé ìàòðèöû. Íà êàæäîì øàãå ãðàäèåíòíîãîàëãîðèòìà â ìàòðèöå âûáèðàåòñÿ è âêëþ÷àåòñÿ â ïîêðûòèåòàêàÿ ñòðîêà, êîòîðàÿ ïîêðûâàåò íàèáîëüøåå ÷èñëî åùå íåïîêðûòûõ ñòîëáöîâ (åñëè òàêèõ ñòðîê íåñêîëüêî, èç íèõâûáèðàåòñÿ ñòðîêà ñ íàèìåíüøèì íîìåðîì). Àëãîðèòì çàêàí÷èâàåòñâîþ ðàáîòó ïîñëå òîãî øàãà, íà êîòîðîì ïîëó÷èëîñü ïîêðûòèå.Ñëåäóþùåå óòâåðæäåíèå äàåò âåðõíþþ îöåíêó äëèíûïîêðûòèÿ, ïîëó÷àåìîãî ñ ïîìîùüþ ãðàäèåíòíîãî àëãîðèòìàäëÿ ìàòðèö ñ çàäàííîé ¾ãóñòîòîé¿.Ïóñòü äëÿ äåéñòâèòåëüíîãî ; 0 < 6 1,â êàæäîì ñòîëáöå ìàòðèöû M; M 2 Bp;s, èìååòñÿ íåìåíüøå, ÷åì p, åäèíèö.
Òîãäà ïîêðûòèå ìàòðèöû M ,ïîëó÷àåìîå ñ ïîìîùüþãðàäèåíòíîãîàëãîðèòìà, èìååò äëèíólm+11íå áîëüøå, ÷åì ln (s) + .Äîêàçàòåëüñòâî. Ïóñòü äëÿ ïîñòðîåíèÿ ïîêðûòèÿ ìàòðèöûÒåîðåìà 6.1 ([6]).1M ñ ïîìîùüþ ãðàäèåíòíîãî àëãîðèòìà ïîòðåáîâàëîñü ñäåëàòüq øàãîâ, ïðè÷åì íà øàãå ñ íîìåðîì t; t 2 [1; q], áûëà âûáðàíàñòðîêà ñ íîìåðîì it . Äëÿ êàæäîãî t; t 2 [1; q ), ðàññìîòðèììàòðèöó Mt , êîòîðàÿ ïîëó÷àåòñÿ èç ìàòðèöû M â ðåçóëüòàòåóäàëåíèÿ ñòðîê ñ íîìåðàìè fi1 ; : : : ; it g, à òàêæå ïîêðûâàåìûõ1++Ïîëàãàåì, ÷òî ln x = ln x, åñëè x > 1, è ln x = 0, åñëè 0 < x < 1.6.49Ôóíêöèÿ ïîêðûòèÿ.
Ãðàäèåíòíîå ïîêðûòèåèìè ñòîëáöîâ, è êîòîðàÿ ïðèíàäëåæèò ìíîæåñòâó B pt ;st , ãäåpt = p t è st = s t ; 0 6 t 6 1. Äëÿ îïðåäåëåííîñòèáóäåì ñ÷èòàòü, ÷òî M0 = M; p0 = p; s0 = s; 0 = 1 èpq = p q; sq = q = 0. Çàìåòèì, ÷òî ïðè ëþáîì t; t 2 [0; q],ñïðàâåäëèâî íåðàâåíñòâîq 6 t + t s;(6.2)òàê êàê ïîñëå âûïîëíåíèÿ ïåðâûõ t øàãîâ àëãîðèòìà îñòàþòñÿíå ïîêðûòûìè t s ñòîëáöîâ ìàòðèöû M , à íà êàæäîìñëåäóþùåì øàãå ïîêðûâàåòñÿ íå ìåíåå îäíîãî ñòîëáöà.Çàìåòèì, äàëåå, ÷òî â êàæäîì ñòîëáöå ìàòðèöû Mt , t 2 [0; q ),èìååòñÿ íå ìåíåå, ÷åì p, åäèíèö è ïîýòîìó îáùåå ÷èñëîåäèíèö â ìàòðèöå Mt íå ìåíüøå, ÷åì pst , à çíà÷èò ñðåäíåå÷èñëî åäèíèö â åå ñòðîêàõ íå ìåíüøå, ÷åì st . Îòñþäàâûòåêàåò, ÷òî ñòðîêà ìàòðèöû M ñ íîìåðîì it+1 , êîòîðàÿâûáèðàåòñÿ íà (t + 1)-ì øàãå àëãîðèòìà è ÿâëÿåòñÿ ñòðîêîéìàòðèöû Mt ñ íàèáîëüøèì ÷èñëîì åäèíèö, ñîäåðæèò íå ìåíüøå,÷åì st , åäèíèö, òî åñòü ïîêðûâàåò íå ìåíüøå, ÷åì st ,åùå íå ïîêðûòûõ ñòîëáöîâ ìàòðèöû M .
Òàêèì îáðàçîì, äëÿëþáîãî t; t 2 [0; q ), âûïîëíÿþòñÿ ñîîòíîøåíèÿst+1 = st+1 6 st st = st (1 ) ;èç êîòîðûõ, ñ ó÷åòîì 0 = 1, ñëåäóåò, ÷òît 6 (1 )t 6 e tïðè ëþáîì t; t 2 [0; q ).Âûáèðàÿ çíà÷åíèå ïàðàìåòðà t òàê, ÷òî1t = ln+ (s) ;(6.3)ïîäñòàâëÿÿ åãî â (6.2) è ó÷èòûâàÿ (6.3), ïîëó÷èìq6+1 +11ln (s) + s e ln (s) 6 ln+ (s) + :Òåîðåìà äîêàçàíà.50Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû êà÷åñòâå ïðèìåðà ïðèìåíåíèÿ ãðàäèåíòíîãî àëãîðèòìàðàññìîòðèì çàäà÷ó î ¾ïðîòûêàíèè¿ ãðàíåé êóáà åãî òî÷êàìè.Çàäà÷à î ¾ïðîòûêàíèè¿ ñèñòåìû N, ñîñòîÿùåé èç ïîäìíîæåñòâN1 ; N2 ; : : : ; Np ìíîæåñòâà N = f1 ; : : : ; s g, çàêëþ÷àåòñÿ âíàõîæäåíèè òàêîãî ïîäìíîæåñòâà ìíîæåñòâà N, â êîòîðîìïðè ëþáîì i; i 2 [1; p], èìååòñÿ õîòÿ áû îäèí ýëåìåíò èçNi .
Ýòà çàäà÷à ñâîäèòñÿ ê çàäà÷å î âûäåëåíèè ïîäïîêðûòèÿèç ïîêðûòèÿ îòðåçêà [1; p] åãî ïîäìíîæåñòâàìè I1 ; : : : ; Is ,ãäå Ii = fj : i 2 Nj g ïðè âñåõ i; i 2 [1; s]. Çàìåòèì, ÷òîìàòðèöà ïîñòðîåííîé òàêèì îáðàçîì ñèñòåìû ïîäìíîæåñòâîòðåçêà [1; p] ïîëó÷àåòñÿ èç ìàòðèöû ñèñòåìû (N; N) â ðåçóëüòàòåòðàíñïîíèðîâàíèÿ.Ïðè ëþáûõ íàòóðàëüíûõ n è m, m 6 n,â êóáå Bn âñåãäà íàéäåòñÿ ïîäìíîæåñòâî ìîùíîñòè íåáîëåå, ÷åì n 2m, ïðîòûêàþùåå âñå ãðàíè ðàíãà m.Äîêàçàòåëüñòâî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
