2. Проблемы ограниченности и безопасности для обыкновенных сетей Петри. Деревья покрытия разметок сетей Петри (Лекция)

Ìîäåëèïîñëåäîâàòåëüíûõèïàðàëëåëüíûõâû÷èñëåíèéÂ.À. ÇàõàðîâËåêöèÿ 2.1.Ïðîáëåìû îãðàíè÷åííîñòè èáåçîïàñíîñòè äëÿ ñåòåé Ïåòðè2.Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåéÏåòðè3.Âàðèàíòû ïðîáëåìû äîñòèæèìîñòè4.Ïðîáëåìû æèâîñòè è äîñòèæèìîñòèäëÿ ñåòåé ÏåòðèÏðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏîçèöèÿ p â ñåòè Ïåòðè π = (P, T , F , W , M) íàçûâàåòñÿîãðàíè÷åííîé , åñëè ñóùåñòâóåò òàêîå ÷èñëî n , ÷òî äëÿ ëþáîéðàçìåòêè M 0, M 0 ∈ R(π) , âåðíî ðàâåíñòâî M 0(p) ≤ n .Ñåòü Ïåòðè íàçûâàåòñÿ îãðàíè÷åííîé , åñëè ëþáàÿ åå ïîçèöèÿîãðàíè÷åíà.Ïðîáëåìà îãðàíè÷åííîñòè ñîñòîèò â òîì, ÷òîáû äëÿïðîèçâîëüíîé çàäàííîé ñåòè Ïåòðè ïðîâåðèòü, ÿâëÿåòñÿ ëè îíàîãðàíè÷åííîé.Î÷åâèäíî, ÷òî ñåòü Ïåòðè îãðàíè÷åíà òîãäà è òîëüêî òîãäà,êîãäà ìíîæåñòâî åå äîñòèæèìûõ ðàçìåòîê R(π) êîíå÷íî.×òîáû óáåäèòüñÿ â ýòîì, äîñòàòî÷íî ïîñòðîèòü ãðàôäîñòèæèìûõ ðàçìåòîê G (π) è óáåäèòüñÿ, ÷òî â ýòîì ãðàôåêîíå÷íîå ÷èñëî âåðøèí.

Îäíàêî íåïðîñòî óáåäèòüñÿ â òîì, ÷òîãðàô G (π) èìååò áåñêîíå÷íî ìíîãî âåðøèí.Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðètp1 t2IRt1p3IRp2t3p 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðètp1 t2IRt1p3IR- tp2t3p 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðètp1 t2IRt1p3IR- t tp2t3p 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðètp1 t2IRt1p3ItR- ttp2t3p 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðètp1 t2IRt1p3ItR- tt tp2t3p 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè-p1 t2IRt1- tp3ItR- tt tp2t3p 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè-p1 t2IRt1- tp3IR- t ttp2t3- tp 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè-p1 t2IRt1- tp3IR- t tp2t3- t tp 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè-p1 t2IRt1- tp3IR- tp2t3t- ttp 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè-p1 t2IRt1- tp3IRp2t3t- tt tp 4Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðèìåð íåîãðàíè÷åííîé ñåòè Ïåòðè-p1 t2IRt1- tp3IRp2t3t- tt tp 4Êàê âèäíî èç ïðîâåäåííîãî âû÷èñëåíèÿ, ïîçèöèè p2 è p4ÿâëÿþòñÿ íåîãðàíè÷åííûìè.Íî êàê ìîæíî ñòðîãî îáîñíîâàòü îáíàðóæåííûé ýôôåêò¾íåîãðàíè÷åííûõ¿ âû÷èñëåíèé?Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÊðèòåðèé íåîãðàíè÷åííîñòè ñåòè ÏåòðèÑåòü Ïåòðè π = (P, T , F , W , M0) ÿâëÿåòñÿ íåîãðàíè÷åííîéòîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò õîòÿ áû îäíî òàêîåâû÷èñëåíèåττ000M0 −→∗ M 0 −→∗ M 00 ,â êîòîðîì äëÿ ïàðû êîíôèãóðàöèé M 0, M 00 âûïîëíÿåòñÿñîîòíîøåíèå M 0 M 00 , ïðè÷åì õîòÿ áû äëÿ îäíîé ïîçèöèè pñïðàâåäëèâî ñòðîãîå íåðàâåíñòâî M 0(p) < M 00(p) .Äîêàçàòåëüñòâî.(⇐ ) Èç óñëîâèÿ M 0 M 00 ñëåäóåò, ÷òî M 00 = M 0 + K äëÿíåêîòîðîé ðàçìåòêè K .Èç óñëîâèÿ M 0(p) < M 00(p) ñëåäóåò, ÷òî ðàçìåòêà K íåïóñòîåìóëüòèìíîæåñòâî ïîçèöèé.Èç îñíîâíîé òåîðåìû î ìîíîòîííîñòè âû÷èñëåíèé ñåòåé Ïåòðèñëåäóåò, ÷òî M 0 + nK ∈ R(π) äëÿ ëþáîãî öåëîãî n, n ≥ 0 .Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÄîêàçàòåëüñòâî.(⇒ ) Åñëè ñåòü Ïåòðè π íåîãðàíè÷åíà, òî åå ãðàô äîñòèæèìûõðàçìåòîê G (π) èìååò áåñêîíå÷íî ìíîãî âåðøèí, äîñòèæèìûõèç íà÷àëüíîé ðàçìåòêè M .Òîãäà, ïî, â òàêîì ãðàôå ñóùåñòâóåòáåñêîíå÷íàÿ öåïü (ìàðøðóò áåç ïîâòîðÿþùèõñÿ âåðøèí)ëåììå Êåíèãàttt123α = M0 −→M1 −→M2 −→···Ëåììà î áåñêîíå÷íûõ ìíîæåñòâàõ ðàçìåòîê.Èç ëþáîé áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè ðàçìåòîêM0 , M1 , M2 , M3 , .

