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

. , xn ; a1 ; a2 ), Σ ∈ UK (L, n), è âûäåëèì â íåé îñòîâíîå äåðåâî D ñ êîðíåì a2 òàê, ÷òîáû â D âîøëè âñå èíöèäåíòíûå a2 êîíòàêòû Σ, à âåðøèíà a1 áûëà ëèñòîì D. Ïóñòü,äàëåå, D0 ñâÿçàííîå ñ D îñòîâíîå íàääåðåâî ÊÑ Σ, êîòîðîåïîëó÷àåòñÿ ïóòåì ïðèñîåäèíåíèÿ êàæäîãî èç íå âîøåäøèõâ D ðåáåð Σ ê îäíîé èç ñâîèõ êîíöåâûõ âåðøèí, îòëè÷íîéîò a1 (ñì. Ÿ1). Ðàññìîòðèì îðèåíòèðîâàííîå óïîðÿäî÷åííîåäåðåâî D00 , ïîëó÷àþùååñÿ èç D0 ââåäåíèåì (óñëîâíîé) îðèåíòàöèè âñåõ åãî ðåáåð ïî íàïðàâëåíèþ ê êîðíþ è òàêèì èõ60Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìóïîðÿäî÷åíèåì, ïðè êîòîðîì âåðøèíà a1 ñòàíîâèòñÿ ïåðâûìëèñòîì D00 (ñì.

Ÿ1).Çàìåòèì, ÷òî ÷èñëî ðåáåð (âåðøèí, ëèñòüåâ) äåðåâà D00íå áîëüøå, ÷åì L (ñîîòâåòñòâåííî L + 1, L), è ïîýòîìó, âñèëó (1.4), ÷èñëî òàêèõ äåðåâüåâ ñ ó÷åòîì ïîìåòîê èõ ðåáåð ñèìâîëàìè x1 , . . . , xn , x1 , . . . , xn íå áîëüøå, ÷åì (8n)L .Çàìåòèì òàêæå, ÷òî ÊÑ Σ ìîæåò áûòü ïîëó÷åíà â ðåçóëüòàòå ïðèñîåäèíåíèÿ êàæäîãî ëèñòà äåðåâà D00 ê îäíîé èç åãîâåðøèí, îòëè÷íîé îò a2 . Ñëåäîâàòåëüíî, KU (L, n) 6 UK (L, n) 6 (8nL)L .Ëåììà äîêàçàíà.Ðàññìîòðèì, â çàêëþ÷åíèå, îñîáåííîñòè ôóíêöèîíèðîâàíèÿ ÊÑ ñ íåñêîëüêèìè âõîäàìè.

Áóäåì ñ÷èòàòü, ÷òî â êàæäîé âåðøèíå (p, q)-ÊÑ Σ ðåàëèçóåòñÿ ñòîëáåö, ñîñòàâëåííûéèç p ÔÀË ïðîâîäèìîñòè îò âõîäîâ Σ ê ýòîé âåðøèíå, à ñàìàÊÑ Σ ðåàëèçóåò ìàòðèöó, êîòîðàÿ ñîñòîèò èç q ñòîëáöîâ, ðåàëèçîâàííûõ íà åå âûõîäàõ. Òàêèì îáðàçîì, ôóíêöèîíèðîâàíèåÊÑΣ == Σ x1 , . . . , xn ; a01 , .

