Теормин (2012) (1133351), страница 5
Текст из файла (страница 5)
Âûäåëèòü îñòîâíîå äåðåâîñîåäåíèâ êàæäîå íå âîøåäøåå âD||U K (L, n)|| ≤ (8nL)L .D, ïîòîì ïîëó÷èòü íàääåðåâî D0 , ïðè-âûïîëíÿåòñÿ íåðàâåíñòâîðåáðî ñõåìû ê îäíîé èç ñâîèõ êîíöåâûõ âåðøèí, îòëè÷íûõ12îò âõîäà, çàòåì ïîëó÷èòüðåâüåâ íå áîëåå(8n)LD00 ,íåíèÿ êàæäîãî ëèñòà äåðåâàïîëó÷àåì îöåíêó.îðèåíòèðîâàâ ðåáðà ïî íàïðàâëåíèþ ê êîðíþ. ×èñëî òàêèõ äå-. Çàìåòèì òàêæå, ÷òî ÊÑ ìîæåò áûòü ïîëó÷åíà â ðåçóëüòàòå ïðèñîåäè-D00ê îäíîé èç åãî âåðøèí, îòëè÷íîé îò âûõîäà.
Ñëåäîâàòåëüíî,Ëþáàÿ ñèììåòðè÷åñêàÿ, òðàíçèòèâíàÿ è ðåôëåêñèâíàÿ ìàòðèöàF, F ∈ (P2 (n))m,m ,ðåà-Σ = Σ(x1 , . . . , xn ; a1 , . . . , am ), êîòîðàÿ ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå âñåõ ÊÑΣij = Σij (x1 , . . . , xn ; ai , aj ), ãäå 1 ≤ i < j ≤ m, à ÊÑ Σij ÿâëÿåòñÿ π -ñõåìîé è ïîñòðîåíà ïîñîâåðøåííîé ÄÍÔ ÔÀË F hi, ji è ñ÷èòàåòñÿ êàíîíè÷åñêîé ÊÑ ìàòðèöû F .ëèçóåòñÿ ÊÑ7Ëåììà.(1)(2){t1 − t5 , t6 , t6 } ⇒ {t7 − t11 }.Ýòàïû äîêàçàòåëüñòâà.
t7 âûâîäèòñÿ ïðèìåíåíèåì ê t5 ñ ñîâïàäàþùèìè âåðøèíàìè òîæ(2)äåñòâà t6 . t8 ïðèìåíèòü ê x1 t4 , ïîòîì ê îäíîðîäíûì ìåòåëêàì t5 , ïîòîì t3 . t9 t7 è t6 .t10 t7 è t5 . t11 ñ ïîìîùüþ t10 äåëàåì ïåðâûé òðåóãîëüíèê, êîòîðûé ïîòîì ðàñøèðÿåì ñïîìîùüþ t5 . Ëåììà. Ïðè n ≥ 2 èìååò ìåñòî âûâîäèìîñòü τn ⇒ τ (n) .Ýòàïû äîêàçàòåëüñòâà. t2 , t9 î÷åâèäíî, èç ñàìèõ ñåáÿ. 8,3,4,5 ïî èíäóêöèè. 7 èç 2 è 5;10 è 11 èç 7 è 5. Èìååò ìåñòî âûâîäèìîñòü8Êàíîíè÷åñêàÿ ÊÑ ïîðÿäêà nïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå êàíîíè÷åñêèõ (1, 1)-ÊÑΣ̂ij (x1 , .
. . , xn ; ai , aj ), ïîñòðîåííûõ íà îñíîâå ñîâåðøåííûõ ÄÍÔ ÔÀË ïðîâîäèìîñòè îòai ê aj äëÿ âñåõ i è j òàêèõ, ÷òî 1 ≤ i < j ≤ m.(n)Êàíîíè÷åñêàÿ öåïü ïîðÿäêà n ëþáàÿ öåïü Ii , ãäå i ∈ [1, 2n ], à òàêæå ëþáàÿ öåïü,(n)êîòîðàÿ ïîëó÷àåòñÿ èç Iiïåðåñòàíîâêîé êîíòàêòîâÊÑ Σ̂(x1 , . . . , xn ; a1 , . . . , am ) ÿâëÿåòñÿ êàíîíè÷åñêîé ÊÑ ïîðÿäêà n òîãäà è òîëüêî òîãäà,âèäàêîãäà îíà îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:1. ëþáîé êîíòàêòΣ̂ ïðèíàäëåæèò íåêîòîðîé êàíîíè÷åñêîé öåïè ïîðÿäêà n, ÿâëÿþùåéñÿΣ̂, ïðè÷åì ïîëþñàìè ýòîé ïîäñõåìû ñëóæàò òîëüêî êîíöåâûå âåðøèíûïîäñõåìîé ñõåìûäàííîé öåïè;2. ëþáàÿ âíóòðåííÿÿ âåðøèíàΣ̂ ÿâëÿåòñÿ âíóòðåííåé âåðøèíîé íåêîòîðîé öåïè èç ïóíêòà1;3. â ÊÑΣ̂îòñóòñòâóþò ¾âèñÿ÷èå öèêëû¿ è ¾ïàðàëëåëüíûå¿ öåïè, òî åñòü êàíîíè÷åñêèåöåïè ïîðÿäêànèç ïóíêòà 1, êîòîðûå ñîåäèíÿþò îäíè è òå æå ïîëþñà è ðåàëèçóþòðàâíûå ÝÊ;4.
â ÊÑΣ̂íåò ñóùåñòâåííûõ òðàíçèòíûõ ïðîâîäèìîñòåé, òî åñòü íàëè÷èå öåïåé âèäàñîåäèíÿþùèõ ïîëþñajòàêîãî æå âèäà, ñîåäèíÿþùåéËåììà.ëåíòíîéΣak è ïîëþñ ak ñ ïîëþñîì at ,ïîëþñ aj ñ ïîëþñîì at .ñ ïîëþñîì,âëå÷åò íàëè÷èå öåïèΣ, ãäå Σ ∈ U K è Σ = Σ(x1 , . . . , xn ; a1 , . . . , am ), è ëþáîéΣ̂(x1 , . .
. , xn ; a1 , . . . , am ) êàíîíè÷åñêîãî âèäà ñóùåñòâóåò ÝÏ Σ ⇒ Σ̂.Äëÿ ëþáîé ÊÑÊÑ(n)Iiýêâèâà-τnΣ ⇒ Σ1 ⇒ Σ2 ⇒ Σ3 ⇒ Σ4 = Σ̂. Ñõåìà Σi îáëàäàåò ñâîéñòàâàìè 1(n) i êàíîíè÷åñêîé ÊÑ. Σ ⇒ Σ1 c ïîìîùüþ ïðèìåíåíèÿ ê êàæäîìó êîíòàêòó òîæäåñòâà t4 .Òåïåðü ÊÑ ñîñòîèò èç êàíîíè÷åñêèõ öåïåé ïîðÿäêà n. Σ1 ⇒ Σ2 ñ êàæäîé âíóòðåííåé âåðøèÝòàïû äîêàçàòåëüñòâà.íîé, èç êîòîðîé âûõîäèò íåêîòîðîå êîëè÷åñòâî (âîçìîæíî è 1) îäíîðîäíûõ çâåçä ðàçëè÷íûõöåïåé, ïðîâîäèì ñëåäóþùèå îïåðàöèè. Êàæäóþ çâåçäó çàìåíÿåì íà öèêë ïî òîæäåñòâó(n)t11.(n)Äîáàâëÿåì íåíóæíûå âèñÿ÷èå âåðøèíû, ÷òîáû ìîæíî áûëî ïðèìåíèòü òîæäåñòâî t3è óäàëèòü ìåøàþùóþ âåðøèíó. Óäàëèâ òàêèì îáðàçîì âñå âíóòðåííèå âåðøèíû, íå ÿâëÿþùèåñÿ13âíóòðåííèìè âåðøèíàìè êàíîíè÷åñêèõ öåïåé, èçΣ1(n)nè t7 , Σ3 ⇒ Σ4 c ïîìîùüþ t10 .
Òåîðåìà. Äëÿ ëþáûõ äâóõ ýêâèâàëåíòíûõ ÊÑ000âèäà Σ ⇒ Σ .τnïîëó÷èëèΣ0èΣ00Σ2 . Σ2 ⇒ Σ3îò ÁÏx1 , . . . , x nñóùåñòâóåò ÝÏÝòàïû äîêàçàòåëüñòâà. Ôàêòè÷åñêè, äâà ðàçà èñïîëüçîâàòü ëåììó è îäèí ðàçÑëåäñòâèå.Ñëåäñòâèå.Kτn ÿâëÿåòñÿ ÊÏÑÒ äëÿ ÝÏ ÊÑ èç U îòKÑèñòåìà τ∞ ÿâëÿåòñÿ ÏÑÒ äëÿ ÝÏ ÊÑ èç U .PΘ(Σ, α) = |E(Σ|α )| − |V (Σ|α )| + |c(Σ|α )|. Θ(Σ) =Θ(Σ, α).Ëåììà.k < n,ÑèñòåìàÅñëèΣ0 (x1 , . . . , xn )Θ(Σ0 ) − Θ(Σ00 )òîα∈B nòîΣ00 (x1 , . . . , xn ),⇒ÁÏ(n)t2.x1 , . . .
, x n .Θ(Σ0 ) = Θ(Σ00 ),à åñëèΣ0 ⇒ Σ00 ,ãäåτk{t1 −t5 }n−käåëèòñÿ íà 2.Ýòàïû äîêàçàòåëüñòâà. Äîêàçàòü, ÷òî(n)t6 ñ ïîìîùüþΘ íå ìåíÿåòñÿ ïðè èñïîëüçîâàíèè òîæäåñòâ t1 . . . t5α, òî îí ïðîâîäèòn−mn−käåëèòñÿ íà 2, à çíà÷èò, íà 2. ñ ïîìîùüþ ïðîñòîãî ïåðåáîðà. Çàòåì, çàìåòèòü, ÷òî åñëè ïðîâîäèò íà íàáîðåíà2n−míàáîðàõ, ñëåäîâàòåëüíî ðàçíîñòüÒåîðåìà. êëàññåUKíå ñóùåñòâóåò êîíå÷íîé ïîëíîé ñèñòåìû òîæäåñòâ.Ýòàïû äîêàçàòåëüñòâà. Îò ïðîòèâíîãî: åñëè îãðàíè÷èòü ÷èñëî ÁÏ, íàïðèìåð, ÷èñëîìòîtn+16n,íå âûâîäèòñÿ.
×òîáû ýòî äîêàçàòü, íàäî ðàññìîòðåòü ëåâóþ ÷àñòü ýòîãî òîæäåñòâà.Ðàçíîñòü ôóíêöèéíåò âûâîäà.Θíå äåëèòñÿ íà 2, ÷òî ïðîòèâîðå÷èò ïðåäûäóùåé ëåììå, ñëåäîâàòåëüíî9 îñíîâå áîëüøèíñòâà ñòðóêòóðíûõ ïðåîáðàçîâàíèé ñõåì ëåæèò ðÿä îïåðàöèé, êîòîðûåîáîáùàþò îïåðàöèþ ñóïåðïîçèöèè ôóíêöèé è èñïîëüçóþòñÿ äëÿ ïîñòðîåíèÿ ñëîæíûõ ñõåìèç áîëåå ïðîñòûõ. Áàçèñîì òàêèõ ïîñòðîåíèé ÿâëÿåòñÿ îáû÷íî ñõåìà èç îäíîé èçîëèðîâàííîéâåðøèíû, ÿâëÿþùåéñÿ åå âõîäîì. Óêàçàííàÿ âåðøèíà íàçûâàåòñÿíîé êðàòíîñòè k, k ≥ 0,åñëè îíà îäíîâðåìåííî ÿâëÿåòñÿòîæäåñòâåííîé âåðøè-k -êðàòíûì âûõîäîì äàííîé ñõåìû.Êðàòíîñòü îäèí íå óêàçûâàåòñÿ, òîæäåñòâåííàÿ âåðøèíà êðàòíîñòè 0 ñ÷èòàåòñÿôèêòèâíîé.Ïðîñòåéøèå âèäû ñóïåðïîçèöèè ñõåì:1. îïåðàöèÿïåðåèìåíîâàíèÿ âõîäîâ ñõåìû2. îïåðàöèÿïåðåèìåíîâàíèÿ âûõîäîâ ñõåìû3.
îïåðàöèÿîáúåäèíåíèÿ ñõåì,ñ âîçìîæíûì èõ îòîæäåñòâëåíèåì;ñ âîçìîæíûõ èõ îòîæäåñòâëåíèåì;íå èìåþùèõ îáùèõ âåðøèí è îáùèõ âõîä-âûõîäíûõ ïî-ìåòîê, ïîíèìàåìàÿ, êàê îáû÷íîå îáúåäèíåíèå ñîîòâåòñòâóþùèõ ãðàôîâ.ÑõåìàΣ èìååò âèä Σ = Σ00 (Σ0 ), òî åñòü ÿâëÿåòñÿ ñóïåðïîçèöèåé ñõåì Σ00 è Σ0áåç îáùèõâåðøèí è âõîä-âûõîäíûõ ïîìåòîê, åñëè îíà ïîëó÷àåòñÿ â ðåçóëüòàòå îáúåäèíåíèÿ ýòèõ ñõåì èïðèñîåäèíåíèÿ (÷àñòè) âõîäîâ ñõåìûïîçèöèÿ ñ÷èòàåòñÿáåñïîâòîðíîé,âûõîäíûì âåðøèíàìâõîäîâ ñõåìûΣ0Σ00Σ0 .Σ00ê (íåêîòîðûì) âûõîäàì ñõåìûåñëè ðàçëè÷íûå âõîäûΣ00Σ0 .Óêàçàííàÿ ñóïåð-ïðèñîåäèíÿþòñÿ ê ðàçëè÷íûìΣ = Σ00 (Σ0 ) íàçûâàåòñÿ ñòûêîâêîé, åñëè ÷èñëî000ñõåìû Σ è êàæäûé âõîä Σ ïðèñîåäèíÿåòñÿ ê âûõîäóÑóïåðïîçèöèÿ âèäàðàâíî ÷èñëó âûõîäîâñ òåì æå íîìåðîì.Äëÿ ñóïåðïîçèöèè ñõåì âèäàΣ = Σ00 (Σ0 )õàðàêòåðíî, êàê ïðàâèëî, òî, ÷òî ñõåìàΣðåà-ëèçóåò ôóíêöèè, ïîëó÷àþùèåñÿ â ðåçóëüòàòå ñîîòâåòñòâóþùåé ïîäñòàíîâêè (âñåõ èëè ÷àñòè)Σ00 .
Â0ñëó÷àå ñòûêîâêè, íàïðèìåð, ýòî îçíà÷àåò, ÷òî ñõåìà Σ ðåàëèçóåò íàáîð ôóíêöèé âèäà F (F ),000000ãäå F è F íàáîðû ôóíêöèé, ðåàëèçîâàííûå ñõåìàìè Σ è Σ ñîîòâåòñòâåííî. Ñóïåðïîçè000öèÿ Σ = Σ (Σ ) ñ÷èòàåòñÿ ïðàâèëüíîé, åñëè ñõåìà Σ îáëàäàåò óêàçàííûì ñâîéñòâîì, èêîððåêòíîé, åñëè, êðîìå òîãî, â ëþáîé âåðøèíå Σ, êîòîðàÿ ñîîòâåòñòâåò âûõîäíîé âåðøèíåΣ0 , ðåàëèçóåòñÿ òà æå ñàìàÿ ôóíêöèÿ, ÷òî è â Σ0 .ôóíêöèé, ðåàëèçîâàííûõ ñõåìîéΣ0âìåñòî (âñåõ èëè ÷àñòè) âõîäíûõ ïåðåìåííûõ ñõåìû00Áóäåì äîïóñêàòü íàëè÷èå â ÊÑ âåíòèëåé è íåîðèåíòèðîâàííûõ ðåáåð áåç ïîìåòîê, êîòîðûåïðîâîäÿò ïðè ëþáûõ çíà÷åíèÿõ óïðàâëÿþùèõ âõîäíûõ ÁÏ è íàçûâàþòñÿF, F 0èF 00 ,ðåàëèçóåìûõ ÊÑΣ, Σ 0èïðîâîäíèêàìè.Σ = Σ00 (Σ0 ) íàçûâàåòñÿ ïðàâèëüíîé, åñëè äëÿ ìàòðèöΣ00 ñîîòâåòñòâåííî, âûïîëíÿåòñÿ ðàâåíñòâî F = F 0 · F 00 .Ñòûêîâêà (ñóïåðïîçèöèÿ) ÊÑ âèäà14êîððåêòíîé,Óêàçàííàÿ ñóïåðïîçèöèÿ ñ÷èòàåòñÿïîäñõåìûΣ00ñõåìûΣÑõåìà íàçûâàåòñÿåñëè, êðîìå òîãî, â âûõîäíûõ âåðøèíàõðåàëèçóþòñÿ òå æå ñàìûå ñòîëáöû ÔÀË, ÷òî è â ñàìîé ñõåìåðàçäåëèòåëüíîé ïî âõîäàì (âûõîäàì),Σ.åñëè ÔÀË ïðîâîäèìîñòèìåæäó ëþáûìè åå ðàçëè÷íûìè âõîäàìè (ñîîòâåòñòâåííî âûõîäàìè) ðàâíà 0.x1 , .
. . , xn ðàçäåëèòåëüíà íà íàáîðå α = (α1 , . . . , αn ) çíà÷åíèé ýòèõ ÁÏ,Σ|α .Ëåììà. Ïóñòü ÊÑ Σ ÿâëÿåòñÿ ðåçóëüòàòîì ñòûêîâêè âèäà Σ = Σ00 (Σ0 ), à F , F 0 è F 00 000000000ìàòðèöû, ðåàëèçóåìûå ÊÑ Σ, Σ è Σ ñîîòâåòñòâåííî. Òîãäà F ≥ F · F è F = F · F , åñëè000ÊÑ Σ ðàçäåëèòåëüíàÿ ïî âõîäàì èëè ÊÑ Σ ðàçäåëèòåëüíàÿ ïî âûõîäàì.Ýòàïû äîêàçàòåëüñòâà.
Ðàññìîòðèì ñëó÷àé áåñïîâòîðíîé ñòûêîâêè. q êîëè÷åñòâî âû000000000õîäîâ (âõîäîâ) ó Σ (Σ ). Cíà÷àëà íàäî äîêàçàòü, ÷òî f ≥ f1 · f2 ∨ · · · ∨ fq · fq (ðàâåíñòâî ïðèÊÑΣîò ÁÏåñëè ñîîòâåòñòâóþùåé ðàçäåëèòåëüíîñòüþ îáëàäàåò ñåòüðàçäåëèòåëüíîñòè). Äëÿ ýòîãî ðàññìîòðåòü ïðîâîäèìîñòü öåïåé ÷åðåç óêàçàííûå âåðøèíû.Ôàêòè÷åñêè,f ñòðîêà ìàòðèöûF. ñëó÷àå îòîæäåñòâëåíèÿ âõîäîâ èìååò ìåñòî ïîðàçðÿä-íàÿ äèçúþíêöèÿ ñòðîê. Ñòûêîâêà îáùåãî âèäà ñâîäèòñÿ ê îòîæäåñòâëåíèþ âõîäîâ è áåñïîâòîðíîé ñòûêîâêè.  ñèëó àññîöèàòèâíîñòè ïðîèçâåäåíèÿ ìàòðèö íåðàâåíñòâî ñîõðàíÿåòñÿ.Ñëåäñòâèå.Σ00ïî âõîäàì â êàæäîé âåðøèíå Ê Σ, Σ =Σ (Σ), êîòîðàÿ ñîîòâåòñòâóåò âûõîäó ÊÑ Σ , ðåàëèçóåòñÿ òîò æå ñàìûé ñòîëáåö ÔÀË, ÷òî è0â ÊÑ Σ , òî åñòü ðàññìàòðèâàåìàÿ ñóïåðïîçèöèÿ ÿâëÿåòñÿ êîððåêòíîé.Ñëåäñòâèå.
Ðàâåíñòâî F = F 0 ·F 00 âûïîëíÿåòñÿ íà ëþáîì íàáîðå çíà÷åíèé ÁÏ, íà êîòîðîì000ÊÑ Σ ðàçäåëèòåëüíà ïî âõîäàì èëè ÊÑ Σ ðàçäåëèòåëüíà ïî âûõîäàì.00 ñëó÷àå ðàçäåëèòåëüíîñòè ÊÑ010ÊàñêàäíàÿÊÑ ïðèâåäåííàÿ ÊÑ áåç èçîëèðîâàííûõ ïîëþñîâ, êîòîðàÿ ìîæåò áûòü ïî-ëó÷åíà èç ñèñòåìû òîæäåñòâåííûõ âåðøèí â ðåçóëüòàòå ðÿäà îïåðàöèé ïðèñîåäèíåíèÿ îäíîãîèëè äâóõ ïðîòèâîïîëîæíûõ êîíòàêòîâ è îïåðàöèé ïåðåèìåíîâàíèÿ âûõîäîâ. Êàñêàäíàÿ ÊÑ(ÊÊÑ) ñ÷èòàåòñÿïîëíîé,åñëè îíà áûëà ïîñòðîåíà áåç èñïîëüçîâàíèÿ îïåðàöèè ïðèñîåäèíå-íèÿ îäíîãî êîíòàêòà.Âåðøèíà ÊÊÑ, ââåäåííàÿ â íåå ñ ïîìîùüþ îïåðàöèè ïðèñîåäèíåíèÿ îäíîãî êîíòàêòà, íàçûâàåòñÿíåïîëíîé âåðøèíîé ýòîé ÊÊÑ. Áóäåì ãîâîðèòü, ÷òî ÊÊÑ Σ00åì íåïîëíîé ÊÊÑΣ0 ,ÿâëÿåòñÿ äîïîëíåíè-åñëè îíà ïîëó÷àåòñÿ â ðåçóëüòàòå ñîåäèíåíèÿ âñåõ íåïîëíûõ âåðøèíΣ0îòñóòñòâóþùèìè â íèõ êîíòàêòàìè ñ íîâûì âõîäîì, óäàëåíèÿ âñåõ ñòàðûõ âõîäîâ è ïåðåõîäàê ñîîòâåòñòâóþùåé ïðèâåäåííîé ÊÑ.Σ00 ê ïîëíîé ÊÊÑ Σ ñ 1 âõîäîì áóäåì íàçûâàòü èíâåðñíîé ê Σ0 ÊÊÑ.0), òî ñóùåñòâóåòËåììà.
Åñëè (1, m)- ÊÊÑ Σ0 ðåàëèçóåò ñèñòåìó ÔÀË F 0 = (f10 , . . . , fm0000 ), è äëÿ êîòîðîé L(Σ00 ) ≤(1, m)-ÊÊÑ Σ , êîòîðàÿ ðåàëèçóåò ñèñòåìó ÔÀË F̄ 0 = (f¯1 , . . . , f¯m2L(Σ0 ).00000Ýòàïû äîêàçàòåëüñòâà.  ñèëó óòâåðæäåíèÿ î òîì, ÷òî L(Σ ) ≤ 2L(Σ ), ãäå Σ äîïîë0íåíèå Σ . ÄîïîëíåíèåCõåìà ñ îäíèì âõîäîì è äâóìÿ âûõîäàìè íàçûâàåòñÿìîé,äâîè÷íîé ðåøàþùåé äèàãðàì-åñëè îíà ñîñòîèò èç îðèåíòèðîâàííûõ êîíòàêòîâ è íå èìååò (îðèåíòèðîâàííûõ) öèêëîâ,v , îòëè÷íîé îò âûõîäîâ, èñõîäÿò äâå äóãè ñ ïðîòèâîïîëîæíûìè ïîxi , x̄i .
Ïðè ýòîì âåðøèíå, îáû÷íî, ñîïîñòàâëÿþò ïîìåòêó xi (0, 1 äëÿ âûõîäíûõ),ïîìåòêè xi è x̄i ó èñõîäÿùèõ ðåáåð çàìåíÿþò ïîìåòêàìè 0 è 1 ñîîòâåòñòâåííî.CÑõåìà Σ, Σ ∈ UÁ , ñ ìîíîòîííîé íóìåðàöèåé âåðøèí íàçûâàåòñÿ âû÷èñëÿþùåé ïðî-à èç êàæäîé åå âåðøèíûìåòêàìè âèäààãðàììîé(ÂÏ) íàä áàçèñîì Á. Èñïîëüçóÿ âû÷èñëÿþùóþ ïðîãðàììó, ïîñëåäîâàòåëüíî ïðî-ñìàòðèâàþòñÿ âåðøèíû â ñîîòâåòñòâèè ñ èõ íîìåðàì è ðåçóëüòàòû ñîõðàíÿþòñÿ â ïàìÿòè.Âõîäíûå âåðøèíû âûïîëíÿþò êîìàíäû ââîäà, à âåðøèíû, ïîìå÷åííûå ÔÑ êîìàíäû âû÷èñëåíèÿ.Çíà÷åíèå ÁÏui ,âû÷èñëåííîå â ìîìåíò âðåìåíè i,ÿ÷åéêó ïàìÿòè íà îòðåçêå âðåìåíèâñòðå÷àåòñÿui .[i, ai ),ãäåaiÌàêñèìàëüíîå ÷èñëî îòðåçêîâ âèäàïåðåñå÷åíèå, íàçûâàåòñÿøèðèíîéÂÏΣ.15i ∈ (n, p],çàíèìàåò îòäåëüíóþ áèòîâóþ ìàêñèìàëüíûé íîìåð êîìàíäû, â êîòîðîé[i, ai ),ãäåi ∈ (n, p],èìåþùèõ íåïóñòîåËåììà.Äëÿ ëþáîé ÔÀË ñóùåñòâóåò ðåàëèçóþùàÿ åå ÂÏ íàä áàçèñîì Á0 øèðèíû íåáîëüøå, ÷åì 2.Ýòàïû äîêàçàòåëüñòâà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
