Характеристики конечных метрических пространств, порожденных графами (1105193), страница 7
Текст из файла (страница 7)
Ïîñêîëüêó deg l = 3, òî −2/3 = ±(2/3)n.Ñíîâà ïîëó÷àåì n = 1, òî åñòü ýòî âåðøèíû, ñìåæíûå ñ l è èìåþùèå ñòåïåíü 3. íàøåì ñëó÷àå òàêèõ âåðøèí äâå, êîòîðûì ñîîòâåòñòâóþò äâà ðàâíûõ ýëåìåíòà−2/3 â l-îé ñòðîêå ìàòðèöû. Îäèí èç ýòèõ ýëåìåíòîâ ñòîèò â ïîìå÷åííîì ñòîëáöå,ïîñêîëüêó îäíîé èç ñìåæíûõ ñ l âåðøèí ñòåïåíè 3 ÿâëÿåòñÿ m.
Ñëåäîâàòåëüíî,òðåòüÿ ñìåæíàÿ ñ l âåðøèíà l′ óñòàíàâëèâàåòñÿ îäíîçíà÷íî.Åñëè â ñòðîêå ñ íîìåðîì l íàéäóòñÿ òðè ýëåìåíòà −2/3, òî ðåàëèçîâàëñÿ âòîðîé ñëó÷àé.  ýòîì ñëó÷àå â ñòðîêå l îäèí èç ýëåìåíòîâ −2/3 ñòîèò â ïîìå÷åííîìñòîëáöå, à îñòàâøèåñÿ äâà ñîîòâåòñòâóþò êðèâèçíàì ìåæäó âåðøèíîé l è äâóìÿäðóãèìè ñìåæíûìè ñ íåé âåðøèíàìè l1 è l2 ñòåïåíè 3. Ïîýòîìó äåðåâî âîññòàíàâëèâàåòñÿ ñ òî÷íîñòüþ äî ïåðåñòàíîâêè ïîääåðåâüåâ, íà÷èíàþùèõñÿ â âåðøèíàõ l1è l2 .
Ïîìå÷àåì ñòðîêè è ñòîëáöû, â êîòîðûõ ñòîÿò ýëåìåíòû ìàòðèöû ñ íîìåðàìè, ñîäåðæàùèìè îäèí èíäåêñ ñìåæíóþ âåðøèíó ñ l, âòîðîé îäèí èç ðàíååóñòàíîâëåííûõ.39Äàëåå, äëÿ ïîääåðåâüåâ, íà÷èíàþùèõñÿ ñ âåðøèíû ñòåïåíè 3, ñìåæíîé ñ l (âîâòîðîì ñëó÷àå ýòî âåðøèíû l1 è l2 , â òðåòüåì l′ ), ïîâòîðÿåì ðàññóæäåíèÿ íàõîäèì ñìåæíûå âåðøèíû è âû÷åðêèâàåì ýëåìåíòû, ñîîòâåòñòâóþùèå êðèâèçíàììåæäó êàæäîé ñìåæíîé âåðøèíîé è âñåìè ïðåäûäóùèìè âåðøèíàìè. Äåëàåì ýòîäî òåõ ïîð, ïîêà âñå ñòîëáöû è ñòðîêè íå áóäóò ïîìå÷åíû.Ñëåäñòâèå 2 äîêàçàíî.2.5.3 Äîêàçàòåëüñòâî ñëåäñòâèÿ 3.Äîêàçàòåëüñòâî.
Ïîäñòàâèì â îáùóþ ôîðìóëó ñóììû êðèâèçí ∑x∼y:x,y∈V k(x, y)âûðàæåíèå äëÿ êðèâèçíû k(x, y), ïîëó÷åííîå â òåîðåìå 1:∑k(x, y) =x∼y:x,y∈V(d(x, y) − d(x, x1 ) − . . . − d(x, xdeg x−1 )1=+d(x, y)deg xx∼y:x,y∈V)d(x, y) − d(y, y1 ) − . . . − d(y, ydeg y−1 )+.deg y∑Òåïåðü ïåðåãðóïïèðóåì ñëàãàåìûå è ïåðåéäåì îò ñóììèðîâàíèÿ ïî ðåáðàì êñóììèðîâàíèþ ïî âåðøèíàì, ïðè ýòîì ñëàãàåìûå èç âûðàæåíèÿ äëÿ êðèâèçíûïàðû (x, y) ðàñïðåäåëèì ïî äâóì ñóììàì:∑x∼y:x,y∈V−degx−1∑1(∑ ( 11 )k(x, y) =+−deg x deg yxy∈E)degy−1∑d(y, yj )d(x, xi )−.deg x d(x, y)degyd(x,y)1Ðàññìîòðèì âñå âîçìîæíûå êðèâèçíû, â êîòîðûõ åñòü ñëàãàåìûå, çàâèñÿùèå îòâåðøèíû x.
Âñåãî èõ deg(x). Ïðîäîëæàåì ïðåîáðàçîâàíèÿ:∑x∼y:x,y∈Vk(x, y) =∑x∈V401deg x−deg x−∑(∑x∈V xi ,xj ∼x,xi ̸=xjÄëÿ êàæäîãî ñëàãàåìîãî âèäà)1d(x, xi ) d(x, xj )+.deg x d(x, xj ) d(x, xi )d(x,xj )d(x,xi )d(x,xj ) + d(x,xi )ïðèìåíèì îöåíêó a+ a1 ≥ 2. Êàæäîé2âåðøèíå v ñîîòâåòñòâóþò Cdegv ðàçëè÷íûõ êîìáèíàöèé ïàð ðåáåð, ñìåæíûõ ñ ýòîéâåðøèíîé. Ñëåäîâàòåëüíî, êîëè÷åñòâî ñëàãàåìûõ âèäà a +1a2ðàâíî Cdegv . Òàêèìîáðàçîì, èìååì:∑k(x, y) ≤ vol(G) − 2x∼y:x,y∈V2Cdegx =∑2∑ Cdegxx∈Vdeg x,deg x(deg x − 1),2k(x, y) ≤ vol(G) −x∼y:x,y∈V∑ deg x(deg x − 1) 12≤2deg xx∈V≤ vol(G) −∑∑(deg x − 1) = 2 vol(G) −deg x.x∈VÄëÿ ãðàôîâ âûïîëíÿåòñÿ ðàâåíñòâî:∑x∈Vx∈Vdeg x = 2|E|, ãäå |E| êîëè÷åñòâîðåáåð.
Äëÿ äåðåâüåâ èìååì:∑deg x = 2|E| = 2(vol(G) − 1)x∈V.Èç ýòîãî ðàâåíñòâà èìååì:∑k(x, y) ≤ 2 vol(G) − 2(vol(G) − 1) ≤ 2x∼y:x,y∈VÑëåäñòâèå 3 äîêàçàíî.412.6Îöåíêà êðèâèçíû Ðè÷÷èÄëÿ ôîðìóëèðîâêè îñíîâíîé òåîðåìû äàííîãî ðàçäåëà ââåäåì íîâîå îáîçíà÷åíèå:U (x) :=1deg(x)∑∗z∼x kz ·d(z, x),ãäå kz∗ = +1, åñëè d(z, x) = minv∼x d(x, v), è kz∗ = −1äëÿ îñòàëüíûõ v ∼ x.  ÷àñòíîñòè, åñëè deg(x) = 1, U (x) = d(x, x′ ), ãäå x ∼ x′ .(Ðóáëåâà Î.Â., [1.3]) Ïóñòü G = (V, E) ïðîèçâîëüíîå äåðåâî,ω âåñîâàÿ ôóíêöèÿ, d ôóíêöèÿ, èçìåðÿþùàÿ âåñ ïóòè ìåæäó âåðøèíàìèäåðåâà. Òîãäà êðèâèçíó Ðè÷÷è íà ëþáîé ïàðå âåðøèí äåðåâà G, íå ÿâëÿþùåãîñÿîòðåçêîì, ìîæíî îöåíèòü ñâåðõó è ñíèçó òàê:Òåîðåìà 12.())11 (2 min(U (v)) ≤2 min(U (v)) ≤ k(x, y) ≤ 1,diam(G) v∈Vd(x, y) v∈Vïðè÷åì ýòè îöåíêè ÿâëÿþòñÿ òî÷íûìè.Äëÿ äåðåâà G, ÿâëÿþùåãîñÿ îòðåçêîì xy, êðèâèçíà k(x, y) = 2.Äîêàçàòåëüñòâî. Ðàññìîòðèì ñíà÷àëà ÷àñòíûé ñëó÷àé äåðåâà îòðåçîê xy.
Âýòîì ñëó÷àå ïðèìåíèì ôîðìóëó äëÿ ãðóáîé êðèâèçíû Ðè÷÷è (êîýôôèöèåíòû kzèç îïðåäåëåíèÿ âûøå):)1 ( 1 ∑1 ∑k(x, y) =kz · d(z, x) +kz · d(z, y) ,d(x, y) deg(x) z∼xdeg(y) z∼y äàííîì ïðèìåðå deg(x) = deg(y) = 1, kx = ky = +1, ïîëó÷àåì:k(x, y) =Îöåíêà ñâåðõó.)1 (d(x, y) + d(y, x) = 2d(x, y)Äîêàæåì, ÷òî k(x, y) ≤ 1 äëÿ ëþáûõ äâóõ âåðøèí x, y ∈ V .Ðàññìîòðèì îáùóþ ôîðìóëó:)1 ( 1 ∑1 ∑k(x, y) =kz · d(z, x) +kz · d(z, y) ,d(x, y) deg(x) z∼xdeg(y) z∼y∑1Ðàññìîòðèì ñëàãàåìîå deg(x)z∼x kz · d(z, x).
Çàìåòèì, ÷òî â ýòîé ñóììå âñåñëàãàåìûå, êðîìå îäíîãî, îòðèöàòåëüíûå, ïîýòîìó âñå ñëàãàåìîå ïðèíèìàåò íàèáîëüøåå çíà÷åíèå, êîãäà çíàìåíàòåëü deg(x) íàèìåíüøèé èç âñåõ âîçìîæíûõ, ò.å.42deg(x) = 1, è, ñîîòâåòñòâåííî, â ÷èñëèòåëå ñòîèò åäèíñòâåííîå ïîëîæèòåëüíîåñëàãàåìîå, ò.å.)1 (k(x, y) ≤d(z1 , x) + d(z2 , y)d(x, y)Òî÷êè z1 è z2 ëåæàò íà ïóòè xy è ÿâëÿþòñÿ ñìåæíûìè ñ òî÷êàìè, ñîîòâåòñòâåííî, x è y , ïîýòîìó ñïðàâåäëèâî íåðàâåíñòâî: d(x, y) ≥ d(x, z1 ) + d(z2 , y), ïðè÷åìðàâåíñòâî äîñòèãàåòñÿ, êîãäà z1 = z2 è x, z1 , y ïîñëåäîâàòåëüíûå òî÷êè ïóòè xy .Ïîýòîìó èìååì:k(x, y) ≤Îöåíêà ñíèçó.1diam(G)(d(x, y)≤ 1.d(x, y)Äîêàæåì,÷òî â ñäåëàííûõ âûøå îáîçíà÷åíèÿõ k(x, y) ≥)2 minv∈V (U (v)) .Ðàññìîòðèì ñíîâà îáùóþ ôîðìóëó äëÿ êðèâèçíû Ðè÷÷è:)1 ( 1 ∑1 ∑k(x, y) =kz · d(z, x) +kz · d(z, y) .d(x, y) deg(x) z∼xdeg(y) z∼yÈç îïðåäåëåíèÿ ôóíêöèè U (x) ñïðàâåäëèâà ñëåäóþùàÿ îöåíêà: U (x) ≤1deg(x)∑z∼x kz· d(x, y).
Ïîñòàâèì åå â öåïî÷êó íåðàâåíñòâ:))1 (1 (k(x, y) ≥U (x) + U (y) ≥2 min(U (x), U (y)) ≥d(x, y)d(x, y))()1 (12 min(U (v)) ≥2 min(U (v)) .d(x, y) v∈Vdiam(G) v∈VÒî÷íîñòü îöåíîê.Ïóñòü( G äåðåâî )ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé. Îöåíêà ñíèçó d(x, y) ≥1diam(G) 2 minv∈V (U (v)) äîñòèãàåòñÿ è ñîâïàäàåò ñ ôîðìóëîé èç òåîðåìû 1 äëÿâåðøèí äåðåâà G ñòåïåíè 1, ðàññòîÿíèå ìåæäó êîòîðûìè ðàâíî diam(G).
Îöåíêàñâåðõó k(x, y) ≤ 1 äîñòèãàåòñÿ è ñîâïàäàåò ñ îöåíêîé èç òåîðåìû 1 äëÿ âåðøèí èçóñîâ âçâåøåííûõ äåðåâüåâ ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé, ðàâíîé 1 íà êàæäîìðåáðå.43Òåîðåìà äîêàçàíà.44Çàêëþ÷åíèå ýòîì ðàçäåëå ìû åùå ðàç ïåðå÷èñëèì îñíîâíûå ðåçóëüòàòû ðàáîòû è âîçìîæíûåäàëüíåéøèå ïóòè èññëåäîâàíèÿ. ãëàâå 1 áûë äîêàçàí êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà, òî åñòü óñòàíîâëåíà ñâÿçü ìåæäó ìèíèìàëüíûìè çàïîëíåíèÿìè êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ è ñâîéñòâîì àääèòèâíîñòè. ãëàâå 2 ïîëó÷åíà ÿâíàÿ ôîðìóëà äëÿ âû÷èñëåíèÿ êðèâèçíû Ðè÷÷è äëÿ ñëó÷àÿ âçâåøåííûõ äåðåâüåâ.  êà÷åñòâå ñëåäñòâèé èç ýòîé ôîðìóëû óñòàíîâëåíî, ÷òîäëÿ áèíàðíûõ äåðåâüåâ ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé ñòðóêòóðà äåðåâà ïîëíîñòüþ îïðåäåëÿåòñÿ ìàòðèöåé ïîïàðíûõ êðèâèçí Ðè÷÷è ìåæäó âåðøèíàìè ýòîãîäåðåâà.
Òàêæå ïîëó÷åíû òî÷íûå íèæíÿÿ è âåðõíÿÿ îöåíêè êðèâèçíû Ðè÷÷è äëÿïðîèçâîëüíîãî âçâåøåííîãî äåðåâà.Ïåðå÷èñëèì íåñêîëüêî âîçìîæíûõ íàïðàâëåíèé äàëüíåéøåãî èññëåäîâàíèÿ èçàäà÷, êîòîðûå õîòåëîñü áû ðåøèòü:1. Äàëüíåéøåå èçó÷åíèå ñâîéñòâ êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ â òåðìèíàõ ïîëóïåðèìåòðà.2. Îáîáùåíèå äàííîé ôîðìóëû íà ïðîèçâîëüíûå âçâåøåííûå ãðàôû.3.
Ïðèìåíåíèå êðèâèçíû Ðè÷÷è ê ðåøåíèþ òðàíñïîðòíûõ çàäà÷ ñ íîâûìè ôóíêöèÿìè ñëó÷àéíûõ áëóæäàíèé.4. Âîçìîæíî ëè óñòàíîâèòü ñâÿçü ìåæäó òîïîëîãèåé ïðîèçâîëüíîãî âçâåøåííîãî äåðåâà è ìàòðèöåé ïîïàðíûõ êðèâèçí Ðè÷÷è ìåæäó âåðøèíàìè ýòîãî äåðåâà?5.
Âîçìîæíî ëè óñòàíîâèòü ñâÿçü ìåæäó òîïîëîãèåé ïðîèçâîëüíîãî âçâåøåííîãî ãðàôà è ìàòðèöåé ïîïàðíûõ êðèâèçí Ðè÷÷è ìåæäó âåðøèíàìè ýòîãî ãðàôà?6. Ñóùåñòâóåò ëè ïðåäåë ìèíèìàëüíûõ çàïîëíåíèé ε-ñåòåé â ìåòðèêå ÃðîìîâàÕàóñäîðôà è, åñëè äà, òî êàê îí ñâÿçàí ñ ìèíèìàëüíûì çàïîëíåíèåì ìíîãî45îáðàçèÿ è/èëè ñàìèì ìíîãîîáðàçèåì?7. Èìåþò ëè êðèâèçíû çàïîëíåíèé ïðåäåë â íåêîòîðîì ðàçóìíîì ñìûñëå, è êàêýòîò ïðåäåë ñâÿçàí ñ êðèâèçíîé Ðè÷÷è ðèìàíîâà ìíîãîîáðàçèÿ èëè åãî çàïîëíåíèÿâ ñìûñëå Ãðîìîâà?46Ñïèñîê ïóáëèêàöèé ïî òåìå äèññåðòàöèè[1.1] Ðóáëåâà Î.Êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàí-ñòâà // Âåñò.
Ìîñê. óí-òà, Ìàòåì. Ìåõàí. 2012, 2, 8-11.[1.2] Ðóáëåâà Î. Êðèâèçíà Ðè÷÷è âçâåøåííûõ äåðåâüåâ // Âåñò. Ìîñê. óí-òà,Ìàòåì. Ìåõàí. 2015, 6, 52-54.[1.3] Ðóáëåâà Î.Îöåíêà êðèâèçíà Ðè÷÷è âçâåøåííîãî äåðåâà // Âåñò. Ìîñê.óí-òà, Ìàòåì. Ìåõàí. 2016, 3, 51-53.[1.4] Ðóáëåâà Î.Êðèâèçíà Ðè÷÷è âçâåøåííîãî äåðåâà// Ìàòåìàò. çàìåòêè2016, 100(4), 586-596.Êðèòåðèé àääèòèâíîñòè êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâè ìèíèìàëüíûå çàïîëíåíèÿ // Ìàòåðèàëû ìåæäóíàðîäíîé êîíôåðåíöèè ¾Âîðî[1.5] Ðóáëåâà Î.íåæñêàÿ çèìíÿÿ ìàòåìàòè÷åñêàÿ øêîëà Ñ.Ã. Êðåéíà 2012¿, 189-190.Êðèâèçíà Ðè÷÷è íà ãðàôàõ. Ôîðìóëà êðèâèçíû Ðè÷÷è äëÿâçâåøåííûõ äåðåâüåâ // Ìàòåðèàëû ìåæäóíàðîäíîé êîíôåðåíöèè ¾Âîðîíåæñêàÿ[1.6] Ðóáëåâà Î.çèìíÿÿ ìàòåìàòè÷åñêàÿ øêîëà Ñ.Ã. Êðåéíà 2014¿, 272-273.[1.7] Ðóáëåâà Î.Îöåíêà êðèâèçíû Ðè÷÷è âçâåøåííîãî äåðåâà // Ìàòåðèàëûìåæäóíàðîäíîé êîíôåðåíöèè ¾Ëîìîíîñîâ 2016¿.[1.8] Ðóáëåâà Î.Êðèâèçíà Ðè÷÷è âçâåøåííîãî äåðåâà // Ìàòåðèàëû ìåæäóíà-ðîäíîé êîíôåðåíöèè ¾Ëîìîíîñîâ 2015¿.Êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà è ìèíèìàëüíûå çàïîëíåíèÿ // Ìàòåðèàëû ìåæäóíàðîäíîé êîíôåðåíöèè[1.9] Ðóáëåâà Î.¾Ëîìîíîñîâ 2011¿.Êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà è ìèíèìàëüíûå çàïîëíåíèÿ // Ìàòåðèàëû ìåæäóíàðîäíîé êîíôåðåíöèè[1.10] Ðóáëåâà Î.¾Àëåêñàíäðîâñêèå ÷òåíèÿ 2012¿.47[1.11] Ðóáëåâà Î.Îöåíêà êðèâèçíû Ðè÷÷è âçâåøåííîãî äåðåâà // Ìàòåðèàëûìåæäóíàðîäíîé êîíôåðåíöèè ¾Àëåêñàíäðîâñêèå ÷òåíèÿ 2016¿.48Ëèòåðàòóðà[1] À.
Î. Èâàíîâ, À. À. Òóæèëèí,Îäíîìåðíàÿ ïðîáëåìà Ãðîìîâà î ìèíèìàëüíîìçàïîëíåíèè, Ìàòåìàò. ñáîðíèê (2011).[2] Ferma P. 1643 ED H Tannery, ed "Oeuveres", vol.1, Paris 1891.[3] G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli, vol. 1, ññ. 79-97.[4] V. Jarnik, O. Kossler (1934), O minimalnich grafech obsahujicich n danych bodu,Cas, Pestovani Mat. (Essen) Ò. 63: 223-235.[5] Ê. À. Çàðåöêèé,Ïîñòðîåíèå äåðåâà ïî íàáîðó ðàññòîÿíèé ìåæäó âèñÿ÷èìèâåðøèíàìè, ÓÌÍ, 20 (6), ññ.
9092 (1965).[6] J. M. S. Simoes-Pereira, A note on the tree realizability of a distance matrix, J.Combinatorial Th., 6, pp. 303310 (1969).[7] M. Gromov,Filling Riemannian manifolds // J. Di. Geom., 18 (1), pp. 1147(1983).[8] À. Î. Èâàíîâ, À. À. Òóæèëèí,Òåîðèÿ ýêñòðåìàëüíûõ ñåòåé //Ìîñêâà,Èæåâñê, Èíñòèòóò êîìïüþòåðíûõ èññëåäîâàíèé (2003).[9] M. M. Deza, E. Deza,Encyclopedia of Distances // Berlin, Heidelberg, Springer-Verlag, (2009).[10] Bakry D., Emery M.,1123, 177-206.[11] Ollivier Y.,Diusions hypercontractives // Lect. Notes Math., 1985,Ricci curvature of Markov chains on metric spaces // J.Funct.Anal.2009, 256(3), 810-864.49[12] Lin Y., Lu L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