. . , a0p ; a001 , . . . , a00q ïðåäñòàâëÿåò ñîáîéìàòðèöó F = F (x1 , . . . , xn ) ñ p ñòðîêàìè, q ñòîëáöàìè è ýëåìåíòàìè èç P2 (n), äëÿ êîòîðîé F hi, ji ÔÀË, ðåàëèçóåìàÿìåæäó a0i è a00j , ãäå i ∈ [1, p] è j ∈ [1, q], òî åñòü ïðè ëþáîì α, α ∈ B n , ìàòðèöà F (α) ÿâëÿåòñÿ ìàòðèöåé äîñòèæèìîñòè ñåòè Σ|α .  ÷àñòíîñòè, ôóíêöèîíèðîâàíèå (1, q)-ÊÑïðåäñòàâëÿåò ñîáîé íàáîð (ñòðîêó) èç q ÔÀË ïðîâîäèìîñòè îò åå âõîäà ê âûõîäàì, à ôóíêöèîíèðîâàíèå (p, 1)-ÊÑ ñòîëáåö èç p ÔÀË ïðîâîäèìîñòè îò åå âõîäîâ ê âûõîäó.Òàê, ÊÑ Σ (x1 , x2 , x3 ; a1h, v; a2i, a3 ), ïîêàçàííàÿ íà ðèñóíêå 6.3c ðåàëèçóåò ìàòðèöó ll3 ll3 îò ÁÏ X(3), à íà ðèñ. 6.4b3 3ïðèâåäåíî (2n , 1)-ÊÄ ïîðÿäêà n îò ÁÏ X (n), êîòîðîå èìååò âèä D (x1 , .

. . , xn ; a0 , . . . , a2n −1 ; a) è ðåàëèçóåò ñòîëáåö èçŸ7.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõ ñõåì61âñåõ ÝÊ ìíîæåñòâà Qn , óïîðÿäî÷åííûõ ñâåðõó âíèç ïî âîçðàñòàíèþ èõ íîìåðîâ. ñîîòâåòñòâèè ñ îáùèìè ïðàâèëàìè èç Ÿ1, ôóíêöèîíèðîâàíèå ÊÑ Σ = Σ (x1 , . . . , xn ; a1 , . . . , am ) ñ íåðàçäåëåííûìè ïîëþñàìè îïðåäåëÿåòñÿ êàê ôóíêöèîíèðîâàíèå ÊÑ ñðàçäåëåííûìè ïîëþñàìè âèäà Σ (x1 , .

. . , xn ; a1 , . . . , am ; a1 , . . . , am ). ýòîì ñëó÷àå ìàòðèöà F ÿâëÿåòñÿ ðåôëåêñèâíîé è òðàíçèòèâíîé ìàòðèöåé, à åñëè, êðîìå òîãî, Σ íåîðèåíòèðîâàííàÿ ñåòü, òî è ñèììåòðè÷íîé ìàòðèöåé. Çàìåòèì òàêæå, ÷òî ôóíêöèîíèðîâàíèå (1, 1)-ÊÑ èç íåîðèåíòèðîâàííûõêîíòàêòîâ ïî ñóùåñòâó íå îòëè÷àåòñÿ îò ôóíêöèîíèðîâàíèÿñîîòâåòñòâóþùåé äâóõïîëþñíîé ÊÑ ñ íåðàçäåëåííûìè ïîëþñàìè. ÷àñòíîñòè, ïîêàçàííàÿ íà ðèñ. 6.3c ÊÑ ñ íåðàçäåëåííûìè ïîëþñàìè a1 , a2 , a3 ðåàëèçóåò ìàòðèöó1 l3 l 3l3 1 0l3 0 1, ÊÑ èçòîæäåñòâåííûõ âåðøèí ðåàëèçóåò åäèíè÷íóþ ìàòðèöó, åñëè êàæäàÿ åå âåðøèíà ÿâëÿåòñÿ âõîäîì è âûõîäîì ñ îäíèìè òåì æå íîìåðîì è ò.

ä.Ñ äðóãîé ñòîðîíû, ëþáàÿ ñèììåòðè÷åñêàÿ, òðàíçèòèâíàÿ è ðåôëåêñèâíàÿ ìàòðèöà F , F ∈ (P2 (n))m,m , ðåàëèçóåòñÿ ÊÑ Σ = Σ (x1 , . . . , xn ; a1 , . . . , am ), êîòîðàÿ ïðåäñòàâëÿåòñîáîé îáúåäèíåíèå âñåõ ÊÑ Σij = Σij (x1 , . . . , xn ; ai , aj ), ãäå1 6 i < j 6 m, à ÊÑ Σij ÿâëÿåòñÿ π -ñõåìîé è ïîñòðîåíà ïîñîâåðøåííîé ÄÍÔ ÔÀË F hi, ji è ñ÷èòàåòñÿF.ÊÑ ìàòðèöûŸ7êàíîíè÷åñêîéÝêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõñõåì. Îñíîâíûå òîæäåñòâà, âûâîäâñïîìîãàòåëüíûõ è îáîáùåííûõ òîæäåñòâÐàññìîòðèì âîïðîñû ÝÏ äëÿ ÊÑ èç UK ñ íåðàçäåëåííûìè (áåñïîâòîðíûìè) ïîëþñàìè.

 ñîîòâåòñòâèè ñ Ÿ1 ýêâèâàëåíòíîñòü ÊÑ Σ0 = Σ0 (x1 , . . . , xn ; a1 , . . . , am ) è Σ00 = Σ00 (x1 , . . . , xn ; a1 , . . . , am ),62Ãëàâà 2.a) t1 :b) t2 :Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìx1c) t3 :x11x1∼2x2∼ ∅∼2•1d) t4 :x2•1•11x2x1•22O xx2 oooo• OOOO1∼2OOOooOoOooOOo1 x OOO ooox o 2Ooo 12•e) t5 :ooo 2oooo x1x11∼3(m)f) t63r•LLLL xLL2LLLx1 rrr:rr,rr1 ,,,,,xm,,x1OOOO1 x OOO1•∼ 1•Ðèñ.

