Минимальные деревья Штейнера в малых окрестностях точек римановых многообразий (848703), страница 5
Текст из файла (страница 5)
. . , An âåðøèíû ïðàâèëüíîãî ìíîãîóãîëüíèêà íà ìíîãîîáðà-A1 , A2 , . . . , An , òèï êîòî{A1 , A2 , .. . , An , B1 , B2 , . . . , Bn−2 }(Bi âíóòðåííèå âåðøèíû ñåòè) è ìíîæåñòâîì ðåáåð (Bi , Bi+1 ), i = 1, . . . , n −3, (Bj , Aj+1 ), j = 1, .
. . , n − 2, (B1 , A1 ), (Bn−2 , An ) . Îáîçíà÷èì ýòîò òèï ÷åðåçG1 (ðèñ. 2). Çàìåòèì, ÷òî ãðàíèöà ìíîãîóãîëüíèêà áåç ñòîðîíû A1 An ñåòüáèíàðíîãî òèïà G1 (íåêîòîðûå ðåáðà âûðîæäåíû). Òîãäà êðàò÷àéøåå äåðåâîâ êëàññå ñåòåé áèíàðíîãî òèïà G1 ÿâëÿåòñÿ ìèíèìàëüíûì äåðåâîì Øòåéíåðà îòíîñèòåëüíî åâêëèäîâîé ìåòðèêè.  ñëó÷àÿõ n = 3, 4, 5 ýòî ïðîâåðÿåòñÿíåïîñðåäñòâåííî. Ñëó÷àé n > 6 âûòåêàåò èç ñëåäóþùåé òåîðåìû.çèè, åãî öåíòð. Ðàññìîòðèì ñåòü, ñîåäèíÿþùóþðîé áèíàðíîå äåðåâî ñ ìíîæåñòâîì âåðøèíÐèñ. 2.Ãðàô G1 .Òåîðåìà 7.
(Jarnik, Kossler [1], Du, Hwang, Weng [2]) Ïðè n > 6 ìèíèìàëüíûì äåðåâîì Øòåéíåðà äëÿ âåðøèí ïðàâèëüíîãî n-óãîëüíèêà íà åâêëèäîâîéïëîñêîñòè ÿâëÿåòñÿ åãî ãðàíèöà áåç ëþáîé ñòîðîíû.16n > 6 ñóùåñòâóåò åùå n − 1 áèíàðíîå äåðåâî, èçîìîðôG1 (îáîçíà÷èì èõ G2 , . . . , Gn ), òàêîå, ÷òî ãðàíèöà ìíîãîóãîëüíèêà áåç ñòîðîíû Ai Ai+1 åñòü êðàò÷àéøåå äåðåâî â êëàññå ñåòåé áèíàðíîãî òèïà Gi+1 ,i = 1, . . .
, n − 1, îòíîñèòåëüíî åâêëèäîâîé ìåòðèêè (ïðè n = 3 òèï, ðåàëèçóþùèé ìèíèìàëüíîå äåðåâî Øòåéíåðà, åäèíñòâåííûé; ïðè n = 4 èõ äâà; ïðèn = 5 èõ 5, íî â ýòèõ ñëó÷àÿõ ìèíèìàëüíûå äåðåâüÿ Øòåéíåðà íå ÿâëÿþòñÿãðàíèöàìè áåç ñòîðîíû). Îáîçíà÷èì ÷åðåç Ωn ìíîæåñòâî òèïîâ, ðåàëèçóþùèõìèíèìàëüíûå äåðåâüÿ Øòåéíåðà äëÿ âåðøèí ïðàâèëüíîãî n-óãîëüíèêà â åâêëèäîâîé ìåòðèêå (Ωn = {G1 , . . . , Gn }). Èç òåîðåì 6 è 7 ïîëó÷àåòñÿ ñëåäóþùèéÇàìåòèì, ÷òî ïðèíîåâûâîä.n ñóùåñòâóåò r0 > 0 òàêîå, ÷òî äëÿ âåðøèín-óãîëüíèêà ñ öåíòðîì â O è ðàäèóñîì r < r0 íà ðèìàMk òèïû ìèíèìàëüíûõ äåðåâüåâ Øòåéíåðà ïðèíàäëåæàòÑëåäñòâèå 3.
Äëÿ äàííîãîëþáîãî ïðàâèëüíîãîíîâîì ìíîãîîáðàçèèìíîæåñòâóΩn . äàëüíåéøåì áóäåì ðàññìàòðèâàòü äâóìåðíîå ïîëíîå ãëàäêîå ðèìàíîâîM2 . Ìû ïîêàæåì, ÷òî ïðè n > 7 äëÿ êàæäîé òî÷êè O ∈ M2r0 > 0 òàêîå, ÷òî êðàò÷àéøåé ñåòüþ, ñîåäèíÿþùåé âåðøèíû ëþáîãî ïðàâèëüíîãî n-óãîëüíèêà ñ öåíòðîì â O è ðàäèóñîì r < r0 ÿâëÿåòñÿ ãðàíèöàïðàâèëüíîãî n-óãîëüíèêà áåç íàèáîëüøåé åãî ñòîðîíû.
Ðàññòîÿíèå ìåæäó òî÷êàìè A, B ∈ M2 áóäåì îáîçíà÷àòü ρ(A, B). Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâîV òî÷åê ìíîãîîáðàçèÿ âûïóêëî, åñëè êàæäàÿ ïàðà åãî òî÷åê ñîäåðæèòñÿ â Vâìåñòå ñ ëþáîé êðàò÷àéøåé êðèâîé, ñîåäèíÿþùåé ýòè òî÷êè. Âûïóêëîé îáîëî÷êîé conv V ìíîæåñòâà V áóäåì íàçûâàòü íàèìåíüøåå ïî âêëþ÷åíèþ âûïóêëîåìíîæåñòâî, ñîäåðæàùåå V . ïåðâóþ î÷åðåäü, çàìåòèì, ÷òî äëÿ êàæäîé òî÷êè X ∈ M2 ñóùåñòâóåòrX > 0 òàêîå, ÷òî ïðè r < rX îêðåñòíîñòü U (X, r) = {Y ∈ M2 ρ(X, Y ) <r} ãîìåîìîðôíà R2 è ÿâëÿåòñÿ âûïóêëîé, ïðè÷åì ëþáûå äâå òî÷êè A, B ∈U (X, r) ñîåäèíåíû åäèíñòâåííîé ãåîäåçè÷åñêîé, ëåæàùåé â U (X, r), è åå äëèíàðàâíà ρ(A, B). Äàííûé ðåçóëüòàò ìîæíî íàéòè â [21; § 3, òåîðåìà 3.6].
Ýòóãåîäåçè÷åñêóþ áóäåì íàçûâàòü îòðåçêîì, ñîåäèíÿþùèì A è B . Äëÿ êàæäîéòî÷êè X ∈ M2 áóäåì îáîçíà÷àòü U (X) = U (X, r) ïðè íåêîòîðîì 0 < r < rX .Ðàññìîòðèì çàìêíóòóþ êðèâóþ γ áåç ñàìîïåðåñå÷åíèé, îáðàç êîòîðîé íàõîäèòñÿ â U (X). Ïî òåîðåìå Æîðäàíà, êðèâàÿ γ äåëèò U (X) íà äâå îáëàñòè.Îáëàñòüþ, îãðàíè÷åííîé êðèâîé γ , áóäåì íàçûâàòü òó èç íèõ, ÷òî íå ïðèëåãàåò ê ∂U (X). Ìíîãîóãîëüíèêîì â U (X) áóäåì íàçûâàòü çàìûêàíèå îáëàñòè,ìíîãîîáðàçèåñóùåñòâóåòîãðàíè÷åííîé íåêîòîðîé êóñî÷íî-ãåîäåçè÷åñêîé çàìêíóòîé êðèâîé áåç ñàìîïåðåñå÷åíèé.Ïóñòü γ çàìêíóòàÿ êðèâàÿ áåç ñàìîïåðåñå÷åíèé â U (X),è â îáëàñòè, îãðàíè÷åííîé êðèâîé γ , ëåæèò âûïóêëûé ìíîãîóãîëüíèê T0 (åãîâåðøèíû è ñòîðîíû ìîãóò ïðèíàäëåæàòü îáðàçó êðèâîé γ). Òîãäà ïåðèìåòðìíîãîóãîëüíèêà T0 íå ïðåâîñõîäèò äëèíû êðèâîé γ , ïðè÷åì ðàâåíñòâî äîñòèãàåòñÿ ëèøü òîãäà, êîãäà ãðàíèöà ìíîãîóãîëüíèêà ñîâïàäàåò ñ îáðàçîì ýòîéêðèâîé.Óòâåðæäåíèå 8.Äîêàçàòåëüñòâî.
Ïðè îáõîäå âäîëü ãðàíèöû ìíîãîóãîëüíèêàåãî âåðøèíûA1 , A2 , . . . , An(ðèñ. 3).Ïðîäîëæèì îòðåçîêA1 A2T0íàçîâåìçà âåðøèíóÐèñ. 3.A1 ,à îòðåçîêAn−1 AnÏåðèìåòð T0 íå áîëüøå äëèíû êðèâîé γ .çà âåðøèíóAn . ñèëó âûïóêëîñòèT0 ,ðàññìàòðèâà-åìûå ïðîäîëæåíèÿ ëèáî ïåðåñåêóòñÿ äðóã ñ äðóãîì (â ýòîì ñëó÷àå ìû ïîëó-n − 1 âåðøèíîé, ïåðèìåòð êîòîðîãî áîëüøåïåðèìåòðà T0 , òàê êàê ñòîðîíà A1 An ìíîãîóãîëüíèêà T0 êðàò÷àéøàÿ; ïðîäåëàåì ñ íèì òî æå ñàìîå), ëèáî êàæäîå ïåðåñå÷åò êðèâóþ γ . Ïåðâîå ïåðåñå÷åíèå ïðîäîëæåíèÿ îòðåçêà A1 A2 ñ êðèâîé γ íàçîâåì B1 , à ïåðâîå ïåðåñå÷åíèå ïðîäîëæåíèÿ îòðåçêà An−1 An ñ êðèâîé γ íàçîâåì Bn . Òî÷êè B1 è Bnäåëÿò êðèâóþ γ íà äâå ÷àñòè.
Òó ÷àñòü, êîòîðàÿ â îáúåäèíåíèè ñ îòðåçêàìè B1 A2 , A2 A3 , . . . , An−2 An−1 , An−1 Bn ÿâëÿåòñÿ çàìêíóòîé êðèâîé (áåç ñàìîïåðåñå÷åíèé), îãðàíè÷åâàþùåé îáëàñòü, â êîòîðîé ñîäåðæèòñÿ T0 , íàçîâåì γ1(âûðîæäåííûé ñëó÷àé B1 ñîâïàäàåò ñ Bn , è γ1 âûðîæäàåòñÿ â òî÷êó). Ôèãóðó, ãðàíèöåé êîòîðîé ÿâëÿåòñÿ ýòà çàìêíóòàÿ êðèâàÿ, à T0 ëåæèò âíóòðèíåå, íàçîâåì T1 .
Äëèíà ãðàíèöû T1 íå ìåíüøå ïåðèìåòðà T0 , òàê êàê ñòîðîíàA1 An ìíîãîóãîëüíèêà T0 êðàò÷àéøàÿ, ïðè÷åì ðàâåíñòâî äîñòèãàåòñÿ ëèøüòîãäà, êîãäà êðèâàÿ γ1 ñîâïàäàåò ñî ñòîðîíîé A1 An ìíîãîóãîëüíèêà T0 . Äàëåå,ïðîäîëæèì îòðåçîê A2 A3 çà âåðøèíó A2 äî ïåðâîãî ïåðåñå÷åíèÿ ñ êðèâîé γ ,êîòîðîå íàçîâåì B2 .
Àíàëîãè÷íî, ðàññìîòðèì ôèãóðó T2 , ñîäåðæàùóþ ôèãóðóT1 , ãðàíèöà êîòîðîé îòëè÷àåòñÿ îò ãðàíèöû T1 òåì, ÷òî îòðåçîê A2 B1 çàìåíåííà îáúåäèíåíèå îòðåçêà A2 B2 è ñîîòâåòñòâóþùåé ÷àñòè êðèâîé γ , ñîåäèíÿþùåé B1 è B2 . Äëèíà ãðàíèöû T2 íå ìåíüøå äëèíû ãðàíèöû T1 , òàê êàê îòðåçîêA2 B1 , ïðèíàäëåæàùèé ∂T1 , ÿâëÿåòñÿ êðàò÷àéøåé. Ïðîäîëæàÿ ýòîò ïðîöåññ,íà n − 1 øàãå ìû ðàññìîòðèì ôèãóðó Tn−1 , ãðàíèöà êîòîðîé îáúåäèíåíèå÷àñòè êðèâîé γ è îòðåçêà Bn−1 Bn (äëèíà ýòîé ãðàíèöû íå ìåíüøå äëèí ãðàíèöôèãóð Tk ïðè k < n − 1).
Òàê êàê ýòîò îòðåçîê êðàò÷àéøàÿ, òî äëèíà âñåéêðèâîé γ íå ìåíüøå äëèíû ãðàíèöû Tn−1 . Òàêèì îáðàçîì, ìû ïîêàçàëè, ÷òîäëèíà êðèâîé γ íå ìåíüøå ïåðèìåòðà T0 , è ðàâåíñòâî äîñòèãàåòñÿ ëèøü òîãäà,êîãäà ãðàíèöà ìíîãîóãîëüíèêà T0 ñîâïàäàåò ñ îáðàçîì ýòîé êðèâîé.÷èì âûïóêëûé ìíîãîóãîëüíèê ñÓòâåðæäåíèå 9. Ïóñòü V êîíå÷íîå ìíîæåñòâî òî÷åê â U (X). Òîãäàâûïóêëàÿ îáîëî÷êà conv V ýòîãî ìíîæåñòâà ÿâëÿåòñÿ âûïóêëûì ìíîãîóãîëüíèêîì (âîçìîæíî, âûðîæäåííûì).18Äîêàçàòåëüñòâî.
Ñëó÷àé, â êîòîðîì âñå òî÷êè ìíîæåñòâàVëåæàò íà îä-íîé ãåîäåçè÷åñêîé, ÿâëÿåòñÿ òðèâèàëüíûì. Ïóñòü âñå òî÷êè ìíîæåñòâàVíåëåæàò íà îäíîé ãåîäåçè÷åñêîé. Ðàññìîòðèì èíòåðâàë ãåîäåçè÷åñêîé, êîíöû êîòîðîãî ëåæàò íà∂U (X).Îí äåëèòU (X)íà äâå îáëàñòè. Îáúåäèíåíèå îäíîéîáëàñòè ñ ýòèì èíòåðâàëîì ãåîäåçè÷åñêîé áóäåì íàçûâàòüïîëóîêðåñòíîñòüþ.Çàìåòèì, ÷òî ïîëóîêðåñòíîñòü ÿâëÿåòñÿ âûïóêëîé. Îòðåçîê, ñîåäèíÿþùèé ïàðó òî÷åê èçV,áóäåì íàçûâàòüòî÷êè ìíîæåñòâàV,ãðàíè÷íûì,åñëè îí íå ïðîõîäèò ÷åðåç äðóãèåè âñå òî÷êè ìíîæåñòâàVëåæàò â îäíîé èç äâóõ ïîëó-îêðåñòíîñòåé, îáðàçîâàííûõ ãåîäåçè÷åñêîé, ÿâëÿþùåéñÿ ïðîäîëæåíèåì ýòîãîîòðåçêà.Çàìåòèì, ÷òî êàæäàÿ òî÷êà ìíîæåñòâàVëèáî íå ÿâëÿåòñÿ êîíöîì íèêà-êîãî ãðàíè÷íîãî îòðåçêà, ëèáî ÿâëÿåòñÿ êîíöîì ðîâíî äâóõ ãðàíè÷íûõ îòðåçêîâ. Äåéñòâèòåëüíî, ïóñòüíåêîòîðóþ òî÷êóC ∈ V.AB ãðàíè÷íûé îòðåçîê,Åñëè îòðåçîêACA, B ∈ V .Ðàññìîòðèìíå ÿâëÿåòñÿ ãðàíè÷íûì, òî â ïî-ëóîêðåñòíîñòè, îáðàçîâàííîé ïðîäîëæåíèåì ýòîãî îòðåçêà, è íå ñîäåðæàùåéòî÷êóB,ëåæèò íåêîòîðàÿ òî÷êàC1ìíîæåñòâàV.Ïåðåéäåì ê åå ðàññìîòðå-íèþ è ïðîäåëàåì òó æå ïðîöåäóðó.
Çàìåòèì, ÷òî â ïîëóîêðåñòíîñòè, îáðàçîâàííîé ïðîäîëæåíèåì îòðåçêàÒàê êàê ìíîæåñòâîVAC1 ,ê ðàññìîòðåíèþ íåêîòîðîé òî÷êèíûì,B 6= C0 .è ñîäåðæàùåé òî÷êóC0òàêîé, ÷òî îòðåçîêÏðè ýòîì ÿñíî, ÷òî òî÷êàãðàíè÷íûõ îòðåçêîâ.B,ëåæèò òî÷êàC.êîíå÷íî, ÷åðåç êîíå÷íîå êîëè÷åñòâî øàãîâ ìû ïðèäåìAAC0ÿâëÿåòñÿ ãðàíè÷-íå ìîæåò ÿâëÿòüñÿ êîíöîì òðåõÄåéñòâèòåëüíî, â òàêîì ñëó÷àå ïðîäîëæåíèå îäíîãî èçíèõ ðàçäåëÿëî áû ðàçëè÷íûå êîíöû äâóõ äðóãèõ.Q0 , îáðàçîâàííóþïðîäîëæåíèåì ýòîãî îòðåçêà, ñîäåðæàùóþ âñå òî÷êè ìíîæåñòâà V .
Ïóñòü A1 A2 âòîðîé ãðàíè÷íûé îòðåçîê, êîíöîì êîòîðîãî ÿâëÿåòñÿ òî÷êà A1 . Äîáàâèì êîòðåçêó A0 A1 îòðåçîê A1 A2 , è íàçîâåì γ1 êóñî÷íî-ãåîäåçè÷åñêóþ êðèâóþ, îáðàçîì êîòîðîé ÿâëÿåòñÿ èõ îáúåäèíåíèå. Ïåðåñå÷åíèå Q0 è ïîëóîêðåñòíîñòè,îáðàçîâàííîé ïðîäîëæåíèåì îòðåçêà A1 A2 , ñîäåðæàùåé âñå òî÷êè ìíîæåñòâàV , íàçîâåì Q1 .
Ïðîäîëæàÿ äàííóþ ïðîöåäóðó, íà íåêîòîðîì øàãå ìû ïîëó÷èìçàìêíóòóþ êóñî÷íî-ãåîäåçè÷åñêóþ êðèâóþ γk áåç ñàìîïåðåñå÷åíèé, è ìíîæåñòâî Qk , ÿâëÿþùååñÿ âûïóêëûì êàê ïåðåñå÷åíèå âûïóêëûõ ïîëóîêðåñòíîñòåé.Ïðè ýòîì Qk ÿâëÿåòñÿ çàìûêàíèåì îáëàñòè, îãðàíè÷åííîé γk . Òàêèì îáðàçîì,Qk ÿâëÿåòñÿ âûïóêëûì ìíîãîóãîëüíèêîì ñ ãðàíèöåé γk , âåðøèíû êîòîðîãî íåêîòîðûå òî÷êè ìíîæåñòâà V , è âñå òî÷êè èç V ñîäåðæàòñÿ â Qk .
Èç ýòîãîñëåäóåò, ÷òî conv V ⊆ Qk . Ïðè ýòîì, îáðàç γk ëåæèò â conv V , òàê êàê ÿâëÿåòñÿîáúåäèíåíèåì îòðåçêîâ, ñîåäèíÿþùèõ òî÷êè èç V . Ëþáàÿ âíóòðåííÿÿ òî÷êàF ∈ Qk òàêæå ëåæèò â conv V , òàê êàê ëåæèò íà íåêîòîðîì îòðåçêå, êîíöûêîòîðîãî ëåæàò íà γk . Òàêèì îáðàçîì, Qk ⊆ conv V . Ýòî îçíà÷àåò, ÷òî Qkñîâïàäàåò ñ conv V .Ðàññìîòðèì ãðàíè÷íûé îòðåçîêA0 A1è ïîëóîêðåñòíîñòüÒåîðåìà 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
