OK-metodichka-2010-part2 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 10

7.8: îáîáùåííûå òîæäåñòâà ïîðÿäêà n äëÿ Êџ7.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõ ñõåì(n)Σ8→100 I2xn−1 xn9••999xn 9xn 2• xn−1I 00 •99−→ ⇒9t8 1t2xn−1 99•xn3xn−1•00Ix9 n•9⇒ 91t2xn 99•xn−132(n)⇒(n−1)t8,t2Σ̌83(n)Ðèñ. 7.9: âûâîä t8D 0zz• DDDI2n−1zDDzz•,z•2xn ,,, xn xn 222xn I10(n)Σ3⇒(n)t81−−−−→(n−1)t32n − 12•2 222xn xn12−−−−→(n−1)t32n•2 222xn xn2n2n − 1(n)Ðèñ. 7.10: âûâîä t3(n)⇒ Σ̌3t36970Ãëàâà 2.(n)Σ4Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìO00OOOvv−−−−→ vHHHo ⇒(n−1)1 x HHH ooo00oo 2 t4t4n•oo I2n−2I1xn vvv• OOOO•II•RRIIIxn−1xn RRRIRIIRRI00 xnxn−1 •UUUUIU1 UU(n)⇒ /?/? xnii ⇒ Σ̌4iii?// ?? xn−1(n−1)t4eii 00eeeeeeuu• I2n−2 t8xn // •e uuu// uuxn−1u•u(n)Ðèñ.

7.11: âûâîä t41(n)Σ5→21vvvvv x−→v•v nvt5vv0vv II0•I0xn31⇒t2I0•22xn22I0 2vv•vxvvv n3(n)(n−1)t53(n)Ðèñ. 7.12: âûâîä t5xn2xn 22vv•vv0vv I2−−−−→ Σ̌5•222⇒t2Ÿ8.Îòñóòñòâèå ÊÏÑÒ â êëàññå ÊÑ(n)71(n)âîé ÷àñòè Σ̌i òîæäåñòâà ti , n > ni , èç åãî ëåâîé ÷àñòè(n)Σi , ïîêàçàííàÿ íà ðèñ. 7.97.12.Ëåãêî âèäåòü, ÷òî âûâîäèìîñòènonono(n) (n)(n)(n) (n)(n) (n)t2 , t5⇒ t7 ,t7 , t5⇒ t10 , t11ïðè n > 2 äîêàçûâàþòñÿ àíàëîãè÷íî òîìó, êàê ýòî äåëàëîñüäëÿ ñëó÷àÿ n = 1 (ñì. ðèñ. 7.6, 7.7).Ëåììà äîêàçàíà.Ÿ8Ïîëíîòà ñèñòåìû îñíîâíûõ òîæäåñòâ èîòñóòñòâèå êîíå÷íîé ïîëíîé ñèñòåìûòîæäåñòâ â êëàññå êîíòàêòíûõ ñõåìÄîêàæåì ñíà÷àëà ïîëíîòó ñèñòåìû îñíîâíûõ òîæäåñòâ τ∞äëÿ ÝÏ ÊÑ. Äëÿ ýòîãî, êàê îáû÷íî, äîñòàòî÷íî äîêàçàòü,÷òî ñ ïîìîùüþ ÝÏ íà îñíîâå ñèñòåìû τ∞ ïðîèçâîëüíóþ ÊÑèç UK ìîæíî ïðèâåñòè ê êàíîíè÷åñêîìó âèäó.

