OK-metodichka-2010-part2 (1132793), страница 11
Текст из файла (страница 11)
Ïðîâåäåì äîêàçàòåëüñòâî îò ïðîòèâíîãî:Òåîðåìà 8.2.ïóñòü τ ÊÏÑÒ äëÿ ÝÏ ÊÑ UK , è ïóñòü n ìàêñèìàëüíîå÷èñëî ÁÏ, âñòðå÷àþùèõñÿ â òîæäåñòâàõ ñèñòåìû τ . Òîãäà(n+1)τn ⇒ τ è τn ÊÏÑÒ äëÿ UK . Äîêàæåì, ÷òî τn 6⇒ t6.0Äëÿ ýòîãî ðàññìîòðèì ÊÑ Σ , ñîñòîÿùóþ èç ïðîñòîãî öèêëàäëèíû (n + 1), ñîäåðæàùåãî êîíòàêòû ñ ïîìåòêàìè xi , i ∈[1, n + 1], è èìåþùóþ åäèíñòâåííûé ïîëþñ ñ ïîìåòêîé 1, êî(n+1)òîðàÿ ÿâëÿåòñÿ ëåâîé ÷àñòüþ òîæäåñòâà t6.
Î÷åâèäíî,00÷òî åé ýêâèâàëåíòíà ÊÑ Σ , ñîäåðæàùàÿ èçîëèðîâàííûé ïî(n+1)ëþñ 1, êîòîðàÿ ÿâëÿåòñÿ ïðàâîé ÷àñòüþ òîæäåñòâà t6. Åñ(n+1)000ëè τn ⇒ t6, òî Σ ⇒ Σ . Ñîãëàñíî äàííûì âûøå îïðåäåτnëåíèÿì, Θ (Σ0 ) = 1, Θ (Σ00 ) = 0 è ðàçíîñòü Θ (Σ0 )−Θ (Σ00 ) = 1íå äåëèòñÿ íà 2, ÷òî ïðîòèâîðå÷èò óòâåðæäåíèþ ëåììû 8.2.(n+1)Òàêèì îáðàçîì, òîæäåñòâî t6íå âûâîäèòñÿ èç ñèñòåìûτn , à çíà÷èò, è èç ñèñòåìû τ . Îòñþäà ñëåäóåò, ÷òî τ íå ìîæåòÿâëÿòüñÿ ÊÏÑÒ äëÿ ÝÏ ÊÑ èç êëàññà UK .Òåîðåìà äîêàçàíà.9Îïåðàöèÿ ñóïåðïîçèöèè è åå êîððåêòíîñòüäëÿ íåêîòîðûõ òèïîâ ñõåì. Ðàçäåëèòåëüíûåêîíòàêòíûå ñõåìû è ëåììà Øåííîíà îñíîâå áîëüøèíñòâà ñòðóêòóðíûõ ïðåîáðàçîâàíèé ñõåìëåæèò ðÿä îïåðàöèé, êîòîðûå îáîáùàþò îïåðàöèþ ñóïåðïîçèöèè ôóíêöèé è èñïîëüçóþòñÿ äëÿ ïîñòðîåíèÿ ñëîæíûõñõåì èç áîëåå ïðîñòûõ. Áàçèñîì òàêèõ ïîñòðîåíèé ÿâëÿåòñÿîáû÷íî ñõåìà èç îäíîé èçîëèðîâàííîé âåðøèíû, ÿâëÿþùåéñÿ åå âõîäîì.
Óêàçàííàÿ âåðøèíà íàçûâàåòñÿk, k > 0, åñëè îíà îäíîâðåìåííîÿâëÿåòñÿ k -êðàòíûì âûõîäîì äàííîé ñõåìû. Ïðè ýòîì êðàò-íîé âåðøèíîé êðàòíîñòèòîæäåñòâåí-78Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìíîñòü îäèí, êàê ïðàâèëî, íå óêàçûâàåòñÿ, à òîæäåñòâåííàÿâåðøèíû êðàòíîñòè 0 ñ÷èòàåòñÿ.Ïðîñòåéøèìè âèäàìè ñóïåðïîçèöèè ñõåì ÿâëÿþòñÿ: 1)îïåðàöèÿñ âîçìîæíûì èõîòîæäåñòâëåíèåì; 2) îïåðàöèÿñ âîçìîæíûì èõ äóáëèðîâàíèåì èëè ñíÿòèåì; 3) îïåðàöèÿ, íå èìåþùèõ îáùèõ âåðøèí è îáùèõ âõîäâûõîäíûõ ïîìåòîê, ïîíèìàåìàÿ, êàê îáû÷íîå îáúåäèíåíèåñîîòâåòñòâóþùèõ ãðàôîâ.Áóäåì ãîâîðèòü, ÷òî ñõåìà Σ èìååò âèä Σ = Σ00 (Σ0 ), òîåñòü ÿâëÿåòñÿΣ00 Σ0 áåç îáùèõ âåðøèíè âõîä-âûõîäíûõ ïîìåòîê, åñëè îíà ïîëó÷àåòñÿ â ðåçóëüòàòå îáúåäèíåíèÿ ýòèõ ñõåì è ïðèñîåäèíåíèÿ (÷àñòè) âõîäîâñõåìû Σ00 ê (íåêîòîðûì) âûõîäàì ñõåìû Σ0 .
Óêàçàííàÿ ñóïåðïîçèöèÿ ñ÷èòàåòñÿ, åñëè ðàçëè÷íûå âõîäûΣ00 ïðèñîåäèíÿþòñÿ ê ðàçëè÷íûì âûõîäíûì âåðøèíàì Σ0 .Ñóïåðïîçèöèÿ âèäà Σ = Σ00 (Σ0 ) íàçûâàåòñÿ, åñëè ÷èñëî âõîäîâ ñõåìû Σ00 ðàâíî ÷èñëó âûõîäîâ ñõåìû Σ0 èêàæäûé âõîä Σ00 ïðèñîåäèíÿåòñÿ ê âûõîäó Σ0 ñ òåì æå íîìåðîì.Çàìåòèì, ÷òî îïåðàöèè îáúåäèíåíèÿ ñõåì è ïåðåèìåíîâàíèÿ èõ âõîäîâ (âûõîäîâ) ÿâëÿþòñÿ ÷àñòíûìè ñëó÷àÿìèââåäåííîé îïåðàöèè ñóïåðïîçèöèè.
Äåéñòâèòåëüíî, äëÿ îáúåäèíåíèÿ ñõåì ýòî î÷åâèäíî, à ëþáîå ïåðåèìåíîâàíèå âûõîäîâ (âõîäîâ) ñõåìû Σ ìîæíî çàäàòü ñóïåðïîçèöèåé âèäà Σ002 (Σ001 (Σ)) (ñîîòâåòñòâåííî Σ(Σ01 (Σ02 ))), ãäå ñõåìû Σ0i èΣ00i , i = 1, 2, ñîñòîÿò èç òîæäåñòâåííûõ âåðøèí ðàçëè÷íîéêðàòíîñòè.Çàìåòèì òàêæå, ÷òî ñóïåðïîçèöèÿ îáùåãî âèäà Σ = Σ00 (Σ0 )b 00 (Σb 0 ), ãäåâñåãäà ìîæåò áûòü ñâåäåíà ê ñòûêîâêå âèäà Σ = Σ000000bbñõåìû Σ è Σ ïîëó÷àþòñÿ èç ñõåì Σ è Σ ñîîòâåòñòâåííî äîáàâëåíèåì òîæäåñòâåííûõ âåðøèí è ïåðåèìåíîâàíèåìâûõîäîâ. Ñòûêîâêà âèäà Σ = Σ00 (Σ0 ), â ñâîþ î÷åðåäü, ìîæåòb 00 (Σb 0 ), ãäåáûòü ñâåäåíà ê áåñïîâòîðíîé ñòûêîâêå âèäà Σ = Σôèêòèâíîéïåðåèìåíîâàíèÿ âõîäîâ ñõåìûïåðåèìåíîâàíèÿ âûõîäîâ ñõåìûîáúåäèíåíèÿ ñõåìñóïåðïîçèöèåé ñõåìèáåñïîâòîðíîéñòûêîâêîé9.Îïåðàöèÿ ñóïåðïîçèöèè.
Ëåììà Øåííîíà79b0 è Σb 00 ïîëó÷àþòñÿ èç ñõåì Σ0 è Σ00 ñíÿòèåì âûõîäîâñõåìû Σè îòîæäåñòâëåíèåì âõîäîâ ñîîòâåòñòâåííî.Äëÿ ñóïåðïîçèöèè ñõåì âèäà Σ = Σ00 (Σ0 ) õàðàêòåðíî, êàêïðàâèëî, òî, ÷òî ñõåìà Σ ðåàëèçóåò ôóíêöèè, ïîëó÷àþùèåñÿ â ðåçóëüòàòå ñîîòâåòñòâóþùåé ïîäñòàíîâêè (âñåõ èëè ÷àñòè) ôóíêöèé, ðåàëèçîâàííûõ ñõåìîé Σ0 âìåñòî (âñåõ èëè÷àñòè) âõîäíûõ ïåðåìåííûõ ñõåìû Σ00 .  ñëó÷àå ñòûêîâêè, íàïðèìåð, ýòî îçíà÷àåò, ÷òî ñõåìà Σ ðåàëèçóåò íàáîðôóíêöèé âèäà F00 (F0 ), ãäå F00 è F0 íàáîðû ôóíêöèé, ðåàëèçîâàííûå ñõåìàìè Σ00 è Σ0 ñîîòâåòñòâåííî. ÑóïåðïîçèöèÿΣ = Σ00 (Σ0 ) ñ÷èòàåòñÿ, åñëè ñõåìà Σ îáëàäàåòóêàçàííûì ñâîéñòâîì, è, åñëè, êðîìå òîãî, â ëþáîé âåðøèíå Σ, êîòîðàÿ ñîîòâåòñòâóåò âûõîäíîé âåðøèíå Σ0 ,ðåàëèçóåòñÿ òà æå ñàìàÿ ôóíêöèÿ, ÷òî è â Σ0 . Çàìåòèì, ÷òîïðàâèëüíàÿ ñóïåðïîçèöèÿ âèäà Σ00 (Σ0 ) àâòîìàòè÷åñêè ÿâëÿåòñÿ êîððåêòíîé, åñëè êðàòíîñòü ëþáîé âûõîäíîé âåðøèíûΣ0 áîëüøå ÷èñëà ïðèñîåäèíÿåìûõ ê íåé âõîäîâ Σ00 .
Çàìåòèìòàêæå, ÷òî ñ ñîäåðæàòåëüíîé òî÷êè çðåíèÿ êîððåêòíîñòü ñóïåðïîçèöèè âèäà Σ00 (Σ0 ) ïîçâîëÿåò îäíîâðåìåííî èñïîëüçîâàòü âûõîäû Σ0 â äðóãèõ ñóïåðïîçèöèÿõ.Çàìåòèì òàêæå, ÷òî ëþáàÿ ÑÔÝ ìîæåò áûòü ïîëó÷åíà âðåçóëüòàòå ìíîãîêðàòíîãî ïðèìåíåíèÿ îïåðàöèè ñóïåðïîçèöèè, íà êàæäîì øàãå êîòîðîé ïðîèñõîäèò äóáëèðîâàíèå âûõîäà èëè ïðèñîåäèíåíèå îäíîãî ÔÝ, ê ÑÔÝ, ïåðâîíà÷àëüíîñîñòîÿùåé èç òîæäåñòâåííûõ âåðøèí.Íà ðèñ. 9.1a ïîêàçàíà ÑÔÝ Σ⊕2 , èìåþùàÿ ñëîæíîñòü 4 èðåàëèçóþùàÿ ÔÀË x1 ⊕ x2 , à íà ðèñ. 9.1b ÑÔÝ Σ⊕q , q > 3,êîòîðàÿ ÿâëÿåòñÿ ðåçóëüòàòîì ¾ïîñëåäîâàòåëüíîé¿ ñóïåðïîçèöèè (q − 1) ñõåì Σ⊕2 è ðåàëèçóåò ÔÀË `q (x1 , . . .
, xq ) ñîñëîæíîñòüþ 4q − 4.Ðàññìîòðèì òåïåðü âîïðîñû, ñâÿçàííûå ñ íàõîæäåíèåìôóíêöèîíèðîâàíèÿ äëÿ ñóïåðïîçèöèé ñåòåé èëè ÊÑ. Èç ñîîáðàæåíèé óäîáñòâà áóäåì äîïóñêàòü íàëè÷èå â ÊÑ âåíòèëåé è íåîðèåíòèðîâàííûõ ðåáåð áåç ïîìåòîê, êîòîðûå ïðî-ïðàâèëüíîéêîððåêòíîé80Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìx/1x2•/•/x1x2•&••w•'¬Σ⊕2x3--∨••z1 &•Σ⊕22222...xq,,,,•Σ⊕2z1a)b)Ðèñ. 9.1: ïðèìåð ñóïåðïîçèöèè ÑÔÝâîäÿò ïðè ëþáûõ çíà÷åíèÿõ óïðàâëÿþùèõ âõîäíûõ ÁÏ èíàçûâàþòñÿ. Ýòî ïîçâîëÿåò ñ÷èòàòü, ÷òî ñåòèÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì ÊÑ è ðåàëèçóþò ñâîè ìàòðèöûäîñòèæèìîñòè, ñîñòîÿùèå èç êîíñòàíòíûõ ÔÀË.Îïåðàöèÿ ñóïåðïîçèöèè ÊÑ è âñå åå ÷àñòíûå ñëó÷àè îïðåäåëÿþòñÿ îáû÷íûì îáðàçîì.
Ïðè ýòîì ïîìåòêàìè âõîäîâ èâûõîäîâ ÊÑ, â îòëè÷èå îò ÑÔÝ, íå îáÿçàòåëüíî ÿâëÿþòñÿïåðåìåííûå, à ÁÏ, óïðàâëÿþùèå ïðîâîäèìîñòüþ êîíòàêòîâÊÑ, íèêàê íå ñâÿçàíû ñ åå âõîäàìè.Ëåãêî âèäåòü, ÷òî ïåðåñòàíîâêà âõîäîâ(âûõîäîâ) ÊÑ ïîðîæäàåò â ðåàëèçóåìîé åþ ìàòðèöå òàêóþ æå ïåðåñòàíîâêóñâÿçàííûõ ñ íèìè ñòðîê (ñîîòâåòñòâåííî ñòîëáöîâ), à ñíÿòèå(äóáëèðîâàíèå) âûõîäîâ ýòîé ÊÑ óäàëåíèå (ñîîòâåòñòâåííî äîáàâëåíèå) ñâÿçàíûõ ñ íèìè ñòîëáöîâ. Çàìåòèì òàêæå,÷òî ÊÑ Σ, êîòîðàÿ ÿâëÿåòñÿ îáúåäèíåíèåì ÊÑ Σ0 è Σ00 , ðåàëèçóþùèõ ìàòðèöû F 0 è F 00 ñîîòâåòñòâåííî, ðåàëèçóåò ìàò-ïðîâîäíèêàìè9.Îïåðàöèÿ ñóïåðïîçèöèè.
Ëåììà Øåííîíà81ðèöó F âèäà1 :F =F0 00 F 00Îáðàòèìñÿ, äàëåå, ê îñîáåííîñòÿì ôóíêöèîíèðîâàíèÿ ÊÑ,ïîëó÷àþùèõñÿ â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèé ñóïåðïîçèöèè îáùåãî âèäà. Íàïîìíèì, ÷òî ñóïåðïîçèöèÿ îáùåãî âèäà ñâîäèòñÿ ê ïîñëåäîâàòåëüíîìó âûïîëíåíèþ îïåðàöèé ïåðåèìåíîâàíèÿ âûõîäîâ, äîáàâëåíèÿ òîæäåñòâåííûõ âåðøèíè ñòûêîâêè. Ïðè ýòîì ñòûêîâêà, â ñâîþ î÷åðåäü, ñâîäèòñÿê ñíÿòèþ âûõîäîâ, îòîæäåñòâëåíèþ âõîäîâ è áåñïîâòîðíîéñòûêîâêå.Çàìåòèì, ÷òî ðåçóëüòàò îòîæäåñòâëåíèÿ ïåðâûõ p âõîäîâ ÊÑ Σ ýêâèâàëåíòåí ðåçóëüòàòó ñòûêîâêè âèäà Σ (Σ0 ),à ðåçóëüòàò p-êðàòíîãî äóáëèðîâàíèÿ ïåðâîãî âûõîäà ÊÑΣ ðåçóëüòàòó ñòûêîâêè Σ00 (Σ), ãäå ÊÑ Σ0 , Σ00 ñîñòîÿò èç(1, p)-ïðîâîäÿùåé çâåçäû (ñì.
ðèñ. 9.2a, a âõîä) è òîæäåb ,ñòâåííûõ âåðøèí. Çàìåòèì òàêæå, ÷òî ñòûêîâêà âèäà Σ(Σ)b ñîñòîèò èç (p, 1)-ïðîâîäÿùåé çâåçäû (ñì. ðèñ. 9.2b,ãäå ÊÑ Σa âûõîä) è òîæäåñòâåííûõ âåðøèí, ñîîòâåòñòâóåò îòîæäåñòâëåíèþ ïåðâûõ p âûõîäîâ ÊÑ Σ. ñîîòâåòñòâèè ñ îáùèìè ïðàâèëàìè ñòûêîâêà (ñóïåðïîçèöèÿ) ÊÑ âèäà Σ = Σ00 (Σ0 ) íàçûâàåòñÿ2, åñëè000000äëÿ ìàòðèö F , F è F , ðåàëèçóåìûõ ÊÑ Σ, Σ è Σ ñîîòâåòñòâåííî, âûïîëíÿåòñÿ ðàâåíñòâîïðàâèëüíîéF = F 0 · F 00 .1(9.1)Ïðåäïîëàãàåòñÿ, ÷òî íîìåð ëþáîãî âõîäà (âûõîäà) ÊÑ Σ0 ìåíüøåíîìåðà ëþáîãî âõîäà (ñîîòâåòñòâåííî âûõîäà) ÊÑ Σ00 â ÊÑ Σ, à âíóòðåííÿÿ óïîðÿäî÷åííîñòü ïîëþñîâ ÊÑ Σ0 è Σ00 â ÊÑ Σ ñîõðàíÿåòñÿ. îñòàëüíûõ ñëó÷àÿõ ïðîèñõîäèò íåîáõîäèìàÿ ïåðåñòàíîâêà âõîäîâ èâûõîäîâ ÊÑ Σ.2Ýòî îïðåäåëåíèå ñîîòâåòñòâóåò ¾îáû÷íîìó¿ îïðåäåëåíèþ êîððåêòíîé ñóïåðïîçèöèè â ðàìêàõ ìîäåëè òàê íàçûâàåìûõ ïðåîáðàçóþùèõÊÑ.82Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì? ????? .
. . ????? . . . ?'. . . ??'?? ''?? ' . . . ?? '' ??' a1aa1 a2apapa2aa)b)?'. . . ??'?? ''?? '?? '' ??' y1ypy2z1c)Ðèñ. 9.2: ïðîâîäÿùèå è âåíòèëüíàÿ çâåçäû ïîðÿäêà pêîððåêòíîéÓêàçàííàÿ ñóïåðïîçèöèÿ ñ÷èòàåòñÿ, åñëè, êðîìå òîãî, â âûõîäíûõ âåðøèíàõ ïîäñõåìû Σ00 ñõåìû Σ ðåàëèçóþòñÿ òå æå ñàìûå ñòîëáöû ÔÀË, ÷òî è â ñàìîé ñõåìåΣ. Àíàëîãè÷íûì îáðàçîì îïðåäåëÿåòñÿ ïðàâèëüíîñòü è êîððåêòíîñòü ñóïåðïîçèöèè ÊÑ íà çàäàííîì íàáîðå çíà÷åíèéóïðàâëÿþùèõ ÁÏ.Çàìåòèì, ÷òî ïðè ïðàâèëüíîé ñòûêîâêå (1, p)-ÊÑ è (p,1)ÊÑ, ðåàëèçóþùèõñòðîêó è ñòîëáåö èç ÔÀË f10 , . .
. , fp0 è0000f1 , . . . , fp ñîîòâåòñòâåííî, ïîëó÷àåòñÿ (1, 1)-ÊÑ, ðåàëèçóþùàÿ ÔÀË f10 f100 ∨· · ·∨fp0 fp00 , ïðè ïðàâèëüíîì îòîæäåñòâëåíèèâõîäîâ (âûõîäîâ) ÊÑ â ðåàëèçóåìîé åþ ìàòðèöå ïðîèñõîäèòïîðàçðÿäíàÿ äèçúþíêöèÿ òåõ ñòðîê (ñîîòâåòñòâåííî ñòîëáöîâ), êîòîðûå ñîîòâåòñòâóþò îòîæäåñòâëåííûì âõîäàì (ñîîòâåòñòâåííî âûõîäàì) è ò.
ï.9.Îïåðàöèÿ ñóïåðïîçèöèè. Ëåììà Øåííîíà83Ëåãêî âèäåòü, ÷òî îïåðàöèÿ ïåðåèìåíîâàíèÿ âõîäîâ (âûõîäîâ) ÊÑ áåç îòîæäåñòâëåíèÿ, îïåðàöèÿ îáúåäèíåíèÿ ÊÑ,à òàêæå îïåðàöèÿ ïîñëåäîâàòåëüíîãî ñîåäèíåíèÿ (1, 1)-ÊÑ(ñì. 6) êîððåêòíû â ëþáîì ñëó÷àå.  òî æå âðåìÿ ïàðàëëåëüíîå ñîåäèíåíèå (1, 1)-ÊÑ, ïðè êîòîðîì ñíà÷àëà îòîæäåñòâëÿþòñÿ âõîäû, à çàòåì âûõîäû ñîåäèíÿåìûõ ÊÑ, íåÿâëÿåòñÿ, â îáùåì ñëó÷àå, êîððåêòíîé îïåðàöèåé ñóïåðïîçèöèè, õîòÿ ÿâëÿåòñÿ ïðè ýòîì ïðàâèëüíîé ñóïåðïîçèöèåé,òàê êàê ïîëó÷åííàÿ ÊÑ ðåàëèçóåò äèçúþíêöèþ ÔÀË, ðåàëèçóåìûõ èñõîäíûìè ÊÑ. Çàìåòèì, ÷òî êîððåêòíîå äèçúþíêòèðîâàíèå âûõîäíûõ ÔÀË ìîæíî îñóùåñòâèòü ñ ïîìîùüþñòûêîâêè èñõîäíîé ÊÑ ñ âåíòèëüíîé çâåçäîé (ñì.
ðèñ. 9.2c).Ñõåìà íàçûâàåòñÿ(),åñëè ÔÀË ïðîâîäèìîñòè ìåæäó ëþáûìè åå ðàçëè÷íûìè âõîäàìè (ñîîòâåòñòâåííî âûõîäàìè) ðàâíà 0. Òàê (p, 1)-ñõåìàΣ00 = Σ00 (y1 , . . . , yp ; z1 ), ïîêàçàííàÿ íà ðèñóíêå 9.2c, ÿâëÿåòñÿ ðàçäåëèòåëüíîé ïî âõîäàì ñõåìîé, êîòîðàÿ íàçûâàåòñÿp. Ïðèìåðîì ðàçäåëèòåëüíîéïî âûõîäàì (âõîäàì) ÊÑ ìîæåò ñëóæèòü (1, 2n ) (ñîîòâåòñòâåííî (2n , 1)) êîíòàêòíîå äåðåâî ïîðÿäêà n (ñì.
ðèñ. 6.4).Áóäåì ãîâîðèòü, ÷òî ÊÑ Σ îò ÁÏ x1 , . . . , xnα = (α1 , . . . , αn ) çíà÷åíèé ýòèõ ÁÏ, åñëè ñîîòâåòñòâóþùåé ðàçäåëèòåëüíîñòüþ îáëàäàåò ñåòü Σ|α . Ñëåäóþùåå óòâåðæäåíèå ÿâëÿåòñÿ îáîáùåíèåì èçâåñòíîé ëåììûØåííîíà (ñì. [31, 14]).ðàçäåëèòåëüíîé ïî âõîäàì âûõîäàìâåíòèëüíîé çâåçäîé ïîðÿäêàðàçäåëèòåëüíàíà íàáîðåÏóñòü ÊÑ Σ ÿâëÿåòñÿ ðåçóëüòàòîì ñòûêîâêè âèäà Σ = Σ00 (Σ0), à F , F 0 è F 00 ìàòðèöû, ðåàëèçóåìûåÊÑ Σ, Σ0 è Σ00 ñîîòâåòñòâåííî. ÒîãäàËåììà 9.1.F > F 0 · F 00è F = F 0 · F 00,(9.2)åñëè ÊÑ Σ00 ðàçäåëèòåëüíà ïî âõîäàì èëè ÊÑ Σ0 ðàçäåëèòåëüíà ïî âûõîäàì.84Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÄîêàçàòåëüñòâî. Ïóñòü ÊÑ Σ ÿâëÿåòñÿ ñíà÷àëà ðåçóëüòà-òîì áåñïîâòîðíîé ñòûêîâêè (p, q)-ÊÑ Σ0 è (q, s)-ÊÑ Σ00 îò ÁÏx1 , . .
. , xn . Ïóñòü, êðîìå òîãî, v 0 (v 00 ) ïðîèçâîëüíàÿ âåðøèíà ÊÑ Σ0 (ñîîòâåòñòâåííî Σ00 ), à ÔÀË fj0 (ñîîòâåòñòâåííî fj00 ),j ∈ [1, q], ÔÀË ïðîâîäèìîñòè îò âåðøèíû v 0 ê j -ìó âûõîäó â ÊÑ Σ0 (ñîîòâåòñòâåííî îò j -ãî âõîäà ê âåðøèíå v 00 âÊÑ Σ00 ). Äîêàæåì, ÷òî äëÿ ÔÀË f ÔÀË ïðîâîäèìîñòè îòâåðøèíû v 0 ê âåðøèíå v 00 â ÊÑ Σ, ñïðàâåäëèâî íåðàâåíñòâîf (x1 , . . . , xn ) > f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(9.3)êîòîðîå ïåðåõîäèò â ðàâåíñòâîf (x1 , . .
. , xn ) = f10 · f100 ∨ · · · ∨ fq0 · fq00 ,(9.4)åñëè ÊÑ Σ0 ðàçäåëèòåëüíà ïî âûõîäàì èëè ÊÑ Σ00 ðàçäåëèòåëüíà ïî âõîäàì.Äåéñòâèòåëüíî, ïóñòü aj , j ∈ [1, q], âåðøèíà ÊÑ Σ,êîòîðàÿ ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèñîåäèíåíèÿ j -ãî âõîäà ÊÑ Σ00 ê j -ìó âûõîäó ÊÑ Σ0 (ñì. ðèñ. 9.3a). Ñïðàâåäëèâîñòü íåðàâåíñòâà (9.3) ñëåäóåò èç òîãî, ÷òî åãî ïðàâàÿ÷àñòü îïèñûâàåò ¾ñóììàðíóþ¿ ïðîâîäèìîñòü òåõ (v 0 − v 00 )öåïåé ÊÑ Σ, êîòîðûå ïðîõîäÿò ÷åðåç âåðøèíû a1 , .
. . , aq ðîâíî îäèí ðàç (ñì. ðèñ. 9.3a). Ëþáàÿ äðóãàÿ (v 0 − v 00 )-öåïü ÊÑΣ ïðîõîäèò ÷åðåç óêàçàííûå âåðøèíû íå ìåíüøå òðåõ ðàç(ñì. ðèñ. 9.3b) è â ñëó÷àå ðàçäåëèòåëüíîñòè ÊÑ Σ0 ïî âûõîäàì èëè ðàçäåëèòåëüíîñòè ÊÑ Σ00 ïî âõîäàì èìååò íóëåâóþïðîâîäèìîñòü.Èç (9.3) è (9.4) íåïîñðåäñòâåííî âûòåêàåò (9.2) ñ ó÷åòîì òîãî, ÷òî ïðè v 0 = a0i è v 00 = a00j , ãäå i ∈ [1, p] è j ∈[1, s], ëåâàÿ(ïðàâàÿ) ÷àñòü ýòèõ ñîîòíîøåíèé ðàâíà ýëåìåíòó ìàòðèöû F (ñîîòâåòñòâåííî F 0 · F 00 ), ðàñïîëîæåííîìó âi-é ñòðîêå è j -ì ñòîëáöå.Ïóñòü òåïåðü ÊÑ Σ ïîëó÷àåòñÿ èç ÊÑ Σ00 â ðåçóëüòàòåïðèìåíåíèÿ îïåðàöèè îòîæäåñòâëåíèÿ âõîäîâ, òî åñòü Σ ýêâèâàëåíòíà áåñïîâòîðíîé ñòûêîâêå âèäà Σ00 (Σ0 ), ãäå ÊÑ Σ09.85Îïåðàöèÿ ñóïåðïîçèöèè. Ëåììà Øåííîíàa01a0p...••v0•a1 •Σ0• aqaj •Σ00•v 00...•a001•a00sa)a01•a1 ••a001a0p...••v0aj1 •Σ0...aj2 •...• aq• ajtv 00••a00sb)Ðèñ. 9.3: ê äîêàçàòåëüñòâó ëåììû 9.186Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìñîñòîèò èç ïðîâîäÿùåé çâåçäû è òîæäåñòâåííûõ âåðøèí.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