7.1: îñíîâíûå òîæäåñòâà äëÿ ÊÑ2Ÿ7.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõ ñõåìa) bt4 :b) bt5 :11x1x1x122∼∼63O xx1 oooo• OOOOO1OOoooOoOo1 xOOOOO oooxoo 2O•oo 111x12x1Ðèñ. 7.2: ïîäñòàíîâêè äëÿ îñíîâíûõ òîæäåñòâòî åñòü ñïðàâåäëèâîñòü òîæäåñòâà t : Σ0 ∼ Σ00 îçíà÷àåò, ÷òîäëÿ ëþáûõ i è j èç îòðåçêà [1, m] ÔÀË ïðîâîäèìîñòè îò ai êaj â ÊÑ Σ0 ðàâíà ÔÀË ïðîâîäèìîñòè îò ai ê aj â ÊÑ Σ00 . Íàðèñ. 7.1a7.1e è 7.1f ïðèâåäåíû ïàðû ýêâèâàëåíòíûõ ÊÑ, îá(m)ðàçóþùèå òîæäåñòâà t1 t5 è t6 , m = 1, 2, . . ., ñîîòâåòñòâåííî, êîòîðûå ìû áóäåì íàçûâàòüäëÿ ÝÏ ÊÑ.Îïðåäåëèì ïîäñòàíîâêó äëÿ ÊÑ êàê ïåðåèìåíîâàíèå (ñâîçìîæíûì îòîæäåñòâëåíèåì è èíâåðòèðîâàíèåì) ÁÏ, à òàêæå ïåðåèìåíîâàíèå (ñ âîçìîæíûì îòîæäåñòâëåíèåì è ñíÿòèåì) ïîëþñîâ. Çàìåòèì, ÷òî ïðèìåíÿÿ îäíó è òó æå ïîäñòàíîâêó ê äâóì ýêâèâàëåíòíûì ÊÑ, ìû ïîëó÷èì ýêâèâàëåíòíûå ÊÑ. Äåéñòâèòåëüíî, äëÿ ïåðåèìåíîâàíèÿ ÁÏ è ïåðåèìåíîâàíèÿ áåç îòîæäåñòâëåíèÿ ïîëþñîâ ýòî î÷åâèäíî, àâ ñëó÷àå îòîæäåñòâëåíèÿ ïîëþñîâ ýêâèâàëåíòíîñòü ïîëó÷àåìûõ ÊÑ âûòåêàåò èç òîãî, ÷òî ìàòðèöà äîñòèæèìîñòè ÊÑ,ÿâëÿþùåéñÿ ðåçóëüòàòîì îòæäåñòâëåíèÿ, îäíîçíà÷íî îïðåäåëÿåòñÿ ìàòðèöåé äîñòèæèìîñòè èñõîäíîé ÊÑ.