Íàïîìíèìb 1 , . . . , xn ; a1 , . . . , am ), èëè,(ñì. Ÿ6), ÷òî êàíîíè÷åñêàÿ ÊÑ Σ(xèíà÷å,n, ïðåäñòàâëÿåò ñîáîé îáúb ij (x1 , . . . , xn ; ai , aj ),åäèíåíèå êàíîíè÷åñêèõ (1, 1)-ÊÑ âèäà Σïîñòðîåííûõ íà îñíîâå ñîâåðøåííûõ ÄÍÔ ÔÀË ïðîâîäèìîñòè îò ai ê aj äëÿ âñåõ i è j òàêèõ, ÷òî 1 6 i < j 6 m.(n)Ëþáóþ öåïü Ii (ñì. Ÿ7), ãäå i ∈ [1, 2n ], à òàêæå ëþáóþ(n)öåïü, êîòîðàÿ ïîëó÷àåòñÿ èç Ii ïåðåñòàíîâêîé êîíòàêòîâ,áóäåì íàçûâàòün. Çàìåòèì,b (x1 , .

. . , xn ; a1 , . . . , am ) ÿâëÿåòñÿ êàíîíè÷åñêîé ÊÑ÷òî ÊÑ Σïîðÿäêà n òîãäà è òîëüêî òîãäà, êîãäà îíà îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:êàíîíè÷åñêàÿ ÊÑ ïîðÿäêàêàíîíè÷åñêîé öåïüþ ïîðÿäêàb ïðèíàäëåæèò íåêîòîðîé êàíîíè÷å1. ëþáîé êîíòàêò Σb,ñêîé öåïè ïîðÿäêà n, ÿâëÿþùåéñÿ ïîäñõåìîé ñõåìû Σïðè÷åì ïîëþñàìè ýòîé ïîäñõåìû ñëóæàò òîëüêî êîíöåâûå âåðøèíû äàííîé öåïè;72Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìb ÿâëÿåòñÿ âíóòðåííåé âåð2.

ëþáàÿ âíóòðåííÿÿ âåðøèíà Σøèíîé íåêîòîðîé öåïè èç ïóíêòà 1;b îòñóòñòâóþò ¾âèñÿ÷èå öèêëû¿ (ñì. òîæäåñòâî3. â ÊÑ Σ(n)t6 ) è ¾ïàðàëëåëüíûå¿ öåïè, òî åñòü êàíîíè÷åñêèå öåïè ïîðÿäêà n èç ïóíêòà 1, êîòîðûå ñîåäèíÿþò îäíè èòå æå ïîëþñà è ðåàëèçóþò ðàâíûå ÝÊ;b íåò ñóùåñòâåííûõ òðàíçèòíûõ ïðîâîäèìîñòåé,4. â ÊÑ Σ(n)òî åñòü íàëè÷èå öåïåé âèäà Ii , ñîåäèíÿþùèõ ïîëþñaj ñ ïîëþñîì ak è ïîëþñ ak ñ ïîëþñîì at (ñì. ðèñ. 8.1a),âëå÷åò íàëè÷èå öåïè òàêîãî æå âèäà, ñîåäèíÿþùåé ïîëþñ aj ñ ïîëþñîì at (ñì. ðèñ. 8.1b).akpppp -(n)Ii ppp-- (n)ppp-I- ippp-ppajbΣakpppp -(n)Ii ppp-- (n)ppp-I- ipp=⇒pp\p\\\\\\\Ii\(n)\\\\\\\\-ajbΣata)atb)Ðèñ.

8.1: ê ñâîéñòâó 4 ÊÑ êàíîíè÷åñêîãî âèäàÄëÿ ëþáîé ÊÑ Σ, ãäå Σ ∈ UK è Σ == Σ (x1 , . . . , xn ; a1 , . . . , am ), è ëþáîé ýêâèâàëåíòíîé Σ ÊÑb (x1 , . . . , xn ; a1 , . . . , am ) êàíîíè÷åñêîãî âèäà ñóùåñòâóåòΣb.ÝÏ Σ ⇒ΣτËåììà8.1.nÄîêàçàòåëüñòâî. Ïîñòðîèì ÝÏ âèäàbΣ ⇒ Σ1 ⇒ Σ2 ⇒ Σ3 ⇒ Σ4 = Σ,τnτnτnτnŸ8.73Îòñóòñòâèå ÊÏÑÒ â êëàññå ÊÑãäå ÊÑ Σi , i = 1, 2, 3, 4, îáëàäàåò îòìå÷åííûìè âûøå ñâîéñòâàìè 1, .

