Характеристики конечных метрических пространств, порожденных графами (1105193), страница 2
Текст из файла (страница 2)
À â 2011 ãîäó Ëèí, Ëó è ßó (â [12]) ìîäèôèöèðîâàëè îïðåäåëåíèå Îëèâüåäëÿ êðèâèçíû Ðè÷÷è öåïåé Ìàðêîâà íà ìåòðè÷åñêèõ ïðîñòðàíñòâàõ ( [11]).Èçíà÷àëüíî êëàññè÷åñêîå ïîíÿòèå êðèâèçíû Ðè÷÷è ñâÿçûâàëîñü ñ ðèìàíîâûìè ìíîãîîáðàçèÿìè. Îíà åñòåñòâåííî îïðåäåëÿåòñÿ êàê ñâåðòêà òåíçîðà Ðèìàíà èèìååò ñëåäóþùóþ ãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ. Íà ðèìàíîâîì ìíîãîîáðàçèèðàññìàòðèâàþòñÿ äâå äîñòàòî÷íî áëèçêèå òî÷êè x è y , ïîðîæäàþùèå êàñàòåëüíûéâåêòîð xy .
 òî÷êå x ðàññìîòðèì äðóãîé êàñàòåëüíûé âåêòîð w è ïóñòü âåêòîð w′ êàñàòåëüíûé âåêòîð â òî÷êå y , ïîëó÷åííûé èç âåêòîðà w ïàðàëëåëüíûì ïåðåíîñîì â íàïðàâëåíèè xy . Äàëåå, ïîñìîòðèì íà ïîâåäåíèå ãåîäåçè÷åñêèõ, âûïóùåííûõ èç òî÷åê x è y â íàïðàâëåíèÿõ ñîîòâåòñòâåííî w è w′ . Åñëè ãåîäåçè÷åñêèåáóäóò ñáëèæàòüñÿ, òî êðèâèçíà áóäåò ïîëîæèòåëüíîé, åñëè ãåîäåçè÷åñêèå áóäóòðàçúåçæàòüñÿ, òî êðèâèçíà áóäåò îòðèöàòåëüíîé. Êðèâèçíà Ðè÷÷è â íàïðàâëåíèèxy õàðàêòåðèçóåò ñðåäíåå çíà÷åíèå êðèâèçí ïî âñåì íàïðàâëåíèÿì w â òî÷êå x.7Åñëè ïðåäñòàâèòü âñå âîçìîæíûå íàïðàâëåíèÿ w â âèäå ãåîäåçè÷åñêîé ñôåðû Sxñ öåíòðîì â òî÷êå x, òî çíàê êðèâèçíû Ðè÷÷è ïîêàçûâàåò áóäåò ëè ðàññòîÿíèåìåæäó öåíòðàìè ãåîäåçè÷åñêèõ ñôåð Sx è Sy áîëüøå èëè ìåíüøå, ÷åì ðàññòîÿíèåìåæäó òî÷êîé a, ëåæàùåé íà ãåîäåçè÷åñêîé ñôåðå Sx , è òî÷êîé íà ãåîäåçè÷åñêîéñôåðå Sy , ïîëó÷åííîé ïàðàëëåëüíûì ïåðåíîñîì âåêòîðà xa âäîëü xy .Àíàëîãè÷íîå ïîíÿòèå êðèâèçíû Ðè÷÷è ìîæíî ââåñòè äëÿ âçâåøåííûõ äåðåâüåâ.
 ýòîì ñëó÷àå â êà÷åñòâå ãåîäåçè÷åñêèõ ñôåð Sx è Sy áóäóò ðàññìàòðèâàòüñÿîêðåñòíîñòè âåðøèí x è y , òî åñòü âñå âåðøèíû, ñìåæíûå ñ íèìè.  êà÷åñòâåìåòðèêè íà ãðàôå áóäåì ðàññìàòðèâàòü ðàññòîÿíèå, ïîðîæäåííîå âåñîì ω , èçìåðÿþùåå íàèìåíüøèé âåñ ïóòè, ñîåäèíÿþùåãî åãî äâå òî÷êè.Áîëåå ôîðìàëüíî. Ðàññìîòðèì âçâåøåííûé ãðàô G = (V, E), ôóíêöèÿ ω : E →åäè→ R, íàçûâàåìóþ ðàñ-R ñòàâèò â ñîîòâåòñòâèå êàæäîìó ðåáðó âåñ, ðàâíûé 1. Ôóíêöèÿ ω íàçûâàåòñÿíè÷íîé âåñîâîé ôóíêöèåé è ïîðîæäàåò ôóíêöèþ d : V × Vñòîÿíèåì, ïîðîæäåííûì åäèíè÷íîé âåñîâîé ôóíêöèåé Ýòà ôóíêöèÿ, î÷åâèäíî,óäîâëåòâîðÿåò ñòàíäàðòíûì àêñèîìàì ìåòðèêè, ïîýòîìó ïàðó V = (V, d) ìîæíîðàññìàòðèâàòü êàê ìåòðè÷åñêîå ïðîñòðàíñòâî.