Íà ðèñ. 7.2a(7.2b) ïîêàçàíà ïîäñòàíîâêà bt4 òîæäåñòâà t4 (ñîîòâåòñòâåííî bt5 òîæäåñòâà t5 ), ñâÿçàííàÿ ñ ïåðåèìåíîâàíèåì ÁÏ x2 âx1 (ñîîòâåòñòâåííî ïîëþñîâ 1 = 3 â 1).îñíîâíûìè òîæäåñòâàìè64Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìÏîíÿòèå ïîäñõåìû äëÿ ÊÑ èç ðàññìàòðèâàåìîãî êëàññàîïðåäåëÿåòñÿ àíàëîãè÷íî Ÿ5 ñ ó÷åòîì íåðàçäåëåííîñòè ïîëþñîâ. Ýòî îçíà÷àåò, ÷òî äëÿ ïîäñõåìû Σ0 ÊÑ Σ èìååò ìåñòî âêëþ÷åíèå V (Σ0 ) ⊂ V (Σ) è E(Σ0 ) ∈ E(Σ), à ïîëþñàìèΣ0 ÿâëÿþòñÿ âñå ïðèíàäëåæàùèå åé ïîëþñà ÊÑ Σè âñå òå ååâåðøèíû, êîòîðûå èíöèäåíòíû â Σ ðåáðàì èç E(Σ) \ E(Σ0 ),è, âîçìîæíî, íåêîòîðûå äðóãèå âåðøèíû.

Ïðè òàêîì îïðåäåëåíèè ïîäñõåìû äëÿ ðàññìàòðèâàåìîãî êëàññà ÊÑ áóäåòâûïîëíÿòüñÿ ïðèíöèï ýêâèâàëåíòíîé çàìåíû.Ðàññìîòðèì ïðèìåðû ÝÏ êîíòàêòíûõ ñõåì ñ ïîìîùüþñèñòåìû îñíîâíûõ òîæäåñòâ. Íà ðèñ. 7.3a7.3e ïðèâåäåíûòîæäåñòâà t7 t11 , êîòîðûå ìû áóäåì íàçûâàòü(1). Çàìåòèì, ÷òî âûâîäèìîñòü {t5 , t6 } ⇒ t7 äîêàçûâàåò(1)ñÿ ïðèìåíåíèåì òîæäåñòâà t6 ê ïðàâîé ÷àñòè òîæäåñòâà bt5(ñì. ðèñ. 7.2a) äëÿ óäàëåíèÿ èç íåå ¾âèñÿ÷åãî¿ öèêëà äëèíû 1. Âûâîäèìîñòü òîæäåñòâ t8 t11 èç îñíîâíûõ òîæäåñòâ(1) (2){t1 − t5 , t6 , t6 } ïîêàçàíà íà ðèñ.

7.47.7 ñîîòâåòñòâåííî,ãäå Σi è Σ̌i ëåâàÿ è ïðàâàÿ ÷àñòè òîæäåñòâà ti , i ∈ [8, 11].Òîæäåñòâî t10 íàçûâàþò èíîãäà òîæäåñòâîì çàìûêàíèÿ ïîòðàíçèòèâíîñòè, à òîæäåñòâî t11 ¾ëåììîé¿ î çâåçäå.Îáîáùèì òîæäåñòâà t1 t11 íà ñëó÷àé ÊÑ îò ÁÏ X (n),ãäå n > 2. Äëÿ êàæäîãî i, i ∈ [1, 2n ], ñîïîñòàâèì ÝÊ âèäà xσ1 1 · · · xσnn , ãäå ν (σ1 , . . . , σn ) = i − 1, ìîäåëèðóþùóþ åå(n)öåïî÷êó Ii (ñì. Ÿ6), è ïóñòüâñïîìîãàòåëü-íûìè(n)Ii(n−1)Ii(n−2)Iii ∈ [1, 2n ] ,= Ii0 , i ∈ 1, 2n−1 ,= Ii00 , i ∈ 1, 2n−2 ,= Ii ,I = I2n ;I 0 = I20 n−1 ;I 00 = I200n−2 .no(n)(n)(n)(n)Ñèñòåìó òîæäåñòâ τ (n) = t1 , .

