Геометрия и комбинаторика виртуальных узлов (1097523), страница 23
Текст из файла (страница 23)
Ïðè ýòîì â ñëó÷àå ïåðâîãî äâèæåíèÿ åéäåìåéñòåðà ïåðåêðåñòîê ìîæåò èìåòü ïðîèçâîëüíûé òèï,äëÿ âòîðîãî äâèæåíèÿ åéäåìåéñòåðà ìû òðåáóåì, ÷òîáû ëèáî îáà ïåðåêðåñòêà áûëè êëàññè÷åñêèìè, ëèáî îáà âèðòóàëüíûìè; â ñëó÷àå òðåòüåãîäâèæåíèÿ åéäåìåéñòåðà ìû ðàçðåøàåì äóãå, ñîäåðæàùåé êëàññè÷åñêèåïåðåêðåñòêè, ïðîõîäèòü ñêâîçü êëàññè÷åñêèé ïåðåêðåñòîê, à òàêæå äóãå,ñîäåðæàùåé âèðòóàëüíûå ïåðåêðåñòêè, ïðîõîäèòü êàê ÷åðåç êëàññè÷åñêèå,òàê è ÷åðåç âèðòóàëüíûå ïåðåêðåñòêè, ñì.
ðèñ. 1.18.Èíûìè ñëîâàìè, ïðàâèëî äëÿ äâèæåíèé åéäåìåéñòåðà äëÿ ïëîñêèõ âèðòóàëüíûõ óçëîâ ìîæíî ñîðìóëèðîâàòü ñëåäóþùèì îáðàçîì. Íà ïåðâîå3.4. Èåðàðõèÿ âèðòóàëüíûõ óçëîâ135äâèæåíèå åéäåìåéñòåðà íå íàêëàäûâàåòñÿ íèêàêèõ îãðàíè÷åíèé. Äëÿ âòîðîãî äâèæåíèÿ åéäåìåéñòåðà ìû òðåáóåì, ÷òîáû îáà ïåðåêðåñòêà áûëèîäíîãî òèïà, à äëÿ òðåòüåãî äâèæåíèÿ åéäåìåéñòåðà ìû ðàçðåøàåì âåòâè, ñîäåðæàùåé äâà ïåðåêðåñòêà òèïà i, ïðîõîäèòü ñêâîçü ïåðåêðåñòîê òèïàj åñëè è òîëüêî åñëè i > j , ãäå > ÿâëÿåòñÿ áèíàðíûì îòíîøåíèåì (â íàøåì ñëó÷àå îáû÷íîå îòíîøåíèå > íà ìíîæåñòâå {1, 2}).
Çäåñü ìû èìååìäâà òèïà ïåðåêðåñòêîâ: 1 ñîîòâåòñòâóåò êëàññè÷åñêèì ïåðåêðåñòêàì, à 2 âèðòóàëüíûì.Âìåñòî äâóõ òèïîâ ïåðåêðåñòêîâ ìû ìîæåì ðàçðåøèòü ðàññòàâëÿòü ïåðåêðåñòêè èç ïðîèçâîëüíîãî ÷àñòè÷íî óïîðÿäî÷åííîãî ìíîæåñòâà M .  ýòîìñëó÷àå âåòâü ñ êëàññè÷åñêèìè ïåðåêðåñòêàìè, èìåþùèìè ìåòêè i, ìîæåòïðîõîäèòü ñêâîçü ïåðåêðåñòîê ñ ìåòêîé j åñëè è òîëüêî åñëè i > j .Èòàê, òåîðèÿ ïëîñêèõ âèðòóàëüíûõ çàöåïëåíèé èìååò ñëåäóþùóþ ïåðåîðìóëèðîâêó:1.
Îñíîâíûå îáúåêòû ïëîñêîé èåðàðõèè ýòî ÷åòûðåõâàëåíòûå ãðàû íàïëîñêîñòè, ñíàáæåííûå ñïåöèàëüíîé ñòðóêòóðîé â ïåðåêðåñòêàõ: êëàññè÷åñêèå ïåðåêðåñòêè èìåþò ìåòêó 1, à âèðòóàëüíûå ïåðåêðåñòêè èìåþò ìåòêó 2.2. Äâà îáúåêòà íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè îäèí èç íèõ ìîæíî ïåðåñòðîèòü âî âòîðîé ïîñëåäîâàòåëüíîñòüþ ñëåäóþùèõ âàðèàíòîâ äâèæåíèé åéäåìåéñòåðà, óêàçàííûõ íà ðèñ. 3.28.rs1 движениеkkls2 движениеk>llkkèñ. 3.28. Äâèæåíèÿ åéäåìåéñòåðà äëÿ èåðàðõè÷åñêèõ óçëîâ3.4. Èåðàðõèÿ âèðòóàëüíûõ óçëîâ136 ñëó÷àå ïåðâîãî äâèæåíèÿ åéäåìåéñòåðà âîçìîæíà ëþáàÿ ìåòêàäëÿ ïåðåêðåñòêà. ñëó÷àå âòîðîãî äâèæåíèÿ åéäåìåéñòåðà ìû òðåáóåì, ÷òîáû îáàïåðåêðåñòêà èìåëè îäèíàêîâûå ìåòêè. ñëó÷àå òðåòüåãî äâèæåíèÿ åéäåìåéñòåðà ìû òðåáóåì, ÷òîáû ïðèïðîõîæäåíèè âåòâè óçëà γ ÷åðåç âåðøèíó ñ ìåòêîé x, ìåòêè äâóõ âåðøèí, ëåæàùèõ íà γ îáà áûëè ðàâíû y , ïðè ýòîì y > x.Ïîñëåäíåå óñëîâèå íà òðåòüå äâèæåíèå åéäåìåéñòåðà îçíà÷àåò, ÷òî âåòâè, ñîäåðæàùåå ëèøü âèðòóàëüíûå ïåðåêðåñòêè, ìîãóò ïðîõîäèòü ñêâîçüêëàññè÷åñêèå ïåðåêðåñòêè, ïðè ýòîì âåòâè, ñîñòîÿùèå èç êëàññè÷åñêèõ ïåðåêðåñòêîâ, íå ìîãóò ïðîõîäèòü ñêâîçü âèðòóàëüíûå ïåðåêðåñòêè.Êàê áûëî ñêàçàíî âî ââåäåíèè, ïëîñêèå âèðòóàëüíûå óçëû ëåãêî êëàññèèöèðóþòñÿ ãåîìåòðè÷åñêè (îíè ïðèâîäÿòñÿ ê ìèíèìàëüíîìó ïðåäñòàâèòåëþ ïîñðåäñòâîì äåñòàáèëèçàöèé è óìåíüøàþùèõ äâèæåíèé åéäåìåéñòåðà; ìèíèìàëüíûé ïðåäñòàâèòåëü îïðåäåëåí ñ òî÷íîñòüþ äî òðåòüåãî äâèæåíèÿ åéäåìåéñòåðà).Îáîáùèì òåïåðü ïîíÿòèå ïëîñêèõ âèðòóàëüíûõ óçëîâ (âèðòóàëüíûõ ñòðóí)ñëåäóþùèì îáðàçîì.
Ïóñòü M ìíîæåñòâî, íà êîòîðîì çàäàíî áèíàðíîåîòíîøåíèå α 6 β (íå îáÿçàòåëüíî àöèêëè÷åñêîå, ò.å. èç ñîîòíîøåíèé α 6 βè β 6 α, âîîáùå ãîâîðÿ, íå ñëåäóåò, ÷òî α = β ). Ïðè ýòîì çàïèñü β > αýêâèâàëåíòíà çàïèñè α 6 β .Áóäåì ðàññìàòðèâàòü ÷åðòûðåõâàëåíòíûå ãðàû íà ïëîñêîñòè è ñîïîñòàâëÿòü ïåðåêðåñòêàì ìåòêè èç ìíîæåñòâà M . Ïðè ýòîì ñêàæåì, ÷òî äâàìå÷åíûõ ÷åòûðåõâàëåíòíûõ ãðàà ýêâèâàëåíòíû åñëè è òîëüêî åñëè îäèíèç íèõ ïîëó÷àåòñÿ èç äðóãîãî ïîñëåäîâàòåëüíûì ïðèìåíåíèåì äâèæåíèéåéäåìåéñòåðà ñ îãðàíè÷åíèÿìè, îïèñàííûìè âûøå.Áóäåì ñòðîèòü èíâàðèàíò òàêèõ îáúåêòîâ êîìáèíàòîðíûì îáðàçîì, àíàëîãè÷íî âèðòóàëüíûì ãðóïïîèäàì.3.4.2.
Àëãåáðàè÷åñêèé îðìàëèçìÔèêñèðóåì ÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî M ñ áèíàðíûì îòíîøåíèåì 6.3.4. Èåðàðõèÿ âèðòóàëüíûõ óçëîâ137Ïóñòü äàí îðèåíòèðîâàííûé ïëîñêèé ÷åòûðåõâàëåíòíûé ãðà D, âñåâåðøèíû êîòîðîãî ïîìå÷åíû ýëåìåíòàìè èç M .  äàëüíåéøåì ìû áóäåì òàêèå ãðàû íàçûâàòü M -èåðàðõè÷åñêèìè äèàãðàììàìè. Äóãîé M -èåðàðõè÷åñêîéäèàãðàììû ìû íàçûâàåì ñâÿçíóþ êîìïîíåíòó ìíîæåñòâà, ïîëó÷åííîãî óäàëåíèåì èç D âñåõ âåðøèí.
Òîãäà D çàäàåò èåðàðõè÷åñêóþ äèàãðàììó.Êàæäàÿ èåðàðõè÷åñêàÿ äèàãðàììà çàäàåò èåðàðõè÷åñêîå çàöåïëåíèå èçíåêîòîðîãî êîëè÷åñòâà êîìïîíåíò. Êîìïîíåíòû èåðàðõè÷åñêîãî çàöåïëåíèÿ ýòî óíèêóðñàëüíûå êðèâûå ñîîòâåòñòâóþùåãî ïëîñêîãî ãðàà.Ïóñòü ìû èìååì èåðàðõè÷åñêóþ äèàãðàììó F çàöåïëåíèÿ èç n êîìïîíåíò. Ïåðåíóìåðóåì êîìïîíåíòû èåðàðõè÷åñêîãî çàöåïëåíèÿ ÷èñëàìè îò 1äî n.Êàæäàÿ âåðøèíà (ïåðåêðåñòîê) ýòîé äèàãðàììû èìååò ìåòêó j , à òàêæåäâà äîïîëíèòåëüíûõ ÷èñëà íîìåðà êîìïîíåíò çàöåïëåíèÿ: x, ñîîòâåòñòâóþùèé âåòâè þãî-çàïàä ñåâåðî-âîñòîê è y , ñîîòâåòñòâóþùèé âåòâèþãî-âîñòîê ñåâåðî-çàïàä, ñì.
ðèñ. 3.29.jyxèñ. 3.29. ÏåðåêðåñòîêÏåðåíóìåðóåì äóãè íàòóðàëüíûìè ÷èñëàìè (ïðîèçâîëüíûì îáðàçîì).Ñîïîñòàâèì òåïåðü äóãå ñ íîìåðîì i ýëåìåíò ai . Ýòè ýëåìåíòû áóäóò îáðàçóþùèìè òîãî ìîäóëÿ N èíâàðèàíòà èåðàðõè÷åñêîãî çàöåïëåíèÿ, êîòîðûé ìû ñòðîèì.Ïîñëå ïåðåíóìåðàöèè âñåõ äóã òàêèì îáðàçîì, çàäàäèì ñîîòíîøåíèÿ âïåðåêðåñòêàõ. Îíè çàäàþòñÿ ñëåäóþùèì îáðàçîì.Ïóñòü äàí ïåðåêðåñòîê ñ ìåòêîé j , êîòîðûé îòíîñèòñÿ ê äóãàì #x è#y (ïîðÿäîê äóã íå èìååò çíà÷åíèÿ). Ïóñòü ýëåìåíòû, ñîîòâåòñòâóþùèåâõîäÿùèì äóãàì, ðàâíû a è b (ñîîòâåòñòâåííî, ëåâûé íèæíèé è ïðàâûé3.4.
Èåðàðõèÿ âèðòóàëüíûõ óçëîâ138íèæíèé, åñëè äóãè îðèåíòèðîâàíû ñíèçó ââåðõ). Òîãäà ñîîòíîøåíèÿ áóäóòâûãëÿäåòü ñëåäóþùèì îáðàçîì:èjc = b − Pxya(3.21)jb,d = a + Pxy(3.22)ãäå c è d èñõîäÿùèå äóãè ëåâàÿ è ïðàâàÿ, ñì. ðèñ. 3.30.c=b-Pxyjad=a+Pxyj bjbaèñ. 3.30. Ñîîòíîøåíèå äëÿ èåðàðõè÷åñêîãî óçëàjÌû åùå íå îïðåäåëèëè Pxy. Êàêèì äîëæíû áûòü ýòè ýëåìåíòû, ÷òîáûàëãåáðàè÷åñêèé îðìàëèçì (ïîäîáíûé òîìó, êîòîðûé áûë ðàçâèò äëÿ ãðóïïîèäîâ, âèðòóàëüíûõ ãðóïïîèäîâ, áèãðóïïîèäîâ) ïðèâîäèë ê èíâàðèàíòóèåðàðõè÷åñêèõ çàöåïëåíèé?àññìîòðèì îðìàëüíóþ íåêîììóòàòèâíóþ àññîöèàòèâíóþ àëãåáðó (íàäïðîèçâîëüíûì êîëüöîì êîýèöèåíòîâ, íàïðèìåð, íàä Q), ïîðîæäåííóþiîðìàëüíûìè ýëåìåíòàìè Pxy, ãäå x, y ïðîáåãàþò ìíîæåñòâî C êîìïîíåíòçàöåïëåíèÿ, à i ïðîáåãàåò ÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî M , â êîòîðîìèìåþò ìåñòî ñëåäóþùèå ñîîòíîøåíèÿ:Äëÿ ëþáûõ i, x, y :ii.= PyxPxyÄëÿ ëþáûõ i, j ∈ M : i 6 j è äëÿ ëþáûõ x, y, z, t:(3.23)3.4.
Èåðàðõèÿ âèðòóàëüíûõ óçëîâiPztj = 0.Pxy139(3.24)Îáîçíà÷èì àëãåáðó (íàä ïîëåì Q), îïðåäåëåííóþ ñîîòíîøåíèÿìè (3.24),(3.23), ÷åðåç A(C).Êàê áóäåò âèäíî â äàëüíåéøåì, ýòè ñîîòíîøåíèÿ íåîáõîäèìû äëÿ èíâàðèàíòíîñòè îáúåêòà, êîòîðûé ìû ñòðîèì, îòíîñèòåëüíî äâèæåíèé åéäåìåéñòåðà.Ñîïîñòàâèì òåïåðü M -èåðàðõè÷åñêîé äèàãðàììå D, êîìïîíåíòû êîòîðîéçàíóìåðîâàíû ýëåìåíòàìè èç ìíîæåñòâà C , ïðàâûé ìîäóëü íàä àëãåáðîéA(C) ñëåäóþùèì îáðàçîì.Âûáåðåì âñå äóãè a1 , . . . , ak ýòîé äèàãðàììû â êà÷åñòâå îáðàçóþùèõ íàäêîëüöîì A(C). Ïðîàêòîðèçóåì ñâîáîäíûé ìîäóëü, ïîðîæäåííûé äóãàìèa1 , .
. . , ak , ïî ñîîòíîøåíèÿì (3.21) è (3.22) â ïåðåêðåñòêàõ, à òàêæå ïî ñîîòíîøåíèÿì âèäà (3.25), ñîñòîÿùèì â ñëåäóþùåì.Äëÿ ëþáûõ i, j, i > j , äëÿ ëþáûõ x, y, z, t ∈ C è äëÿ ëþáûõ l, m = 1, . . . , kïðè èêñèðîâàííûõ i, j âñå ýëåìåíòû ìîäóëÿ âèäàiPxyPztj al(3.25)ðàâíû ìåæäó ñîáîé. Äëÿ êðàòêîñòè ìû áóäåì îáîçíà÷àòü âñå ýòè ýëåìåíòû÷åðåç P i P j ∗.Èíûìè ñëîâàìè, ìû òðåáóåì, ÷òîáû ïîïàðíûå ïðîèçâåäåíèÿ ðàâíÿëèñüíóëþ â íåêîòîðûõ ÷àñòíûõ ñëó÷àÿõ (3.24), à èìåííî, ïðè i 6 j , ýòî âõîäèòâ îïðåäåëåíèå êîëüöà A(C). Ïðè ýòîì â ñëó÷àå, åñëè òàêîå ïðîèçâåäåíèåíå ðàâíî íóëþ, ìû òðåáóåì, ÷òîáû îíî áûëî íåêîòîðûì ýëåìåíòîì íàøåãîìîäóëÿ, çàâèñÿùèì òîëüêî îò èíäåêñîâ i è j .Îáîçíà÷èì ïîëó÷åííûé ìîäóëü ÷åðåç N (D).Çàìå÷àíèå 3.9.
 ñëó÷àå, êîãäà èìååòñÿ âñåãî îäíà êîìïîíåíòà, ìû ìîæåì çàáûòü ïðî íèæíèå èíäåêñû è ñòðîèòü àíàëîãè÷íîå êîëüöîC)è ìîäóëü, ñîîòâåòñòâóþùèé çàöåïëåíèþ.Òåîðåìà 3.18.öåïëåíèé.ÌîäóëüN (D)A (áåçÿâëÿåòñÿ èíâàðèàíòîì èåðàðõè÷åñêèõ çà-3.4. Èåðàðõèÿ âèðòóàëüíûõ óçëîâ140Äëÿ êàæäîãî äâèæåíèÿ åéäåìåéñòåðà èìååòñÿ ÷àñòü äèàãðàììû, ïðåòåðïåâàþùàÿ èçìåíåíèÿ; ó ýòîé ÷àñòè äèàãðàììû åñòü âõîäÿùèå è èñõîäÿùèå ðåáðà.
Íàì íóæíî ïîêàçàòü, ÷òî âûðàæåíèå ýëåìåíòîâ, ñîîòâåòñòâóþùèõ èñõîäÿùèì ðåáðàì, ÷åðåç ýëåìåíòû, ñîîòâåòñòâóþùèå âõîäÿùèì ðåáðàì, íå ìåíÿåòñÿ ïðè ïðèìåíåíèè äâèæåíèé åéäåìåéñòåðà; ïðè ýòîì ìåòêè, ñîîòâåòñòâóþùèå ïðîìåæóòî÷íûì ðåáðàì, ìîæíîèñêëþ÷èòü èç ÷èñëà îáðàçóþùèõ, òàê êàê îíè âûðàæàþòñÿ ÷åðåç âõîäÿùèåðåáðà (ðàññóæäåíèå ïîëíîñòüþ àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 3.3).Ìû ðàññìîòðèì ïî îäíîìó ñëó÷àþ äëÿ êàæäîãî èç òðåõ äâèæåíèé åéäåìåéñòåðà. Âñå îñòàëüíûå ñëó÷àè ïðîâåðÿþòñÿ àíàëîãè÷íî. ñëó÷àå ïåðâîãî äâèæåíèÿ åéäåìåéñòåðà ìû èìååì äåëî ðîâíî ñ îäíîéêîìïîíåíòîé çàöåïëåíèÿ è îäíèì ïåðåêðåñòêîì; òàêèì îáðàçîì, ïðè ïðîiâåðêå èíâàðèàíòíîñòè áóäåò èãóðèðîâàòü òîëüêî îäíà îáðàçóþùàÿ Pppêîëüöà, êîòîðóþ ìû äëÿ êðàòêîñòè áóäåì îáîçíà÷àòü ÷åðåç P , ñì. ðèñ.3.31.Äîêàçàòåëüñòâî.bxaèñ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