Íà ýòîì ìåòðè÷åñêîì ïðîñòðàíñòâåçàäàäèì ðàñïðåäåëåíèå âåðîÿòíîñòè mαx : V → [0, 1] ñïåöèàëüíîãî âèäà:mαx (y) =α,åñëè x = y ,1−αdeg(x) ,åñëè x ∼ y ,0,åñëè x y è x ̸= y ,(∗)ãäå x ∼ y îáîçíà÷àåò, ÷òî âåðøèíû x è y ñìåæíû (òàêîå îáîçíà÷åíèå ââåäåíîJurgen Jost ñì., íàïðèìåð, [19]). Ýòè ôóíêöèè áóäåì íàçûâàòüôóíêöèÿìè ñëó÷àé-íîãî áëóæäàíèÿ. È ââåäåì ôóíêöèþ Âàññåðøòåéíà 1 ïîðÿäêà W (mαx, mαy), êîòîðàÿ áóäåò èçìåðÿòü ðàññòîÿíèå ìåæäó äâóìÿ ôóíêöèÿìè mαx è mαy íà V = (V, d):W (mαx , mαy ) =∑maxf 1-ëèïøèöåâà ôóíêöèÿ v∈Vf (v)(mx (v) − my (v))(0.0.1)Ïðè ðåøåíèè òðàíñïîðòíîé çàäà÷è ýòà ôóíêöèÿ ÿâëÿåòñÿ ìàêñèìóìîì öåëåâîéôóíêöèè, ïîýòîìó ïî-äðóãîìó åå íàçûâàþò ôóíêöèåéðîâîêðàññòîÿíèÿ òðàíñïîðòè-(ñì.
ðàçäåë 2.1). Îíà ñ÷èòàåò ìèíèìàëüíóþ ñòîèìîñòü ïåðåâîçêè ãðóçà8åäèíè÷íîé ìàññû èç îêðåñòíîñòè âåðøèíû x â îêðåñòíîñòü âåðøèíû y .  îêðåñòíîñòÿõ ýòèõ âåðøèí ãðóç ðàñïðåäåëåí ñîãëàñíî ôóíêöèÿì mαx è mαy , ââåäåííûìðàíåå. Áîëåå ïîäðîáíî î ôóíêöèè Âàññåðøòåéíà ïåðâîãî ïîðÿäêà, î åå ãåîìåòðè÷åñêîì è ôèçè÷åñêîì ñìûñëå ðàññêàçàíî âî âòîðîé ãëàâå äèññåðòàöèè.Ñëåäóÿ ðàáîòàì [12, 14], îïðåäåëèì α-êðèâèçíó Ðè÷÷è ôîðìóëîé kα(x, y) =1 − W (mαx , mαy )/ d(x, y).
Ïðè α = 0 âåëè÷èíà k0 (x, y) êðèâèçíà Ðè÷÷è-Îëèâüå.Êðèâèçíîé Ðè÷÷è íàçîâåì ôóíêöèþ:kα (x, y).α→1 1 − αÔóíêöèÿ k(x, y) çàäàíà êîððåêòíî. Ñóùåñòâîâàíèå ïðåäåëà íåñëîæíî ïðîâåk(x, y) := limðèòü ñ ïîìîùüþ ïðàâèëà Ëîïèòàëÿ. òåðìèíàõ òðàíñïîðòíîé çàäà÷è ýòà ôóíêöèÿ ïîêàçûâàåò êàê ìåíÿåòñÿ îïòèìàëüíàÿ ñòîèìîñòü ïåðåâîçêè ãðóçà ìàññû 1, ñêîíöåíòðèðîâàííîãî â âåðøèíå, ïðèâîçíèêíîâåíèè ïîãðåøíîñòè, òî åñòü, êîãäà ÷àñòü ýòîãî ãðóçà áåñêîíå÷íî ìàëîéìàññû ðàñïðåäåëåíà ïî ñîñåäíèì âåðøèíàì. Òàêèì îáðàçîì, ïî êðèâèçíå Ðè÷÷èìîæíî îïðåäåëÿòü, êàêàÿ ïåðåâîçêà ÿâëÿåòñÿ áîëåå âûãîäíîé èç îêðåñòíîñòèîäíîé âåðøèíû â îêðåñòíîñòü äðóãîé âåðøèíû, èëè èç îäíîé âåðøèíû â äðóãóþ. ïåðâîì ñëó÷àå çíà÷åíèå êðèâèçíû Ðè÷÷è áóäåò ïîëîæèòåëüíûì, âî âòîðîì îòðèöàòåëüíûì è ðàâíî íóëþ, åñëè òàêèå ïåðåâîçêè îäèíàêîâûå ïî ñòîèìîñòè.Èçó÷àÿ ðàáîòû [12, 14, 11], àâòîð ïðåäëîæèë ðàññìîòðåòü êðèâèçíó Ðè÷÷è ìåæäó âåðøèíàìè âçâåøåííîãî äåðåâà G = (V, E) ñ ïðîèçâîëüíîé âåñîâîé ôóíêöèåé(íå åäèíè÷íîé) ω : E → R+ , ïîðîæäàþùåé ìåòðè÷åñêîå ïðîñòðàíñòâî (V, dω ), ãäådω : V × V → R ôóíêöèÿ, âû÷èñëÿþùàÿ ìèíèìàëüíûé âåñ ïóòè ìåæäó äâóìÿâåðøèíàìè ãðàôà G.
Äëÿ íîâîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà (V, dω ) òàêæå ðàññìàòðèâàþòñÿ mαx âèäà (∗) è ôóíêöèè ðàññòîÿíèÿ òðàíñïîðòèðîâîê W (mαx , mαy ) âèäà (1). Çàìåíèâ åäèíè÷íóþ ôóíêöèþ ðàññòîÿíèÿ ïðîèçâîëüíîé, α-êðèâèçíà Ðè÷÷èîïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:kα (x, y, ω) = 1 − W (mαx , mαy )/ dω (x, y),òîãäà êðèâèçíà Ðè÷÷è k(x, y, ω) := limα→19kα (x,y,ω)1−α .Äëÿ êðèâèçíû Ðè÷÷è ñ ïðîèçâîëüíîé ôóíêöèåé ðàññòîÿíèÿ dω â äèññåðòàöèèïîëó÷åíà ñëåäóþùàÿ òåîðåìà è íåêîòîðûå ñëåäñòâèÿ èç íåå:Ïóñòü (G, ω), G = (V, E) âçâåøåííîå äåðåâî ñ âåñîâîé ôóíêöèåé ω. Òîãäà êðèâèçíà Ðè÷÷è ìåæäó ëþáûìè ðàçëè÷íûìè âåðøèíàìè äåðåâà Gâû÷èñëÿåòñÿ ïî ñëåäóþùåé ôîðìóëå:Òåîðåìà 2.k(x, y, ω) =1dω (x,y)(1deg(x)∑z∼x kz· dω (z, x) +1deg(y))z∼y kz · dω (z, y) , (0.0.2)∑ãäå kz = 1 , åñëè ðåáðî xz âõîäèò â ïóòü xy, è kz = −1, åñëè íå âõîäèò.Îäíèì èç âàæíûõ ñëåäñòâèé ýòîé ôîðìóëû ÿâëÿåòñÿ ñëåäñòâèå 2.
Îêàçûâàåòñÿ,çíàÿ êðèâèçíû Ðè÷÷è ìåæäó âñåìè ïàðàìè âåðøèí áèíàðíîãî äåðåâà ñ åäèíè÷íîéâåñîâîé ôóíêöèåé, ìîæíî âîññòàíîâèòü ñòðóêòóðó ýòîãî äåðåâà.  äîêàçàòåëüñòâåñëåäñòâèÿ 2 ïðèâåäåí ñïåöèàëüíûé àëãîðèòì, âîññòàíàâëèâàþùèé ñòðóêòóðó äåðåâà.Êðîìå òîãî, ïîëó÷åíû òî÷íûå âåðõíÿÿ è íèæíÿÿ îöåíêè êðèâèçíû Ðè÷÷è ìåæäó ëþáûìè ðàçëè÷íûìè âåðøèíàìè äåðåâà, ñì. òî÷íûå ôîðìóëû â Òåîðåìå 12.Äàëüíåéøåå èçó÷åíèå îäíîìåðíîé çàäà÷è Ãðîìîâà î ìèíèìàëüíûõ çàïîëíåíèÿõ êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ ìîæåò ïîìî÷ü ãëóáæå ïîíÿòü âçàèìîñâÿçüêðèâèçíû Ðè÷÷è â êëàññè÷åñêîì ñìûñëå è êðèâèçíû Ðè÷÷èÎëèâüå äëÿ âçâåøåííûõ ãðàôîâ. À èìåííî, èíòåðåñíî ïðîñëåäèòü çà ïîâåäåíèåì êðèâèçí Ðè÷÷èÎëèâüå ìèíèìàëüíûõ çàïîëíåíèé êîíå÷íûõ ε-ñåòåé ðèìàíîâà ìíîãîîáðàçèÿïðè ïðåäåëüíîì ïåðåõîäå (â ìåòðèêå ÃðîìîâàÕàóñäîðôà) ê ñàìîìó ìíîãîîáðàçèþ.
Ãèïîòåçà ñîñòîèò â òîì, ÷òî êðèâèçíû çàïîëíåíèé ìîãóò èìåòü ïðåäåë âíåêîòîðîì ðàçóìíîì ñìûñëå, è ýòîò ïðåäåë ñâÿçàí ñ êðèâèçíîé Ðè÷÷è ðèìàíîâàìíîãîîáðàçèÿ èëè åãî çàïîëíåíèÿ â ñìûñëå Ãðîìîâà. Òàêæå èíòåðåñíî âûÿñíèòü,ñóùåñòâóåò ëè ïðåäåë ñàìèõ ìèíèìàëüíûõ çàïîëíåíèé ε-ñåòåé â ìåòðèêå ÃðîìîâàÕàóñäîðôà è, åñëè äà, òî êàê îí ñâÿçàí ñ ìèíèìàëüíûì çàïîëíåíèåì ìíîãîîáðàçèÿ è/èëè ñàìèì ìíîãîîáðàçèåì.10Ñòðóêòóðà ðàáîòûÄèññåðòàöèÿ ñîñòîèò èç ââåäåíèÿ, äâóõ ãëàâ, çàêëþ÷åíèÿ, ñïèñêà ïóáëèêàöèé ïîòåìå äèññåðòàöèè è ñïèñêà ëèòåðàòóðû.Ïåðâàÿ ãëàâà ïîñâÿùåíà çàäà÷å îïèñàíèÿ àääèòèâíûõ êîíå÷íûõ ìåòðè÷åñêèõïðîñòðàíñòâ â òåðìèíàõ ìèíèìàëüíûõ çàïîëíåíèé.  ðàçäåëå 1.5 ñôîðìóëèðîâàíè äîêàçàí êðèòåðèé àääèòèâíîñòè êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ.Âòîðàÿ ãëàâà ïîñâÿùåíà èññëåäîâàíèþ êðèâèçíû Ðè÷÷è íà ìåòðè÷åñêèõ ïðîñòðàíñòâàõ ñî ñëó÷àéíûì áëóæäàíèåì.
 ðàçäåëå 2.3 àâòîð äîêàçûâàåò ôîðìóëóäëÿ êðèâèçíû Ðè÷÷è ìåæäó âåðøèíàìè âçâåøåííîãî äåðåâà.  ðàçäåëàõ 2.4 2.5ïîëó÷åíû ñëåäñòâèÿ èç ôîðìóëû äëÿ áèíàðíûõ äåðåâüåâ, òàêæå ïîëó÷åíû òî÷íûåîöåíêè êðèâèçíû Ðè÷÷è ìåæäó âåðøèíàìè âçâåøåííîãî äåðåâà â ðàçäåëå 2.6.Ñïèñîê îñíîâíûõ ðåçóëüòàòîâ, âûíîñèìûõ íà çàùèòóÐåçóëüòàòû, âûíîñèìûå íà çàùèòó ÿâëÿþòñÿ íîâûìè.  äèññåðòàöèè ïîëó÷åíûñëåäóþùèå ðåçóëüòàòû:1.