. . , t11 , ãäå t1 = t1 , t6 (n)ñîîòâåòñòâóþùåå îñíîâíîå òîæäåñòâî (ñì. ðèñ. 7.1f), t2 ñèñòåìà, ñîñòîÿùàÿ èç òîæäåñòâ, ïîêàçàííûõ íà ðèñ. 7.8a,Ÿ7.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõ ñõåìa) t7 :x11b) t8 :12tt 2ttttJ•JJJJx2 J∼∼3x1 oooo•ooo∼oc) t9 :11x1d) t10 :1Oe) t11 :m 2 x12 ∼33OOO x1 x1 oooOOO ooox1ooo 0ooooo x11x1x1tJtJt1 x JJJJ1•x2 2 31x177 21 777x1 77 x17 14∼2x2x1 ttt•x2x13x1 4x1 44x1444m 4404x1 44424444x14 3Ðèñ. 7.3: âñïîìîãàòåëüíûå òîæäåñòâà äëÿ ÊÑ6566Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì•2Jx1 yyyx1 ttt• JJJx2 x2 ttytJytJJ ttyt⇒ EyEEΣ8 −→ JtJJt•tJJt4 1JJ tttt JJJJ1EEt5x1 Jtt x2 x2 x1 EE••32yyyyyyEy x2•E−→ Σ̌8EEx2t3EEEx2x2Ðèñ.

7.4: âûâîä t8Σ9 −→t7x1•x11−−→ Σ̌9(2)t6Ðèñ. 7.5: âûâîä t91Σ10 −→t72x1 −→ Σ̌10 xt51x13Ðèñ. 7.6: âûâîä t103Ÿ7.Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ êîíòàêòíûõ ñõåì1O2 OOO x1 oooOox1 Ooo x1oooo 0oo x1Σ11 −→t7moo 21Ooooox13x1673OOOx1 oooOox1 Ooo−→ot5oxoo 0oo1x1−→t5m2oo OOOxO1OooO 31OooOOOx1 oooOox1 Ooo⇒ Σ̌11oooo 0t5oo x1x1−→t5mÐèñ. 7.7: âûâîä t11ãäå Ie ïðîèçâîëüíàÿ ïåðåñòàíîâêà öåïî÷êè I , à îñòàëüíûåòîæäåñòâà ïðèâåäåíû íà ðèñ.

7.8b7.8i, áóäåì íàçûâàòü ñèñòåìîén. Ïðè ýòîì ñèñòåìàno(1)(n)τn = t1 , . . . , t5 , t6 , . . . , t6ñ÷èòàåòñÿ ñèñòåìîé îñíîâíûõòîæäåñòâ ïîðÿäêà n, à ñèñòåìà âñåõ îñíîâíûõ òîæäåñòâ îáîçíà÷àåòñÿ ÷åðåç τ∞ .îáîáùåííûõ òîæäåñòâ ïîðÿäêàÏðè n>2 èìååò ìåñòî âûâîäèìîñòü τn ⇒τ (n).Äîêàçàòåëüñòâî. Îòìåòèì ñíà÷àëà ñëåäóþùèå î÷åâèäíûåËåììà 7.1.âûâîäèìîñòè:(n){t2 } ⇒ t2 ,(n)(n){t9 } ⇒ t9 .Âûâîäèìîñòü τn ⇒ ti , i = 8, 3, 4, 5, äîêàæåì èíäóêöèåéïî n, n > ni , ãäå n3 = n5 = 1 è n8 = n4 = 2.

Áàçèñ ýòîé(n )èíäóêöèè ñîñòàâëÿåò òîæäåñòâî ti = ti i , i = 8, 3, 4, 5, àîáîñíîâàíèå èíäóêòèâíîãî ïåðåõîäà äàåò âûâîäèìîñòü ïðà-68a)Ãëàâà 2.(n)t2Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåì:1I2r•LLrrr LLLIL2Lnrr I2LLrrr∼1I1b)c)d)e)f)(n)t3(n)t4(n)t5(n)t7(n)t8(n):1:1:1:1h)t10 :(n)11O(n)t11 :2{{{ 2{{{ I30I2pp 2ppNNN•pNNxn ∼∼∼ 2 I2 2n2•RRR I 0l•[[[R[R[R1RRR[[[[R8lxlnI20 mmm1 8882mmxn 8 mmm0mm I n−1•2C1 CCCC1IC∼3I2Ippp•NpNp1 0NNNxn•I∼13xn 2 3 2?  I?1 ????I2I01I2II gg•gggg∼1Iexnxn3OOO I I oooOoOooIoo 0oooo Im∼3:t9IxnI1:g)i)2n2I13I4244 I 444 I44 44 34m 4404I 4I∼Ðèñ.