Lectionc1 (1132950), страница 5
Текст из файла (страница 5)
ßäðî èÄÍÔ Êâàéíà. Êðèòåðèé âõîæäåíèÿèìïëèêàíò â òóïèêîâûå ÄÍÔ,åãî ëîêàëüíîñòüÐàññìîòðèì âîïðîñ î ïîñòðîåíèè òåõ ÄÍÔ, â êîòîðûõ íåòíè÷åãî ¾ëèøíåãî¿. Áóäåì ãîâîðèòü, ÷òî ÄÍÔ A, ðåàëèçóþùàÿ4.Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ31òóïèêîâîéÔÀË f , ÿâëÿåòñÿÄÍÔ, åñëè f 6= A0 äëÿ ëþáîéÄÍÔ A0 , ïîëó÷åííîé èç A â ðåçóëüòàòå óäàëåíèÿ íåêîòîðûõáóêâ èëè öåëûõ ÝÊ. Èç îïðåäåëåíèÿ âûòåêàåò, ÷òî â òóïèêîâóþÄÍÔ A ÔÀË f ìîãóò âõîäèòü òîëüêî ïðîñòûå èìïëèêàíòûýòîé ÔÀË, òî åñòü A ïîëó÷àåòñÿ èç ñîêðàùåííîé ÄÍÔ ÔÀËf ïóòåì óäàëåíèÿ íåêîòîðûõ ÝÊ, è ÷òî A ÿâëÿåòñÿ íåïðèâîäèìîéÄÍÔ (ñì.
3). Ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ òóïèêîâàÿÄÍÔ A ÔÀË f çàäàåò òóïèêîâîå (ñì. 1) ïîêðûòèå ìíîæåñòâàNf ìàêñèìàëüíûìè ãðàíÿìè ÔÀË f è îáðàòíî. Èñõîäÿ èçýòèõ ¾ãåîìåòðè÷åñêèõ¿ ñîîáðàæåíèé ìîæíî íàõîäèòü âñåèëè íåêîòîðûå òóïèêîâûå ÄÍÔ äëÿ ÔÀË îò íåáîëüøîãî÷èñëà ÁÏ. Òàê, íàïðèìåð, ñîêðàùåííàÿ ÄÍÔ (3.8) äëÿ ÔÀ˾ãîëîñîâàíèÿ¿ H (x1 ; x2 ; x3 ) ÿâëÿåòñÿ åäèíñòâåííîé òóïèêîâîéÄÍÔ ýòîé ÔÀË, ÔÀË g (x1 ; x2 ; x3 ) (ñì.
ðèñ. 2.1a è (3.5))èìååò ïÿòü òóïèêîâûõ ÄÍÔ A1 = K1 _ K3 _ K5 ; A2 = K2 _ K4 _ K6 ;A3 = K1 _ K2 _K4 _ K5 ; A4 = K2 _ K3 _ K5 _ K6 ;A5 = K3 _ K4 _ K6 _ K1 ;(4.1)(4.2)à ó ÔÀË g 0 (x1 ; x2 ; x3 ; x4 ) (ñì. ðèñ. 3.1-3.2 è (3.6)) èìåþòñÿäâå òóïèêîâûå ÄÍÔ A01 = K10 _ K30 _ K40 _ K50 ; A02 = K20 _ K30 _ K40 _ K50 :(4.3)Ïîñòðîåíèå âñåõ èëè íåêîòîðûõ òóïèêîâûõ ÄÍÔ äëÿçàäàííîé ÔÀË f ÿâëÿåòñÿ, îáû÷íî, ïðîìåæóòî÷íûì ýòàïîìïðè ïîñòðîåíèè() ÄÍÔ ÔÀË f ,òî åñòü ÄÍÔ, êîòîðàÿ èìååò ìèíèìàëüíûé ðàíã (ñîîòâåòñòâåííîäëèíó) ñðåäè âñåõ ÄÍÔ, ðåàëèçóþùèõ f . Ýòî ñâÿçàíî ñ òåì,÷òî ìèíèìàëüíàÿ ÄÍÔ îáÿçàòåëüíî ÿâëÿåòñÿ òóïèêîâîé, àñðåäè êðàò÷àéøèõ ÄÍÔ âñåãäà åñòü òóïèêîâàÿ.
Òàê ÄÍÔA1 , A2 â (4.1) è òóïèêîâûå ÄÍÔ A01 , A02 â (4.3) ÿâëÿþòñÿìèíèìàëüíûìè è, îäíîâðåìåííî, êðàò÷àéøèìè ÄÍÔ ÔÀËg è ÔÀË g0 ñîîòâåòñòâåííî.ìèíèìàëüíîé êðàò÷àéøåé32Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÏðè ïîñòðîåíèè òóïèêîâûõ ÄÍÔ ÔÀË f áûâàåò ïîëåçíîçíàòü ÄÍÔ() ÔÀËf , òî åñòü äèçúþíêöèþ âñåõ òåõ ðàçëè÷íûõ ïðîñòûõ èìïëèêàíòýòîé ÔÀË, êîòîðûå âõîäÿò â ëþáóþ (ñîîòâåòñòâåííî õîòÿáû â îäíó) òóïèêîâóþ ÄÍÔ ÔÀË f .
Çàìåòèì, ÷òî ÄÍÔïåðåñå÷åíèå òóïèêîâûõ (ÄÍÔ \T ) ÔÀË f â îáùåì ñëó÷àåíå ðåàëèçóåò ñàìó ÔÀË f , à â íåêîòîðûõ ñëó÷àÿõ è, â ÷àñòíîñòè,â ñëó÷àå ÔÀË g (ñì. âûøå), ìîæåò áûòü ïóñòîé.  òî æåâðåìÿ ÄÍÔ ñóììà òóïèêîâûõ (ÄÍÔ T ) ÔÀË f âñåãäàðåàëèçóåò ýòó ÔÀË, ñîäåðæèòñÿ â åå ñîêðàùåííîé è ìîæåòñ íåé ñîâïàäàòü, êàê ýòî èìååò ìåñòî â ñëó÷àå ÔÀË g èëèâ ñëó÷àå ÔÀË ¾ãîëîñîâàíèÿ¿. Àíàëîãè÷íûì îáðàçîì îïðåäåëÿåòñÿÄÍÔ ñóììà ìèíèìàëüíûõ (ÄÍÔ M ) ÔÀË f è ò. ï. Î÷åâèäíî,÷òî ÄÍÔ M ÔÀË f ðåàëèçóåò ýòó ÔÀË è ñîäåðæèòñÿ âåå ÄÍÔ T , à äëÿ âñåõ ïðèâåäåííûõ âûøå ÔÀË ÄÍÔ Mñîâïàäàåò ñ ÄÍÔ T .Íàáîð , 2 B n , íàçûâàåòñÿÔÀË f (x1 ; : : : ; xn ),åñëè 2 Nf è âõîäèò òîëüêî â îäíó ìàêñèìàëüíóþ ãðàíüÔÀË f .
Ïðè ýòîì ãðàíü NK , ÿâëÿþùàÿñÿ ìàêñèìàëüíîéãðàíüþ ÔÀË f è ñîäåðæàùàÿ òî÷êó , ñ÷èòàåòñÿÔÀË f , à ñîâîêóïíîñòü âñåõ ðàçëè÷íûõ ÿäðîâûõãðàíåé ÔÀË f íàçûâàåòñÿÔÀË f . Òàê, ÿäðîì ÔÀË0g , ïîêàçàííîé íà ðèñ. 3.1, ÿâëÿþòñÿ ãðàíè N30 ; N40 è N50 ,êîòîðûå ñîäåðæàò ÿäðîâûå òî÷êè 3 ; 4 è 5 ñîîòâåòñòâåííî.ïåðåñå÷åíèå òóïèêîâûõ ñóììà òóïèêîâûõÿäðîâîé òî÷êîéãðàíüþÿäðîâîéÿäðîìÄèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà \T ÔÀËf ñîñòîèò èç òåõ ïðîñòûõ èìïëèêàíò ÔÀË f , êîòîðûåñîîòâåòñòâóþò ÿäðîâûì ãðàíÿì ýòîé ÔÀË.Äîêàçàòåëüñòâî.
Ïóñòü òóïèêîâàÿ ÄÍÔ A ÔÀË f (x1; : : : ; xn)Ëåììà 4.1.íå âêëþ÷àåò â ñåáÿ ïðîñòóþ èìïëèêàíòó K , êîòîðàÿ ñîîòâåòñòâóåòÿäðîâîé ãðàíè NK ÔÀË f , ñîäåðæàùåé ÿäðîâóþ òî÷êó ýòîé ÔÀË. Ïîñêîëüêó âñå îòëè÷íûå îò K ïðîñòûå èìïëèêàíòûÔÀË f îáðàùàþòñÿ â 0 íà íàáîðå , òî ÄÍÔ A òàêæå áóäåòðàâíà 0 íà ýòîì íàáîðå è, ñëåäîâàòåëüíî, f () = 0. Ïîëó÷åííîå4.33Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔïðîòèâîðå÷èå ñ òåì, ÷òî 2 Nf , äîêàçûâàåò íåîáõîäèìîñòüâêëþ÷åíèÿ ÝÊ K â ëþáóþ òóïèêîâóþ ÄÍÔ ÔÀË f .Ïóñòü òåïåðü ïðîñòàÿ èìïëèêàíòà K ÔÀË f ñîîòâåòñòâóåòãðàíè NK , êîòîðàÿ íå âõîäèò â ÿäðî ÔÀË f .
Ïðè ýòîìêàæäàÿ òî÷êà ãðàíè NK ïîêðûâàåòñÿ õîòÿ áû îäíîé îòëè÷íîéîò NK ìàêñèìàëüíîé ãðàíüþ ÔÀË f . Ñëåäîâàòåëüíî, âñåîòëè÷íûå îò NK ìàêñèìàëüíûå ãðàíè ÔÀË f îáðàçóþò ïîêðûòèåìíîæåñòâà Nf , èç êîòîðîãî ìîæíî âûäåëèòü òóïèêîâîå ïîäïîêðûòèå,ñîîòâåòñòâóþùåå òóïèêîâîé ÄÍÔ ÔÀË f , íå ñîäåðæàùåéÝÊ K .Ëåììà äîêàçàíà.ÿäðîâîéÁóäåì íàçûâàòü ÔÀË, åñëè âñå åå ìàêñèìàëüíûåãðàíè ÿâëÿþòñÿ ÿäðîâûìè. Èç ëåììû 4.1 ñëåäóåò, ÷òî ñîêðàùåííàÿÄÍÔ ÿäðîâîé ÔÀË ÿâëÿåòñÿ åå åäèíñòâåííîé òóïèêîâîéÄÍÔ.
Ïðèìåðîì ÿäðîâîé ÔÀË ÿâëÿåòñÿ ÔÀË ãîëîñîâàíèÿ(3.8) (ñì. òàêæå 6).(111)@@@@ @@@ @@@ x2x@1I@@6 x3``c`c``c`c`(000)`Ðèñ. 4.1: ¾ãåîìåòðèÿ¿ ñîêðàùåííîé ÄÍÔ ÔÀËg00Äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà, ïîëó÷àþùàÿñÿ èçñîêðàùåííîé ÄÍÔ ÔÀË f óäàëåíèåì òåõ ÝÊ K , äëÿ êîòîðûõãðàíü NK ïîêðûâàåòñÿ ÿäðîì ÔÀË f , íî íå âõîäèò â íåãî,íàçûâàåòñÿýòîé ÔÀË.
Èç îïðåäåëåíèé ñëåäóåò,÷òî ÄÍÔ Êâàéíà ÔÀË f âêëþ÷àåò â ñåáÿ ÄÍÔ T ýòîéÄÍÔ Êâàéíà34Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÔÀË è ñîäåðæèòñÿ â åå ñîêðàùåííîé ÄÍÔ. Çàìåòèì, ÷òîäëÿ ÔÀË g 00 (x1 ; x2 ; x3 ), ïîêàçàííîé íà ðèñ. 4.1, åå ñîêðàùåííàÿÄÍÔ èìååò âèä g 00 = x2 x3 _ x1 x2 _ x1 x3 ; òî åñòü îòëè÷àåòñÿîò ÄÍÔ Êâàéíà, êîòîðàÿ ÿâëÿåòñÿ åäèíñòâåííîé òóïèêîâîéÄÍÔ ýòîé ÔÀË è èìååò âèä g 00 = x2 x3 _ x1 x3 :  òî æå âðåìÿäëÿ ÔÀË g 0 , ïîêàçàííîé íà ðèñ. 3.1, ÄÍÔ Êâàéíà ñîâïàäàåòñ ñîêðàùåííîé ÄÍÔ ýòîé ÔÀË è îòëè÷àåòñÿ îò åå ÄÍÔ T ,êîòîðàÿ (ñì.
âûøå) ðàâíàK10 _ K20 _ K30 _ K40 _ K50 :Äëÿ ÔÀË f (x1 ; : : : ; xn ) è íàáîðà , 2 Nf , îáîçíà÷èì÷åðåç (f ) ìíîæåñòâî âñåõ ïðîõîäÿùèõ ÷åðåç ìàêñèìàëüíûõãðàíåé ÔÀË f , êîòîðîå ìû áóäåì íàçûâàòü ïó÷êîì ÔÀË f÷åðåç òî÷êó . Òî÷êó ; 2 Nf , áóäåì íàçûâàòü ðåãóëÿðíîéòî÷êîé ÔÀË f , åñëè íàéäåòñÿ òî÷êà ; 2 Nf , äëÿ êîòîðîéèìååò ìåñòî ñòðîãîå âêëþ÷åíèå (f ) (f ). Óêàçàííîåâêëþ÷åíèå îçíà÷àåò, ÷òî ëþáàÿ ìàêñèìàëüíàÿ ãðàíü ÔÀËf , ïðîõîäÿùàÿ ÷åðåç òî÷êó , ïðîõîäèò è ÷åðåç òî÷êó ,ïðè÷åì åñòü òàêàÿ ìàêñèìàëüíàÿ ãðàíü ÔÀË f , êîòîðàÿïðîõîäèò ÷åðåç òî÷êó , íî íå ïðîõîäèò ÷åðåç òî÷êó .
Ëåãêîâèäåòü, ÷òî äëÿ ëþáîé ðåãóëÿðíîé òî÷êè ÔÀË f âñåãäàíàéäåòñÿ òàêàÿ íåðåãóëÿðíàÿ òî÷êà ; 2 Nf , äëÿ êîòîðîé (f ) (f ).Èç îïðåäåëåíèé ñëåäóåò, ÷òî ëþáàÿ íåÿäðîâàÿ òî÷êà ÿäðîâîéãðàíè ðåãóëÿðíà, è ïîýòîìó òî÷êè i ; i 2 [1; 7], ÔÀË g 0 ,ïîêàçàííîé íà ðèñ. 3.1, ÿâëÿþòñÿ åå ðåãóëÿðíûìè òî÷êàìè.Êðîìå òîãî, â ñèëó âêëþ÷åíèÿ 0 (g 0 ) 0 (g 0 ), òî÷êà 0òîæå ÿâëÿåòñÿ ðåãóëÿðíîé òî÷êîé ýòîé ÔÀË.Ãðàíü NK ÔÀË f íàçûâàåòñÿýòîéÔÀË, åñëè âñå òî÷êè NK ðåãóëÿðíû.
Çàìåòèì, ÷òî ãðàíü,êîòîðàÿ íå âõîäèò â ÿäðî, íî ïîêðûâàåòñÿ èì, ÿâëÿåòñÿ ðåãóëÿðíîé.Çàìåòèì òàêæå, ÷òî äëÿ ÔÀË g 0 , ïîêàçàííîé íà ðèñ. 3.1,ãðàíè N60 è N70 , êîòîðûå íå âõîäÿò â ÄÍÔ T , ÿâëÿþòñÿðåãóëÿðíûìè, òàê êàê ñîñòîÿò èç ðåãóëÿðíûõ òî÷åê.ðåãóëÿðíîé ãðàíüþ4.Òóïèêîâûå è ìèíèìàëüíûå ÄÍÔ35Ïðîñòàÿ èìïëèêàíòàK ÔÀË f âõîäèò â ÄÍÔ T òîãäà è òîëüêî òîãäà, êîãäàãðàíü NK íå ÿâëÿåòñÿ ðåãóëÿðíîé ãðàíüþ ýòîé ÔÀË.Äîêàçàòåëüñòâî. Ïóñòü 1; : : : ; s âñå ðåãóëÿðíûå òî÷êèÒåîðåìà 4.1 (ñð.
[27, 6, 22, 10]).ÔÀË f . Òîãäà äëÿ êàæäîãî j; j = 1; : : : ; s, â ñèëó ðåãóëÿðíîñòèòî÷êè j , íàéäåòñÿ íåðåãóëÿðíàÿ òî÷êà j ÔÀË f , îáëàäàþùàÿòåì ñâîéñòâîì, ÷òî ëþáàÿ ìàêñèìàëüíàÿ ãðàíü ÔÀË f , ïðîõîäÿùàÿ÷åðåç òî÷êó j , ïðîõîäèò è ÷åðåç òî÷êó j . Ñëåäîâàòåëüíî,ëþáàÿ ñèñòåìà ìàêñèìàëüíûõ ãðàíåé ÔÀË f , ïîêðûâàþùàÿòî÷êè 1 ; : : : ; s , ¾àâòîìàòè÷åñêè¿ ïîêðîåò âñå òî÷êè 1 ; : : : ; s .Òàêèì îáðàçîì, ãðàíü NK , ñîñòîÿùàÿ èç ðåãóëÿðíûõ òî÷åê,íå ìîæåò âõîäèòü â òóïèêîâîå ïîêðûòèå ìíîæåñòâà Nf ìàêñèìàëüíûìèãðàíÿìè, è ïîýòîìó ÝÊ K íå ìîæåò âõîäèòü â ÄÍÔ T ÔÀËf.Ïóñòü òåïåðü NK íåðåãóëÿðíàÿ ãðàíü ÔÀË f , êîòîðàÿñîäåðæèò íåðåãóëÿðíóþ òî÷êó , è ïóñòü Nf n NK == f1 ; : : : ; q g.
Èç íåðåãóëÿðíîñòè òî÷êè ñëåäóåò, ÷òî äëÿëþáîãî j; j = 1; : : : ; q , ïó÷îê j (f ) íå ìîæåò áûòü ñòðîãîâëîæåí â ïó÷îê (f ). Êðîìå òîãî, ðàâåíñòâî j (f ) == (f ) òîæå íåâîçìîæíî, òàê êàê NK 2 (f ) n j (f ),è ïîýòîìó â j (f ) íàéäåòñÿ ãðàíü NKj , êîòîðàÿ ïðîõîäèò÷åðåç òî÷êó j , íî íå ïðîõîäèò ÷åðåç òî÷êó . Ñëåäîâàòåëüíî,èç ïîêðûòèÿ ìíîæåñòâà Nf ìàêñèìàëüíûìè ãðàíÿìè NK ; NK1 ; : : : ; NKqíåëüçÿ óäàëèòü ãðàíü NK , òàê êàê òîëüêî îíà ïîêðûâàåòâ íåì òî÷êó .
Òàêèì îáðàçîì, ëþáîå òóïèêîâîå ïîêðûòèåìíîæåñòâà Nf , ÿâëÿþùååñÿ ïîäïîêðûòèåì óêàçàííîãî ïîêðûòèÿ,áóäåò ñîîòâåòñòâîâàòü òóïèêîâîé ÄÍÔ, ñîäåðæàùåé ÝÊ K .Òåîðåìà äîêàçàíà.Êîñíåìñÿ, â çàêëþ÷åíèå, âîïðîñà î ëîêàëüíîì õàðàêòåðåðàññìîòðåííûõ âûøå êðèòåðèåâ âõîæäåíèÿ ïðîñòûõ èìïëèêàíòÔÀË f â åå ÄÍÔ \T è ÄÍÔ T (ñì. [27, 6, 22, 9]). Äëÿêàæäîé ìàêñèìàëüíîé ãðàíè N ÔÀË f (x1 ; : : : ; xn ) ïîëîæèìS0 (N; f ) = fNg, à çàòåì èíäóêöèåé ïî r; r = 1; 2; : : :, îïðåäåëèì36Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûìíîæåñòâî Sr (N; f ) êàê ìíîæåñòâî âñåõ òåõ ìàêñèìàëüíûõãðàíåé ÔÀË f , êîòîðûå èìåþò íåïóñòîå ïåðåñå÷åíèå õîòÿ áûñ îäíîé ãðàíüþ èç Sr 1 (N; f ).
Ïðè ýòîì ìíîæåñòâî Sr (N; f )áóäåì íàçûâàòürNf.îêðåñòíîñòüþ ïîðÿäêà ãðàíè ôóíêöèèÄîêàæåì, ÷òî âîïðîñ î âõîæäåíèè ïðîñòîé èìïëèêàíòûK ÔÀË f â ÄÍÔ \T (ÄÍÔ T ) ýòîé ÔÀË ìîæíî ðåøèòü,ðàññìàòðèâàÿ îêðåñòíîñòü S1 (NK ; f ) (ñîîòâåòñòâåííî S2 (NK ; f )).Äåéñòâèòåëüíî, ãðàíü NK ÿâëÿåòñÿ ÿäðîâîé ãðàíüþ ÔÀËf òîãäà è òîëüêî òîãäà, êîãäà îíà íå ïîêðûâàåòñÿ âñåìèîñòàëüíûìè ìàêñèìàëüíûìè ãðàíÿìè ýòîé ÔÀË. Ïîñêîëüêóãðàíè, íå âõîäÿùèå â S1 (NK ; f ), íå èìåþò îáùèõ òî÷åê ñNK , ãðàíü NK ÿâëÿåòñÿ ÿäðîâîé òîãäà è òîëüêî òîãäà, êîãäàîíà íå ïîêðûâàåòñÿ âñåìè îñòàëüíûìè ãðàíÿìè èç S1 (NK ; f ).Èç òåîðåìû 4.1 ñëåäóåò, ÷òî ÝÊ K íå âõîäèò â ÄÍÔ TÔÀË f òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîé òî÷êè èçNK íàéäåòñÿ òî÷êà , 2 Nf , äëÿ êîòîðîé (f ) (f ).Çàìåòèì, ÷òî âñå ãðàíè ïó÷êà (f ) âõîäÿò â S1 (NK ; f ),à âñå ãðàíè ïó÷êà (f ), åñëè (f ) \ (f ) 6= ?, âS2 (NK ; f ). Ñëåäîâàòåëüíî, ïðîâåðêó ãðàíè NK íà ðåãóëÿðíîñòüìîæíî îñóùåñòâèòü íà îñíîâå àíàëèçà åå îêðåñòíîñòè ïîðÿäêà2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