Êðèòåðèé àääèòèâíîñòè êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ (Òåîðåìà 1);2. Ôîðìóëà äëÿ âû÷èñëåíèÿ êðèâèçíû Ðè÷÷è äëÿ âçâåøåííûõ äåðåâüåâ (Òåîðåìà 2);3. Òåîðåìà î âîññòàíîâëåíèè ñòðóêòóðû áèíàðíîãî äåðåâà ïî ìàòðèöå êðèâèçíÐè÷÷è ìåæäó âåðøèíàìè ýòîãî äåðåâà (Ñëåäñòâèå 2);4. Îöåíêà êðèâèçíû Ðè÷÷è âçâåøåííîãî äåðåâà ñ ïðîèçâîëüíîé âåñîâîé ôóíêöèåé (Òåîðåìà 12).Ìåòîäû èññëåäîâàíèÿ äèññåðòàöèè ïðèìåíÿþòñÿ ìåòîäû ìåòðè÷åñêîé, äèñêðåòíîé ãåîìåòðèè, ìåòîäûòåîðèè ãðàôîâ, ìåòîäû òåîðèè ìèíèìàëüíûõ çàïîëíåíèé êîíå÷íûõ ìåòðè÷åñêèõïðîñòðàíñòâ.11Àïðîáàöèÿ ðàáîòûÐåçóëüòàòû äèññåðòàöèè äîêëàäûâàëèñü íà ñëåäóþùèõ ñåìèíàðàõ è êîíôåðåíöèÿõ:1. Íàó÷íàÿ êîíôåðåíöèÿ ¾Ëîìîíîñîâñêèå ÷òåíèÿ¿ (ÌÃÓ, àïðåëü 2011 ãîäà);2.
Ìåæäóíàðîäíàÿ êîíôåðåíöèÿ ¾Âîðîíåæñêàÿ çèìíÿÿ ìàòåìàòè÷åñêàÿ øêîëàÑ.Ã. Êðåéíà¿ (28 ÿíâàðÿ 2012 ãîäà);3. Ìåæäóíàðîäíàÿ êîíôåðåíöèÿ Àëåêñàíäðîâñêèå ÷òåíèÿ (ÌÃÓ, ìàé 2012 ãîäà);4. Ñåìèíàð ¾Äèôôåðåíöèàëüíàÿ ãåîìåòðèÿ è ïðèëîæåíèÿ¿ ïîä ðóêîâîäñòâîìàêàäåìèêà À.Ò. Ôîìåíêî (ÌÃÓ, 18 íîÿáðÿ 2013 ãîäà);5. Ìåæäóíàðîäíàÿ êîíôåðåíöèÿ ¾Âîðîíåæñêàÿ çèìíÿÿ ìàòåìàòè÷åñêàÿ øêîëàÑ.Ã. Êðåéíà¿ (29 ÿíâàðÿ 2014 ãîäà);6. Ñåìèíàð ¾Ìèíèìàëüíûå ñåòè¿ ïîä ðóêîâîäñòâîì ïðîôåññîðîâ À.
Î. Èâàíîâàè À. À. Òóæèëèíà, íåîäíîêðàòíî (ÌÃÓ, 2010 - 2016 ãã.);7. Ìåæäóíàðîäíàÿ êîíôåðåíöèÿ Àëåêñàíäðîâñêèå ÷òåíèÿ (ÌÃÓ, ìàé 2016 ãîäà).ÏóáëèêàöèèÐåçóëüòàòû äèññåðòàöèè îïóáëèêîâàíû â ÷åòûðåõ ñòàòüÿõ àâòîðà [1.1, 1.2, 1.3, 1.4]è ñåìè òåçèñàõ, èç íèõ â æóðíàëàõ èç ïåðå÷íÿ ÂÀÊ 4 ñòàòüè.Áëàãîäàðíîñòè.Àâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü ñâîåìó íàó÷íîìó ðóêîâîäèòåëþ ä.ô.ì.í., ïðîôåññîðó Àëåêñàíäðó Îëåãîâè÷ó Èâàíîâó çà ïîñòàíîâêó çàäà÷, ïîìîùü èñîâåòû íà âñåõ ýòàïàõ íàïèñàíèÿ ðàáîòû. Àâòîð áëàãîäàðåí ä.ô.-ì.í., ïðîôåññîðóÀëåêñåþ Àâãóñòèíîâè÷ó Òóæèëèíó çà ïîñòîÿííûé èíòåðåñ, ñîâåòû è ìíîãî÷èñëåííûå îáñóæäåíèÿ.Àâòîð ïðèçíàòåëåí ó÷àñòíèêàì ñåìèíàðà ¾Îïòèìàëüíûå ñåòè¿ çà ïîëåçíûå çàìå÷àíèÿ, êîììåíòàðèè è äèñêóññèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