. . , i, îòëè÷àþùèìè êàíîíè÷åñêèå ÊÑ. Ïåðâîå èçýòèõ ÝÏ èìååò âèäΣ ⇒ Σ1(n)t4è ñâÿçàíî ñ ïðèìåíåíèåì ê êàæäîìó êîíòàêòó òîæäåñòâà(n)t4 .Ñóùåñòâîâàíèå ÝÏΣ1n⇒(n) (n) (n) (n) (n)t6 , t11 , t9 , t3 , t1Σ2o(8.1)äîêàæåì èíäóêöèåé ïî ÷èñëó òåõ âíóòðåííèõ âåðøèí ÊÑ Σ1 ,êîòîðûå íå ÿâëÿþòñÿ âíóòðåííèìè âåðøèíàìè åå êàíîíè÷åñêèõ öåïåé. Áàçèñ èíäóêöèè ñîñòàâëÿþò ñõåìû Σ1 , êîòîðûåíå èìåþò óêàçàííûõ âåðøèí è äëÿ êîòîðûõ, ñëåäîâàòåëüíî,Σ2 = Σ1 .

Ïóñòü òåïåðü ÊÑ Σ1 èìååò õîòÿ áû îäíó âåðøèíóóêàçàííîãî âèäà è ïóñòü v îäíà èç òàêèõ âåðøèí. Óäà(n)ëèì ñ ïîìîùüþ òîæäåñòâà t6 âñå ïðèñîåäèíåííûå ê v ¾âèñÿ÷èå¿ öèêëû è ðàññìîòðèì âñå îñòàëüíûå öåïè C1 , . . . , Cq ,êîíöåâîé âåðøèíîé êîòîðûõ îíà ÿâëÿåòñÿ (ñì. ðèñ. 8.2a).Íå îãðàíè÷èâàÿ îáùíîñòè ðàññóæäåíèé, áóäåì ñ÷èòàòü, ÷òîäëÿ íåêîòîðûõ íàòóðàëüíûõ ÷èñåëa1 = 1 < a2 < · · · < ap < ap+1 = q + 1è ëþáîãî j, j ∈ [1, p], öåïè Caj , . . .

, Caj+1 −1 ÿâëÿþòñÿ öåïÿ(n)ìè òèïà Iij = Iij , ãäå i1 , . . . , ip ðàçëè÷íûå ÷èñëà îòðåçêà[1, 2n ]. Ïðèìåíÿÿ ê êàæäîé èç ýòèõ p ãðóïï öåïåé îäíîãî òè(n)ïà òîæäåñòâî t11 , ïîëó÷èì ÊÑ Σ01 , â êîòîðîé èç âåðøèíûv âûõîäèò ïî îäíîé öåïè êàæäîãî òèïà Iij , j ∈ [1, p] (ñì.ðèñ. 8.2b). Ïóñòü, äàëåå, ÊÑ Σ001 ïîëó÷àåòñÿ èç ÊÑ Σ01 ïðèñî(n)åäèíåíèåì ê âåðøèíå v ñ ïîìîùüþ òîæäåñòâà t9 ¾âèñÿ÷èõ¿74Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì UU ZZUZUZUZUCZU1UU v iCiqidididididiidddZZZUZU iZdiZ....UdUZIi1ZZZddddidi" U d.

ididididiiii "" UUUUZUZUZUZU.i Ca −1 "Cap "2 "Ca2 "" C " a3 −1 . . . "Σ1| {z }Ii2a)vv2n p+1222Cp+1C2n 2222 Ii1 2v Iip\\\\\\ v⇒ v1p(n)t9Ii2 v2I ip⇒v1vv\\\Ii\p\\pIi2 v2 Ii1(n)t11v2n b)−−→ v1 (n)t3(n)vp+1 vp ⇒ Σ0001v2c)⇒t9(n)t1d)Ðèñ. 8.2: ê äîêàçàòåëüñòâó ëåììû 8.1öåïåé Cp+1 , . . . , C2n âñåõ îòñóòñòâóþùèõ ñðåäè Ii1 , . . . , Iip òè00ïîâ (ñì.

