Геометрия и комбинаторика виртуальных узлов (1097523), страница 61
Текст из файла (страница 61)
 äàëüíåéøåì ìû áóäåì ãîâîðèòü: äóãà õîðäîâîé äèàãðàììû ïðèíàäëåæèò íåêîòîðîìó öèêëó, ïîäðàçóìåâàÿ, ÷òî ýòîìó öèêëó ïðèíàäëåæèòñîîòâåòñòâóþùåå äàííîé õîðäå ðåáðî 4-ãðàà ñ A-ñòðóêòóðîé.Äàëüíåéøåå äîêàçàòåëüñòâî ëåììû 8.3 òàêîâî. Äëÿ êàæäîãî n ìû ñòðîèì ÿâíî äâà öèêëà A, B , ñîñòîÿùèå èç äóã õîðäîâîé äèàãðàììû ∆2n+1 .
Åñëèõîðäîâàÿ äèàãðàììà D ñîäåðæèò ∆2n+1 êàê ïîääèàãðàììó, òî êàæäàÿ äóãàäèàãðàììû ∆2n+1 ïîäðàçáèâàåòñÿ íà äóãè äèàãðàììû D õîðäàìè.  ýòîìñëó÷àå íàøè öèêëû òàêæå ïîäðàçáèâàþòñÿ: ðåáðà, ñîîòâåòñòâóþùèå äóãàìäèàãðàììû ∆2n+1 , áóäóò ðàçáèòû íà ðåáðà, ñîîòâåòñòâóþùèå äóãàì äèàãðàììû D. Ïðè òàêîì ðàçáèåíèè ïîÿâÿòñÿ íîâûå âåðøèíû, ñîîòâåòñòâóþùèå êîíöàì õîðä, âõîäÿùèõ â D, íî íå â ∆2n+1 . Íî ýòè âåðøèíû íå âëèÿþòíà êîëè÷åñòâî òî÷åê ïåðåêðåñòüÿ èññëåäóåìûõ öèêëîâ, èáî ïî ïîñòðîåíèþðàññìàòðèâàåìûå öèêëû â ýòèõ âåðøèíàõ ïåðåõîäÿò ñ ðåáðà íà íå ïðîòèâîïîëîæíîå, ñëåäîâàòåëüíî, åñëè òàêàÿ âåðøèíà è áóäåò âñòðå÷àòüñÿ â îáîèõöèêëàõ, òî îíà íå áóäåò ó÷èòûâàòüñÿ.Ïðèìåð äâóõ öèêëîâ äëÿ 2n + 1-óãîëüíèêà ïîêàçàí íà ðèñ. 8.13; äóãè,ñîîòâåòñòâóþùèå ïåðâîìó öèêëó ïîìå÷åíû öèðîé 1, à äóãè, ñîîòâåòñòâó-8.6.
Äîêàçàòåëüñòâî ãèïîòåçû Âàñèëüåâà364þùèå âòîðîìó öèêëó, öèðîé 2. Õîðäà, ñîîòâåòñòâóþùàÿ åäèíñòâåííîéèõ òî÷êå ïåðåêðåñòüÿ, èçîáðàæåíà ïóíêòèðíîé ëèíèåé.Ñëåäóþùàÿ ëåììà äîêàçàíà â ðàáîòå [Kau7℄ â íåñêîëüêî èíîé îðìóëèðîâêå.Ëåììà 8.4. Ïóñòü 4-ãðà Γ ñ A-ñòðóêòóðîé îáëàäàåò ñâîéñòâîì èñòî÷íèêñòîê. Ïóñòü õîðäîâàÿ äèàãðàììàõîäó ãðààΓ,â ïëîñêîñòü ñD,ñîîòâåòñòâóþùàÿ íåêîòîðîìó îá-d-äèàãðàììîé. Òîãäàñîõðàíåíèåì A-ñòðóêòóðû.ÿâëÿåòñÿãðàΓäîïóñêàåò âëîæåíèåÍàãëÿäíîå îïèñàíèå äîêàçàòåëüñòâî ëåììû ïðèâåäåíî íà ðèñ.
8.14. Âñðåäíåé ÷àñòè ðèñóíêà ïîêàçàíî, êàê ïî õîðäå âîññòàíàâëèâàåòñÿ îêðåñòíîñòü âåðøèíû ãðàà.  íèæíåé ÷àñòè óêàçàíî, ÷òî â ñëó÷àå d-äèàãðàììûñîîòâåòñòâóþùèé ãðà óêëàäûâàåòñÿ íà ïëîñêîñòü, ïðè÷åì ñòðóêòóðà ïðîòèâîïîëîæíîñòè ðåáåð â âåðøèíàõ (A-ñòðóêòóðà) ñîõðàíÿåòñÿ.àññìîòðèì d-äèàãðàììó D è âëîæèì åå âïëîñêîñòü ñëåäóþùèì îáðàçîì. àçîáüåì õîðäû ýòîé äèàãðàììû íà äâàñåìåéñòâà õîðä F1 , F2 òàê, ÷òî ëþáûå äâå õîðäû èç îäíîãî ñåìåéñòâà íå áûëè çàöåïëåíû ìåæäó ñîáîé (ðàçáèåíèå âûáèðàåòñÿ ïðîèçâîëüíûì îáðàçîì).Äàëåå âëîæèì îêðóæíîñòü â ïëîñêîñòü ñòàíäàðòíûì îáðàçîì, ðàñïîëîæèâêîíöû õîðä íà îêðóæíîñòè òàê, ÷òîáû íèêàêèå äâà îáðàçà êîíöîâ õîðä íåáûëè äèàìåòðàëüíî ïðîòèâîïîëîæíûìè.
Õîðäû ïåðâîãî ñåìåéñòâà ðàñïîëîæèì âíóòðè îêðóæíîñòè, à õîðäû âòîðîãî ñåìåéñòâà âíå. Ýòî ìîæíîñäåëàòü áåç ïåðåñå÷åíèé, îòîáðàçèâ õîðäû ïåðâîãî ñåìåéñòâà â ïðÿìîëèíåéíûå îòðåçêè, à õîðäû âòîðîãî ñåìåéñòâà â îáðàçû ïðÿìîëèíåéíûõîòðåçêîâ îòíîñèòåëüíî èíâåðñèè â ðàññìàòðèâàåìîé îêðóæíîñòè.Îðèåíòèðóåì îêðóæíîñòü ïðîòèâ ÷àñîâîé ñòðåëêè. Êàæäàÿ õîðäà c ñîåäèíÿåò ïàðó òî÷åê íà îêðóæíîñòè: X è Y . àññìîòðèì íà îêðóæíîñòèòî÷êè X1 = X − ε, X2 = X + ε, Y1 = Y − ε, Y2 = Y + ε. Çäåñü ε íåêîòîðîå ìàëîå ÷èñëî (óãîë), à îïåðàöèè + è − ïîíèìàþòñÿ â ñìûñëå ìàëîãîñäâèãà òî÷êè íà óãîë ±ε.
Óäàëèì òåïåðü õîðäó c âìåñòå ñ äâóìÿ äóãàìè[X1 , X2 ] è [Y1 , Y2 ]. Âìåñòî íåå ðàçìåñòèì â îêðåñòíîñòè óäàëåííîé õîðäûäâà (êðèâîëèíåéíûõ) îòðåçêà [X1 , Y1 ] è [X2 , Y2 ] òàê, ÷òîáû îíè ïåðåñåêàëèñü òðàíñâåðñàëüíî ðîâíî â îäíîé òî÷êå Z (ñêàæåì, â ñåðåäèíå óäàëåííîéÄîêàçàòåëüñòâî ëåììû 8.4.8.6. Äîêàçàòåëüñòâî ãèïîòåçû Âàñèëüåâà365õîðäû). Ïðîäåëàâ ýòó îïåðàöèþ äëÿ âñåõ õîðä äèàãðàììû D, ìû ïîëó÷èì÷åòûðåõâàëåíòíûé ãðà ∆.Ïî ïîñòðîåíèþ ãðà ∆ èçîìîðåí ãðàó Γ.Íàì îñòàëîñü äîêàçàòü, ÷òî îíè èìåþò îäèíàêîâóþ A-ñòðóêòóðó.Èç òîãî, ÷òî ãðà Γ îáëàäàåò ñâîéñòâîì èñòî÷íèê-ñòîê ñëåäóåò, ÷òî ïîëó÷åííîå âëîæåíèå ÿâëÿåòñÿ ðåàëèçàöèåé, ò.å.
íà 4-ãðàå Γ A-ñòðóêòóðîéðåáðî, ñîîòâåòñòâóþùåå [X1 , Z], ïðîòèâîïîëîæíî ðåáðó, ñîîòâåòñòâóþùåìó[Z, Y1 ].Ýòî âûòåêàåò èç ñëåäóþùèõ ñîîáðàæåíèé. Òàê êàê 4-ãðà Γ A-ñòðóêòóðîéîáëàäàåò ñâîéñòâîì èñòî÷íèê-ñòîê, òî ëþáîé åãî îáõîä ìîæíî ñäåëàòü îðèåíòèðîâàííûì ñîãëàñíî ïðàâèëó èñòî÷íèê-ñòîê: êàæäîå ðåáðî, âõîäÿùååâ âåðøèíó, ïðîäîëæàåòñÿ ðåáðîì, èñõîäÿùèì èç íåå (è ïîâîðà÷èâàþùèì âîäíîì èç äâóõ íàïðàâëåíèé).Íàì îñòàëîñü çàìåòèòü, ÷òî ïðè ëþáîì ïîâîðà÷èâàþùåì îáõîäå ãðàà∆ ðåáðî [Z, X2 ] ñëåäóåò çà ðåáðîì [X1 , Z] â òîì è òîëüêî â òîì ñëó÷àå,åñëè ðåáðî [Z, Y2 ] ñëåäóåò çà ðåáðîì [Y1 , Z].
Ïîñëåäíåå âûòåêàåò èç òîãî,÷òî ëþáîé ïîâîðà÷èâàþùèé îáõîä ÷åòûðåõâàëåíòíîãî ãðàà íà ïëîñêîñòèàïïðîêñèìèðóåòñÿ âëîæåíèåì îêðóæíîñòè â ïëîñêîñòü.Ëåììà äîêàçàíà.Ñóììèðóÿ äîêàçàííîå â ëåììàõ 8.1,8.2,8.3,8.4, ìû ïîëó÷àåì óòâåðæäåíèåãèïîòåçû Âàñèëüåâà.Çàìåòèì, ÷òî â ëåììå 8.3 äîêàçûâàåòñÿ, ÷òî â ñëó÷àå îòñóòñòâèÿ ïðåïÿòñòâèÿ (äâóõ öèêëîâ ñ åäèíñòâåííîé òî÷êîé ñàìîïåðåêðåñòüÿ) õîðäîâàÿäèàãðàììà, ñîîòâåòñòâóþùàÿ ëþáîìó îáõîäó, áóäåò d-äèàãðàììîé, à â ëåììå 8.4 òðåáóåòñÿ ëèøü óñëîâèå èñòî÷íèê-ñòîê è íàëè÷èå d-äèàãðàììû, ñîîòâåòñòâóþùåé íåêîòîðîìó îáõîäó.
Íà ñàìîì äåëå â ñëó÷àå, åñëè 4-ãðàñ A-ñòðóêòóðîé óäîâëåòâîðÿåò óñëîâèþ èñòî÷íèê-ñòîê, âåðíî ñëåäóþùååóòâåðæäåíèå.Óòâåðæäåíèå 8.1.òîðîìóïîâîðà÷èâàþùåìó îáõîäó 4-ãðàà ñäèàãðàììîé, òîþùàÿëþáîìóíåêîÿâëÿåòñÿ d-Åñëè õîðäîâàÿ äèàãðàììà, ñîîòâåòñòâóþùàÿA-ñòðóêòóðîé,d-äèàãðàììîé ÿâëÿåòñÿ òàêæå äèàãðàììà, ñîîòâåòñòâó-ïîâîðà÷èâàþùåìó îáõîäó.8.6. Äîêàçàòåëüñòâî ãèïîòåçû Âàñèëüåâà366Ïðèâåäåì ïðèìåð. àññìîòðèì ãðà ñ A-ñòðóêòóðîé, èçîáðàæåííûé âëåâîì âåðõíåì óãëó íà ðèñ. 8.15.
Ýòîò ãðà íå âëîæèì â ïëîñêîñòü ñ ñîõðàíåíèåì A-ñòðóêòóðû. Ïðè ýòîì îáõîä psqr åãî ðåáåð, èçîáðàæåííûé âïðàâîì âåðõíåì óãëó íà òîì æå ðèñóíêå, çàäàåò õîðäîâóþ äèàãðàììó èçäâóõ çàöåïëåííûõ õîðä, ÿâëÿþùóþñÿ d-äèàãðàììîé. Èç ýòîãî ñëåäóåò, ÷òîâëîæåííûé â ïëîñêîñòü ãðà (ëåâàÿ íèæíÿÿ ÷àñòü ðèñóíêà 8.15) èçîìîðåí èçíà÷àëüíîìó ãðàó. Îäíàêî îáõîä psqr íå óäîâëåòâîðÿåò óñëîâèþèñòî÷íèê-ñòîê â âåðøèíå X : ïðîòèâîïîëîæíûå ðåáðà p è r òàêîâû, ÷òî pâõîäèò â âåðøèíó X , à r èç íåå âûõîäèò.
Ïîýòîìó ãðà, èçîáðàæåííûé âëåâîì íèæíåì óãëó, èìååò äðóãóþ A-ñòðóêòóðó â âåðøèíå X : ó íåãî ïðîòèâîïîëîæíûìè â ýòîé âåðøèíå ÿâëÿþòñÿ ðåáðà p è q , à íå p è r, êàê óèçíà÷àëüíîãî ãðàà.Îòìåòèì, ÷òî îïèñàííûé âûøå êðèòåðèé ðåàëèçóåò áûñòðûé (êâàäðàòè÷íîé ñëîæíîñòè) àëãîðèòì îïðåäåëåíèÿ, ÿâëÿåòñÿ ëè ãðà ñ A-ñòðóêòóðîéâëîæèìûì â ïëîñêîñòü ñ ñîõðàíåíèåì A-ñòðóêòóðû, è â ñëó÷àå, åñëè îí íåÿâëÿåòñÿ òàêîâûì, âûäàåò äâà öèêëà ñ ðîâíî îäíîé òàêîé òî÷êîé ïåðåêðåñòüÿ. Ïðè ýòîì ñëîæíîñòü ñ÷èòàåòñÿ îòíîñèòåëüíî ÷èñëà âåðøèí.Îñíîâíûå øàãè ýòîãî àëãîðèòìà òàêîâû.Ïåðåíóìåðóåì ðåáðà è âåðøèíû ãðàà â ïðîèçâîëüíîì ïîðÿäêå è âûïèøåì â êàæäîé âåðøèíå, êàêèå ðåáðà åé èíöèäåíòíû, ïðè ýòîì òàêæåóêàæåì ñîîòíîøåíèå ïðîòèâîïîëîæíîñòè ðåáåð â ýòîé âåðøèíå.Ïåðåíóìåðàöèÿ ðåáåð èìååò ëèíåéíóþ ñëîæíîñòü, êàê è ïåðåíóìåðàöèÿâåðøèí è çàïîìèíàíèå èíîðìàöèè î ðåáðàõ, èíöèäåíòíûõ âåðøèíå.Äàëåå ìû ñòðîèì îáõîä ãðàà. Ýòà îïåðàöèÿ òàêæå èìååò ëèíåéíóþñëîæíîñòü.Èìåÿ îáõîä, ìû ìîæåì ïðîâåðèòü, çàäàåò ëè îí óñëîâèå èñòî÷íèê-ñòîê âêàæäîé âåðøèíå.
Åñëè íåò, òî, ñîãëàñíî ëåììå 8.2, ìû ïîëó÷àåì äâà öèêëà,èìåþùèå ðîâíî îäíó òî÷êó ïåðåêðåñòüÿ. Ýòà îïåðàöèÿ ëèíåéíà.Ïóñòü îáõîä èìååò ñòðóêòóðó èñòî÷íèê-ñòîê. Ïîñòðîèì ñîîòâåòñòâóþùóþ åìó õîðäîâóþ äèàãðàììó. Îïåðàöèÿ ïîñòðîåíèÿ õîðäîâîé äèàãðàììû ëèíåéíà. Äàëåå, îïðåäåëåíèå çàöåïëåííîñòè õîðä õîðäîâîé äèàãðàììûèìååò êâàäðàòè÷íóþ ñëîæíîñòü (íóæíî ðàññìîòðåòü âñå ïàðû õîðä).
Òåìñàìûì ìû ïîëó÷èëè ìàòðèöó ïåðåñå÷åíèé õîðäîâîé äèàãðàììû èëè, ÷òî8.7. Áåñêîíå÷íîñòü êîëè÷åñòâà äëèííûõ óçëîâ,èìåþùèõ èêñèðîâàííîå çàìûêàíèå367òî æå ñàìîå, ãðà ïåðåñå÷åíèé õîðäîâîé äèàãðàììû. Ïîñëå ýòîãî âîïðîñî òîì, ÿâëÿåòñÿ ëè èñõîäíàÿ äèàãðàììà d-äèàãðàììîé ïåðåîðìóëèðóåòñÿòàê: ÿâëÿåòñÿ ëè ãðà ïåðåñå÷åíèé äâóäîëüíûì ãðàîì?Âîïðîñ îïðåäåëåíèÿ, ÿâëÿåòñÿ ëè ãðà äâóäîëüíûì ìîæíî ðåøèòü çàêâàäðàòè÷íîå ÷èñëî îïåðàöèé. Áîëåå òîãî, çà êâàäðàòè÷íîå ÷èñëî îïåðàöèé â ãðàå, íå ÿâëÿþùèìñÿ äâóäîëüíûì ìîæíî íàéòè ìèíèìàëüíûé (ïîâêëþ÷åíèþ) öèêë íå÷åòíîé äëèíû â òåðìèíàõ õîðäîâûõ äèàãðàìì (2n + 1)-óãîëüíèê. Ïîñëå ýòîãî ïàðà öèêëîâ, èìåþùèõ åäèíñòâåííóþ òî÷êóïåðåêðåñòüÿ, ñòðîèòñÿ ñîãëàñíî ëåììå 8.3.
Òàêîå ïîñòðîåíèå èìååò ëèíåéíóþ ñëîæíîñòü.8.7. Áåñêîíå÷íîñòü êîëè÷åñòâà äëèííûõ óçëîâ,èìåþùèõ èêñèðîâàííîå çàìûêàíèå çàâåðøåíèå íàñòîÿùåé ãëàâû äîêàæåì ñëåäóþùóþ òåîðåìó ( èñïîëüçîâàíèåì èíâàðèàíòîâ Âàñèëüåâà âèðòóàëüíûõ óçëîâ ïîðÿäêà íóëü). Ïðèâîäèìûé çäåñü ðåçóëüòàò áûë âïåðâûå äîêàçàí Ä.Ñèëüâåðîì è Ñ.Óèëüÿìñâ ðàáîòå [SW2℄ (íåñêîëüêî ðàíüøå, ÷åì åãî ïîëó÷èë àâòîð).Òåîðåìà 8.7.Äëÿ êàæäîãî èçîòîïè÷åñêîãî êëàññà óçëàäëèííûõ óçëîâk,òàêèõ ÷òîCl(k) = K ,Kìíîæåñòâîñ÷åòíî.àññìîòðèì êîìïàêòíûé âèðòóàëüíûé óçåë è ïðîèçâîëüíûé äëèííûé óçåë K1 , ïîëó÷åííûé íåêîòîðûì ðàçðûâàíèåì óçëà K . Òàêèìîáðàçîì ìû èìååì Cl(K1 ) = K .Ïî êàæäîìó äëèííîìó óçëó M ìû ìîæåì ïîñòðîèòü íîâûé äëèííûéóçåë M ′ òàê êàê ïîêàçàíî íà ðèñ. 8.16.Î÷åâèäíûì îáðàçîì ìû èìååì Cl(M ′ ) = Cl(M ).Ïóñòü òåïåðü K2 = (K1 )′ , K3 = (K2 )′ è òàê äàëåå: äëÿ êàæäîãî íàòóðàëüíîãî i ïîëîæèì Ki = (Ki−1 )′ .
Î÷åâèäíî, ÷òî äëÿ êàæäîãî íàòóðàëüíîãî iìû èìååì Cl(Ki ) = Cl(K1 ) = K .Ïîêàæåì, ÷òî ñðåäè óçëîâ Ki íàéäåòñÿ áåñêîíå÷íî ìíîãî ðàçëè÷íûõ.Äëÿ ýòîãî íàì äîñòàòî÷íî çàìåòèòü, ÷òî ðàçëè÷íû èõ çàìûêàíèÿ Êèøèíî,êîòîðûå îïðåäåëåíû òàê, êàê ïîêàçàíî íà ðèñ. 8.17.Äîêàçàòåëüñòâî.8.7. Áåñêîíå÷íîñòü êîëè÷åñòâà äëèííûõ óçëîâ,èìåþùèõ èêñèðîâàííîå çàìûêàíèå368Ëåãêî ïðîâåðèòü, ÷òî îïåðàöèÿ çàìûêàíèÿ Êèøèíî êîððåêòíî îïðåäåëåíà: äëÿ ýêâèâàëåíòíûõ äëèííûõ óçëîâ ìû ïîëó÷àåì ýêâèâàëåíòíûå êîìïàêòíûå óçëû ïðè òàêîì çàìûêàíèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