. . ìîæíî âûäåëèòü áåñêîíå÷íóþ ìîíîòîííîâîçðàñòàþùóþ ïîäïîñëåäîâàòåëüíîñòü ðàçìåòîêMr Mr Mr . . . .123Äîêàçàòåëüñòâî îñíîâíîé ëåììûÊàæäàÿ ðàçìåòêà ìîæåò áûòü ïðåäñòàâëåíà íàáîðîìíàòóðàëüíûõ ÷èñåë Mi = hn1i , n2i , . . . , nmi i .Çàìåòèì, ÷òî íèêàêàÿ ïîñëåäîâàòåëüíîñòü íàòóðàëüíûõ ÷èñåëíå ìîæåò áûòü áåñêîíå÷íî óáûâàþùåé.Ïîýòîìó â áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè ðàçìåòîê α ìîæíîâûäåëèòü áåñêîíå÷íóþ ïîäïîñëåäîâàòåëüíîñòü ðàçìåòîêα(1) = Mi1 , Mi2 , .

. . , Mik , . . . ,â êîòîðîé ïåðâûå êîìïîíåíòû íàáîðîâ, çàäàþùèõ ýòèðàçìåòêè, îáðàçóþò íåóáûâàþùóþ ïîñëåäîâàòåëüíîñòün1i ≤ n1i ≤ n1i ≤ . . . .Òî÷íî òàê æå â áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè ðàçìåòîê α(1)ìîæíî âûäåëèòü áåñêîíå÷íóþ ïîäïîñëåäîâàòåëüíîñòü ðàçìåòîê123α(2) = Mj1 , Mj2 , . . . , Mj` , .

. . ,â êîòîðîé âòîðûå êîìïîíåíòû íàáîðîâ, çàäàþùèõ ýòèðàçìåòêè, îáðàçóþò íåóáûâàþùóþ ïîñëåäîâàòåëüíîñòün2j ≤ n2j ≤ n2j ≤ . . . .123Ïðîáëåìà îãðàíè÷åííîñòè äëÿ ñåòåé ÏåòðèÏðîâåäÿ òàêîå âûäåëåíèå ïîäïîñëåäîâàòåëüíîñòåé m ðàç (ïî÷èñëó ïîçèöèé â ñåòè π ), ïîëó÷èì áåñêîíå÷íóþ íåóáûâàþùóþïîñëåäîâàòåëüíîñòü ïîïàðíî ðàçëè÷íûõ ðàçìåòîêα(m) = Mr1 Mr2 Mr3 . .

. .Ëåììà î áåñêîíå÷íûõ ìíîæåñòâàõ ðàçìåòîê äîêàçàíà.Ïîñêîëüêó ðàçìåòêè ýòîé ïîñëåäîâàòåëüíîñòè ðàñïîëàãàþòñÿäðóã çà äðóãîì íà îäíîì è òîì æå ìàðøðóòå â ãðàôåäîñòèæèìûõ ðàçìåòîê G (π) , ïðèõîäèì ê çàêëþ÷åíèþ î òîì,÷òî ïàðà ðàçëè÷íûõ ðàçìåòîê Mr , Mr óäîâëåòâîðÿåòñîîòíîøåíèþττ10200M0 −→∗ Mr1 −→∗ Mr2äëÿ íåêîòîðûõ êîíå÷íûõ ïîñëåäîâàòåëüíîñòåé ïåðåõîäîâ τ 0, τ 00è ïðè ýòîì ñïðàâåäëèâî íåðàâåíñòâî Mr Mr .12Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÊðèòåðèé íåîãðàíè÷åííîñòè ñåòè Ïåòðè ïîçâîëÿåò ïîñòðîèòüàëãîðèòì ðåøåíèÿ ïðîáëåìû îãðàíè÷åííîñòè ñåòè.Ýòîò àëãîðèòì îñóùåñòâëÿåò ïðîâåðêó îãðàíè÷åííîñòè ñåòèÏåòðè ïóòåì ïîñòðîåíèÿ ò.í..Âåðøèíàìè ýòîãî äåðåâà ñëóæàò íàáîðû, ñîñòîÿùèå èçíàòóðàëüíûõ ÷èñåë, à òàêæå ñïåöèàëüíîãî ñèìâîëà ∞ .Íàáîðû, â êîòîðûõ ñîäåðæèòñÿ ñèìâîë ∞ , áóäåì íàçûâàòüïðåäåëüíûìè .Ïðåäåëüíûå íàáîðû ìîæíî ðàññìàòðèâàòü êàê ðàçìåòêèîñîáîãî ðîäà: ðàâåíñòâî M(p) = ∞ äëÿ íåêîòîðîé ïîçèöèè pîçíà÷àåò, ÷òî â ýòîé ïîçèöèè ìîæåò áûòü íàêîïëåíî áåñêîíå÷íîìíîãî ôèøåê.Ïðåäåëüíûå íàáîðû ìîæíî ñðàâíèâàòü äðóã ñ äðóãîì è ñíàáîðàìè íàòóðàëüíûõ ÷èñåë (ðàçìåòêàìè) ïîêîìïîíåíòíî,ïîëàãàÿ, ÷òî n < ∞ äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà n .äåðåâà ïîêðûòèÿ ðàçìåòîêÄåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðè ïîñòðîåíèè äåðåâà ïîêðûòèÿ ðàçìåòîê ïðåäåëüíûå íàáîðûáóäóò âîçíèêàòü âñÿêèé ðàç, êîãäà îáíàðóæèâàþòñÿ ïàðûñðàâíèìûõ ðàçìåòîê.Ïóñòü çàäàíû äâå ðàçìåòêè M 0, M 00 ñåòè Ïåòðè π è ïðè ýòîìM 0 ≺ M 00 .

Òîãäà çàïèñü [M 0 , M 00 ] áóäåò îáîçíà÷àòü ïðåäåëüíûéíàáîð, êîòîðûé óäîâëåòâîðÿåò ñëåäóþùèì ðàâåíñòâàì äëÿëþáîé ïîçèöèè p :(M 00 (p), åñëè M 0 (p) = M 00 (p),[M 0 , M 00 ](p) =∞, åñëè M 0 (p) < M 00 (p).Äåðåâî ïîêðûòèÿ ðàçìåòîê Γ(π) ñåòè Ïåòðèπ = (P, T , F , W , M0 ) óñòðîåíî ñëåäóþùèì îáðàçîì.1)  êà÷åñòâå âíóòðåííèõ (íåëèñòîâûõ) âåðøèí èñïîëüçóþòñÿòîëüêî íàáîðû íàòóðàëüíûõ ÷èñåë, ñîîòâåòñòâóþùèåðàçìåòêàì ñåòè π .2) Ïðåäåëüíûå íàáîðû ñëóæàò òîëüêî ëèñòîâûìè âåðøèíàìè.Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé Ïåòðè3) êîðíåì äåðåâà ÿâëÿåòñÿ íà÷àëüíàÿ ðàçìåòêà M0 ;4) ðàçìåòêà M ñåòè π , âõîäÿùàÿ â ñîñòàâ äåðåâà Γ(π) ,ñëóæèò ëèñòîâîé âåðøèíîé òîãäà è òîëüêî òîãäà, êîãäàI ëèáîI ëèáîM0MMÿâëÿåòñÿ òóïèêîâîé ðàçìåòêîé ñåòèâñòðå÷àëàñü ðàíåå â äåðåâåâ âåðøèíóMΓ(π)π,íà ïóòè èç êîðíÿ;t5) åñëè âåðøèíà M íå ÿâëÿåòñÿ ëèñòîâîé, è M −→M 00 äëÿíåêîòîðîãî ïåðåõîäà t , òî â äåðåâå Γ(π) èìååòñÿ äóãà,âåäóùàÿ èç âåðøèíû M â òàêóþ âåðøèíó Mb , ÷òîIIb = M 00 , åñëè íà ïóòè èç èç êîðíÿ M0 â âåðøèíó M íåòM0000âåðøèí M , óäîâëåòâîðÿþùèõ îòíîøåíèþ M ≺ M;000bM = [M , M ] , åñëè íà ïóòè èç èç êîðíÿ M0 â âåðøèíó M0âñòðå÷àåòñÿ òàêàÿ âåðøèíà M , äëÿ êîòîðîé ñïðàâåäëèâî000ñðàâíåíèå M ≺ M.Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðèìåð äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) äëÿ ñåòè Ïåòðè π .tp1 t2IRt1p3IRp2t3Íà÷àëüíàÿ ðàçìåòêà M0 = (1, 0, 0, 0)M0 = (1, 0, 0, 0)p 4Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðèìåð äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) äëÿ ñåòè Ïåòðè π .-p1 t2IRt1Rp2;M1 òóïèêîâàÿ ðàçìåòêàt- tp3I2M0 −→M1 = (0, 0, 1, 0)t3M0 = (1, 0, 0, 0)p 4Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðèìåð äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) äëÿ ñåòè Ïåòðè π .-p1 t2IRt1Rp2;M1 òóïèêîâàÿ ðàçìåòêàtM0 = (1, 0, 0, 0)- tp3IM1 = (0, 0, 1, 0)2M0 −→M1 = (0, 0, 1, 0)t3p 4Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðèìåð äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) äëÿ ñåòè Ïåòðè π .tp1 t2IRt1M0 = (1, 0, 0, 0)p3IM1 = (0, 0, 1, 0)Rp2t3Íà÷àëüíàÿ ðàçìåòêà M0 = (1, 0, 0, 0)p 4Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðèìåð äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) äëÿ ñåòè Ïåòðè π .tp1 t2IRt1M0 = (1, 0, 0, 0)p3IM1 = (0, 0, 1, 0)R- tp2t1M0 −→M2 = (1, 1, 0, 0)M0 ≺ M2[M0 , M2 ] = (1, ∞, 0, 0)t3p 4Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÏðèìåð äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) äëÿ ñåòè Ïåòðè π .tp1 t2IRt1M0 = (1, 0, 0, 0)@p3@IM1 = (0, 0, 1, 0) @R@[M , M ] = (1, ∞, 0, 0) 0 2R- tpp 2t1M0 −→M2 = (1, 1, 0, 0)M0 ≺ M2[M0 , M2 ] = (1, ∞, 0, 0)t34Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÒåîðåìà î äåðåâå ïîêðûòèÿ ðàçìåòîê1.

Äëÿ ëþáîé ñåòè ÏåòðèðàçìåòîêΓ(π)2. Ñåòü Ïåòðèπäåðåâî ïîêðûòèÿÿâëÿåòñÿ êîíå÷íûì.πÿâëÿåòñÿ îãðàíè÷åííîé òîãäà èòîëüêî òîãäà, êîãäà â äåðåâå ïîêðûòèÿ ðàçìåòîêΓ(π)îòñóòñòâóþò ïðåäåëüíûå âåðøèíû.Äîêàçàòåëüñòâî.Ñëåäóåò èç êðèòåðèÿ íåîãðàíè÷åííîñòè ñåòåéÏåòðè è îïðåäåëåíèÿ äåðåâà ïîêðûòèÿ ðàçìåòîê.Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÑëåäñòâèÿ èç òåîðåìû î äåðåâå ïîêðûòèÿðàçìåòîê1.

Ïðîáëåìà îãðàíè÷åííîñòè îáûêíîâåííûõ ñåòåéÏåòðè àëãîðèòìè÷åñêè ðàçðåøèìà.2. Ïðîáëåìà áåçîïàñíîñòè îðäèíàðíûõ ñåòåéÏåòðè àëãîðèòìè÷åñêè ðàçðåøèìà.Çàäà÷à 1 [òðóäíàÿ]À êàêîâà ñëîæíîñòü ïðåäëîæåííîãî àëãîðèòìàïðîâåðêè îãðàíè÷åííîñòè ñåòåé Ïåòðè ïóòåìïîñòðîåíèÿ äåðåâüåâ ïîêðûòèÿ ðàçìåòîê?Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÈíîãäà âàæíî íå òîëüêî óñòàíîâèòü, ÷òî ñåòü Ïåòðè ÿâëÿåòñÿíåîãðàíè÷åííîé, íî òàêæå è îïðåäåëèòü, â êàêèõ ïîçèöèÿõìîæåò íàêàïëèâàòüñÿ áåñêîíå÷íî ìíîãî ôèøåê.Äëÿ ýòîãî äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π) óæå íåäîñòàòî÷íî,ïîñêîëüêó àíàëèç âû÷èñëåíèé íà åãî âåòâÿõ îáðûâàåòñÿ ïðèîáíàðóæåíèè ïåðâîãî æå ïîêðûòèÿ ðàçìåòîê M 0 ≺ M 00 .tp1 t2IRt1M0 = (1, 0, 0, 0)@p3@IM1 = (0, 1, 0, 0) @R@[M , M ] = (1, ∞, 0, 0) 0 2Rpp 2t34 ýòîé ñåòè íåîãðàíè÷åíû ïîçèöèè p2 è p4 , íî ãðàô Γ(π)îáíàðóæèâàåò òîëüêî íåîãðàíè÷åííîñòü p2 .Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÍî ïîñòðîåíèå äåðåâà ïîêðûòèÿ ìîæíî ïðîäîæèòü, åñëèîáðàùàòüñÿ ñ ïðåäåëüíûìè íàáîðàìè òàê æå, êàê ñ îáû÷íûìèðàçìåòêàìè.Óñëîâèìñÿ, ÷òî äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà m âåðíûðàâåíñòâà ∞ + m = ∞ − m = ∞ .Òîãäà äëÿ âñÿêîãî ïðåäåëüíîãî íàáîðà M è ïåðåõîäà t âïðîèçâîëüíîé ñåòè Ïåòðè π ìîæíî îïðåäåëèòüI óñëîâèå ñðàáàòûâàíèÿ ïåðåõîäà: FW (•, t) M ,I ðåçóëüòàò ñðàáàòûâàíèÿ ïåðåõîäà:M 0 = (M FW (•, t)) + FW (t, •) .Òàêèì îáðàçîì, ïîñòðîåíèå äåðåâà ïîêðûòèÿ ðàçìåòîê Γ(π)ìîæåò áûòü ïðîäîæåíî èç ïðåäåëüíûõ âåðøèí.Ïîëó÷åííîå â ðåçóëüòàòå òàêîãî ïîñòðîåíèÿ äåðåâî íàçûâàåòñÿïîëíûì äåðåâîì ïîêðûòèÿ ðàçìåòîê ñåòè Ïåòðè π .Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèM0 = (1, 0, 0, 0)t2 HHt1jHp3IM1 = (0, 1, 0, 0) M20 = (1, ∞, 0, 0)t1 M30 = (1, ∞, 0, 0) t2R?p4p2tp1 t2IRt1t3M40 = (0, ∞, 1, 0)t3?Ïîëíîå äåðåâî ïîêðûòèÿðàçìåòîê ñåòè ÏåòðèM50 = (0, ∞, 1, ∞)t3?M60 = (0, ∞, 1, ∞)Äåðåâüÿ ïîêðûòèÿ ðàçìåòîê ñåòåé ÏåòðèÒåîðåìà î ïîëíîì äåðåâå ïîêðûòèÿðàçìåòîê1.