ðèñ. 8.2c), à ÊÑ Σ0001 ïîëó÷àåòñÿ èç ÊÑ Σ1 â ðåçóëüòà(n)òå óäàëåíèÿ ñ ïîìîùüþ òîæäåñòâà t3 âåðøèíû v âìåñòå ñîâñåìè ¾èíöèäåíòíûìè¿ åé öåïÿìè è óñòðàíåíèÿ ñ ïîìîùüþòîæäåñòâà t1 îáðàçîâàâøèõñÿ ïðè ýòîì èçîëèðîâàííûõ âåðøèí êîíöåâûõ âåðøèí öåïåé Cp+1 , . . . , C2n (ñì. ðèñ. 8.2d).Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ äëÿ ÊÑ Σ000 ñóùåñòâóåòÝÏ âèäàΣ000 n⇒Σo 2(n)(n)(n)(n)(n)t6 , t11 , t9 , t3 , t1è, ñëåäîâàòåëüíî, äëÿ ÊÑ Σ1 ñóùåñòâóåò ÝÏ (8.1).Ïåðåõîä îò ÊÑ Σ2 ê ÊÑ Σ3 îñóùåñòâëÿåòñÿ ñ ïîìîùüþŸ8.75Îòñóòñòâèå ÊÏÑÒ â êëàññå ÊÑ(n)(n)òîæäåñòâ t6 è t7 , à îò ÊÑ Σ2 ê ÊÑ Σ3 ñ ïîìîùüþ òîæ(n)äåñòâ t10 .Ëåììà äîêàçàíà.Äëÿ ëþáûõ äâóõ ýêâèâàëåíòíûõ ÊÑ Σ0 è Σ00îò ÁÏ x1, .

. . , xn ñóùåñòâóåò ÝÏ âèäà Σ0 ⇒Σ00 .τÒåîðåìà 8.1.nÄîêàçàòåëüñòâî. Ïóñòü Σb 0 è Σb 00 êàíîíè÷åñêèå ÊÑ îò ÁÏx1 , . . . , xn , ýêâèâàëåíòíûå ÊÑ Σ0 è Σ00 ñîîòâåòñòâåííî. Èçb0 ⇒ Σb 00 , è ïîýòîìó, â ñèëó ëåìîïðåäåëåíèé ñëåäóåò, ÷òî Σ(n)t2ìû 8.1, ñóùåñòâóåò ÝÏ âèäàb0 ⇒ Σb 00 ⇒ Σ00 .Σ0 ⇒ Στn(n)t2τnÒåîðåìà äîêàçàíà.Ñèñòåìà τn ÿâëÿåòñÿ ÊÏÑÒ äëÿ ÝÏ ÊÑ èçîò ÁÏ x1, . .

