С.А. Ложкин - Лекции по основам кибернетики (2010) (1132804), страница 10
Текст из файла (страница 10)
Íàïîìíèì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τn8.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 v2I 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 íå ñóùåñòâóåò êîíå÷íîé ïîëíîéñèñòåìû òîæäåñòâ.Äîêàçàòåëüñòâî. Ïðîâåäåì äîêàçàòåëüñòâî îò ïðîòèâíîãî:Òåîðåìà 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.Îïåðàöèÿ ñóïåðïîçèöèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