. , xn.Ñèñòåìà τ∞ ÿâëÿåòñÿ ÏÑÒ äëÿ ÝÏ ÊÑ èçÑëåäñòâèå 1.UKÑëåäñòâèå 2.UK.Äîêàæåì òåïåðü îòñóòñòâèå ÊÏÑÒ â êëàññå UK . Äëÿ ÊÑ Σîò ÁÏ x1 , . . . , xn è íàáîðà α, α ∈ B n , îïðåäåëèì âåëè÷èíóΘ (Σ, α) = |E (Σ|α )| − |V (Σ|α )| + |c (Σ|α )| ,êîòîðàÿ (ñì. Ÿ1) çàäàåò öèêëîìàòè÷åñêîå ÷èñëî ãðàôà Σ|α .Ïîëîæèì, äàëåå,Θ (Σ) =Xα∈B nΘ (Σ, α) .76Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÅñëè Σ0 (x1, . . . , xn) ⇒ Σ00 (x1, . .

. , xn), òî{t −t }Θ (Σ0 ) = Θ (Σ00 ), à åñëè Σ0 ⇒ Σ00 , ãäå k < n, òî Θ (Σ0 )−Θ (Σ00 )τäåëèòñÿ íà 2n−k .Äîêàçàòåëüñòâî. Äîêàæåì, ÷òî Θ(Σ0)=Θ(Σ00), åñëè Σ0−→Σ00tËåììà 8.2.15kiäëÿ ëþáîãî i èç îòðåçêà [1, 5]. Äåéñòâèòåëüíî, ïóñòü ÊÑ Σ00b 0 , êîòîðàÿ èìåïîëó÷àåòñÿ èç ÊÑ Σ0 çàìåíîé åå ïîäñõåìû Σiåò âèä ëåâîé ÷àñòè òîæäåñòâà ti , íà ñîîòâåòñòâóþùóþ åéb 00 ýòîãî òîæäåñòâà. Íåòðóäíî ïðîâåðèòü, ÷òîïðàâóþ ÷àñòü Σiäëÿ ëþáîãî i, i ∈ [1, 5], ÷èñëî ëèíåéíî íåçàâèñèìûõ öèêëîâ ãðàôîâ Σ|α0 è Σ|α00 îäèíàêîâî ïðè âñåõ α, α ∈ B n , è,ñëåäîâàòåëüíî, Θ (Σ0 ) = Θ (Σ00 ).Ïóñòü òåïåðü Σ0 ⇒ Σ00 , ïðè÷åì k < n.

Åñëè ÊÑ Σ0 ñîτkäåðæèò â êà÷åñòâå ïîäñõåìû öèêë èç k êîíòàêòîâ ñ îäíèìïîëþñîì, òî ÊÑ Σ00 ñîäåðæèò âìåñòî íåãî îäèí ëèøü ïîëþñ. Ðàññìîòðèì öèêëîìàòè÷åñêîå ÷èñëî ñåòè Σ0 |α äëÿ ðàçëè÷íûõ α, α ∈ B n . Åñëè öèêë óêàçàííîãî âèäà â ÊÑ Σ0ñîäåðæèò êîíòàêòû, ïîìå÷åííûå ðàçëè÷íûìè áóêâàìè îäíîé è òîé æå ÁÏ, òî, î÷åâèäíî, äëÿ ëþáîãî α, α ∈ B n ,Θ (Σ0 )−Θ (Σ00 ) = 0.  ïðîòèâíîì ñëó÷àå, ïóñòü xj1 , . . . , xjm âñå ðàçëè÷íûå ÁÏ, âñòðå÷àþùèåñÿ ñðåäè ïîìåòîê óêàçàííîãî öèêëà, ïðè÷åì m 6 k . Çàìåòèì, ÷òî åñëè öèêë ïðîâîäèòíà íàáîðå α, α ∈ B n , òî îí ïðîâîäèò è íà âñåõ 2n−m íàáîðàõ, â êîòîðûõ çíà÷åíèÿ ïåðåìåííûõ ñ èíäåêñàìè j1 , .

. . , jmñîâïàäàþò ñî çíà÷åíèÿìè ñîîòâåòñòâóþùèõ ïåðåìåííûõ íàáîðà α. Òàêèì îáðàçîì, ðàçíîñòüΘ Σ0 − Θ Σ00 =XΘ Σ0 |α − Θ Σ00 |αα=(α1 ,...,αn )äåëèòñÿ íà 2n−m è, ñëåäîâàòåëüíî, äåëèòñÿ íà 2n−kËåììà äîêàçàíà.Ÿ9.Îïåðàöèÿ ñóïåðïîçèöèè. Ëåììà Øåííîíà77 êëàññå UK íå ñóùåñòâóåò êîíå÷íîé ïîëíîéñèñòåìû òîæäåñòâ.Äîêàçàòåëüñòâî.