Характеристики конечных метрических пространств, порожденных графами, страница 5

. . n íàçûâàþò çàïàñàìè ïîñòàâùèêîâ, bj ïðè j = 1, . . . m çàïðîñàìè ïîòðåáèòåëåé, à ôóíêöèîíàë F öåëåâîé ôóíêöèåé.2.1.2 Îáîáùåíèå òðàíñïîðòíîé çàäà÷è.Ðàññìîòðèì òðàíñïîðòíóþ çàäà÷ó â òåðìèíàõ òåîðèè ãðàôîâ. Ïóñòü (G, ω) âçâåøåííûé ãðàô ñòîèìîñòåé ïåðåâîçîê, ãäå G = (V, E), è ïóñòü d ðàññòîÿíèå, ïîðîæäåííîå âåñîâîé ôóíêöèåé ω . Îïðåäåëèì íà âåðøèíàõ ãðàôà ôóíêöèþðàñïðåäåëåíèÿ m1 , êîòîðàÿ çàäàåò ðàñïðåäåëåíèå åäèíè÷íîé ìàññû ïî âñåì âåðøèíàì ãðàôà G. Äàëåå íàì íåîáõîäèìî ïåðåðàñïðåäåëèòü ìàññó 1 ïî âåðøèíàìãðàôà, ñîãëàñíî ðàñïðåäåëåíèþ m2 . Ïóñòü ôóíêöèÿ d(x, y) îïðåäåëÿåò öåíó ïåðåâîçêè ãðóçà ìàññû 1 èç âåðøèíû x â âåðøèíó y . Òàêèì îáðàçîì, ñòîèìîñòüïåðåìåùåíèÿ ãðóçà âåñà m âäîëü ïóòè xy (èç âñåõ ïóòåé xy âûáèðàåì ïóòü ñíàèìåíüøåé öåíîé) áóäåò ðàâíà m d(x, y).

Îáîçíà÷èì ÷åðåç cij âåñ ãðóçà, ïåðåâîçèìîãî èç âåðøèíû xi â âåðøèíó xj . Òîãäà ñòîèìîñòü ïåðåðàñïðåäåëåíèÿ ãðóçà áóäåò ðàâíà F =∑ ∑ij cijd(xi , xj ). Äàííàÿ òðàíñïîðòíàÿ çàäà÷à ñîñòîèò âòîì, ÷òîáû îïðåäåëèòü ïëàí ïåðåâîçîê cij , ïðè êîòîðîì m1 ïðåâðàòèòñÿ â m2 ,ò.å. m1 (xi ) −∑j cij +∑k ckj= m2 (xi ) è òàêîé, ÷òîáû ñòîèìîñòü ïåðåâîçîê áûëàìèíèìàëüíîé, ò.å. F → min.2.1.3 Äâîéñòâåííàÿ òðàíñïîðòíàÿ çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ.Äëÿ äâîéñòâåííîé òðàíñïîðòíîé çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ èìååòñÿ nïóíêòîâ îòïðàâëåíèÿ è m ïóíêòîâ íàçíà÷åíèÿ.

Îáîçíà÷èì ui ñòîèìîñòü åäèíèöûïðîäóêöèè â i-ì ïóíêòå îòïðàâëåíèÿ, vj còîèìîñòü åäèíèöû ïðîäóêöèè ïîñëåïåðåâîçêè â j -é ïóíêò íàçíà÷åíèÿ. Ïåðåìåííûå ui è vj íàçûâàþò ñîîòâåòñòâåííîïîòåíöèàëàìè ïîñòàâùèêà è ïîòðåáèòåëÿ.Äâîéñòâåííàÿ òðàíñïîðòíàÿ çàäà÷à ñîñòîèò â íàõîæäåíèè íåîòðèöàòåëüíûõ âåëè÷èí ui è vj , îáðàùàþùèõ â ìàêñèìóì öåëåâóþ ôóíêöèþ27G=n∑ai ui +m∑bj vj ,j=1i=1ïðè óñëîâèèui + vj ≤ cij , i = 1, . . . n, j = 1, .

. . m,ãäå ai ïðè i = 1, . . . n çàïàñû ïîñòàâùèêîâ, bj ïðè j = 1, . . . m çàïðîñû ïîòðåáèòåëåé, à cij öåíà ïåðåâîçêè ãðóçà èç i-ãî ïóíêòà â j -é ïóíêò.2.1.4 Îáîáùåííàÿ äâîéñòâåííàÿ òðàíñïîðòíàÿ çàäà÷à è ôóíêöèÿ Âàññåðøòåéíà 1 ïîðÿäêàÄëÿ òðàíñïîðòíîé çàäà÷è, ñôîðìóëèðîâàííîé â ðàçäåëå 2.1.2, ìîæíî ñôîðìóëèðîâàòü äâîéñòâåííóþ ê íåé çàäà÷ó.  êàæäîé âåðøèíå ãðàôà xi îïðåäåëåíàñòîèìîñòü åäèíèöû òîâàðà â íåé f (xi ). Õîòèì íàéòè òàêîå èçìåíåíèå ñòîèìîñòèåäèíèöû òîâàðà, ïîñëå êîòîðîãî ñóììàðíàÿ ñòîèìîñòü òîâàðà â âåðøèíàõ ãðàôàìàêñèìàëüíî óâåëè÷èòñÿ, ò.å.

G =∑x∈Vf (x)(m1 (x) − m2 (x)) → max, íî ïðèýòîì ðàçíîñòü ñòîèìîñòè âûâîçèìîé åäèíèöû ïðîäóêöèè â x è åå ñòîèìîñòè ïîñëåïåðåâîçêè â y íå ïðåâûøàåò öåíó çà òðàíñïîðòèðîâêó: |f (x) − f (y)| ≤ d(x, y).Ïî ïåðâîé òåîðåìå äâîéñòâåííîñòè ìàêñèìàëüíîå çíà÷åíèå îäíîé è ìèíèìàëüíîå çíà÷åíèå äðóãîé ôóíêöèé (ïðÿìîé è äâîéñòâåííîé òðàíñïîðòíîé çàäà÷è) ñîâïàäàþò: F = G (ñì. [16]). Ìàêñèìàëüíîå çíà÷åíèå ôóíêöèè G íàçûâàåòñÿðàññòî-ÿíèåì Âàññåðøòåéíà ïåðâîãî ïîðÿäêà W (m1, m2) ìåæäó äâóìÿ ðàñïðåäåëåíèÿìèâåðîÿòíîñòåé m1 è m2 íà (V, d):W (m1 , m2 ) =∑maxf 1-ëèïøèöåâà ôóíêöèÿ x∈Vf (x)(m1 (x) − m2 (x))(2.1.1)Õîðîøî èçâåñòíî, ÷òî ôóíêöèÿ W (m1 , m2 ) ÿâëÿåòñÿ ìåòðèêîé íà ïðîñòðàíñòâåâåðîÿòíîñòíûõ ìåð ([18]).282.1.5 Êðèâèçíû Ðè÷÷è äëÿ ìåòðè÷åñêèõ ïðîñòðàíñòâ ñî ñëó÷àéíûìáëóæäàíèåì.Äàëåå, áóäåì ðàññìàòðèâàòü ôóíêöèè ðàñïðåäåëåíèÿ mαx : V → [0, 1] ñïåöèàëüíîãîâèäà:mαx (y) =α,åñëè x = y ,1−αdeg(x) ,åñëè x ∼ y ,0,åñëè x y è x ̸= y ,ãäå x ∼ y îáîçíà÷àåò, ÷òî âåðøèíû x è y ñìåæíû.

Ýòè ôóíêöèè áóäåì íàçûâàòüôóíêöèÿìè ñëó÷àéíîãî áëóæäàíèÿ.Ñëåäóÿ ðàáîòàì [12, 14], îïðåäåëèì α-êðèâèçíó Ðè÷÷è ôîðìóëîé kα(x, y) =1 − W (mαx , mαy )/ d(x, y). Ïðè α = 0 âåëè÷èíà k0 (x, y) êðèâèçíà Ðè÷÷è-Îëèâüå.Êðèâèçíîé Ðè÷÷è íàçîâåì ôóíêöèþ:kα (x, y).α→1 1 − αÔóíêöèè mαx è mαy ðàñïðåäåëÿþò âñþ ìàññó â îêðåñòíîñòè òî÷åê x è y . Ïîk(x, y) := limñêîëüêó ìû ðàññìàòðèâàåì ïðåäåë ïðè α → 1, ïîëó÷àåì, ÷òî ïðàêòè÷åñêè âñÿìàññà ñîñðåäîòî÷åíà â öåíòðàëüíûõ òî÷êàõ x è y è ëèøü ìàññà m → 0 íàõîäèòñÿ â ñìåæíûõ ñ öåíòðàìè òî÷êàõ.

Ýòó áåñêîíå÷íî ìàëóþ ìàññó, ðàñïðåäåëåííóþâ îêðåñòíîñòè òî÷êè, íàçîâåì ïîãðåøíîñòüþ. Çàïèøåì âûðàæåíèå äëÿ êðèâèçíûÐè÷÷è ïî-äðóãîìó:k1+(α−1) (x, y) − k1 (x, y)k1 (x, y) − kα (x, y)= lim=α→1α→11−αα−1d=|α=1 kα (x, y).dαÒàêèì îáðàçîì êðèâèçíà Ðè÷÷è íà ãðàôàõ ïîêàçûâàåò êàê ìåíÿåòñÿ îïòèìàëük(x, y) = limíàÿ ñòîèìîñòü ïåðåâîçêè ãðóçà ìàññû 1, ñêîíöåíòðèðîâàííîãî â âåðøèíå, ïðè âîçíèêíîâåíèè ïîãðåøíîñòè.292.2Ïðåäâàðèòåëüíûå ðåçóëüòàòûÒåîðåìà 9. ([12])Äëÿ ëþáûõ äâóõ âåðøèí x, y ãðàôà G = (V, E) ñ ïîñòîÿííîéåäèíè÷íîé âåñîâîé ôóíêöèåé d α-êðèâèçíà Ðè÷÷è îãðàíè÷åíà ñâåðõókα (x, y) ≤ (1 − α)2.d(x, y)Òåîðåìà 10.

([13])Äëÿ ëþáûõ äâóõ âåðøèí x, y ãðàôà G = (V, E) ñ ïîñòîÿííîéåäèíè÷íîé âåñîâîé ôóíêöèåé d êðèâèçíà Ðè÷÷è-Îëèâüå k0(x, y) ≥ d2 + d2 − 2, åñëèdx > 1 è dy > 1; k0 (x, y) = 0, åñëè dx = 1 èëè dy = 1.xyÀíàëîã òåîðåìû Áîííå-Ìàéåðà äëÿ ãðàôîâ:Òåîðåìà 11. ([12])Äëÿ ëþáûõ äâóõ âåðøèí x, y ãðàôà G = (V, E) ñ ïîñòîÿííîéåäèíè÷íîé âåñîâîé ôóíêöèåé d, åñëè k(x, y) > 0, òîãäàd(x, y) ≤2.k(x, y)Åñëè äëÿ ëþáîãî ðåáðà xy ∈ E k(x, y) ≥ c > 0, òîãäà2diam(G) ≤ .c2.3Ôîðìóëà êðèâèçíû Ðè÷÷è äëÿ âçâåøåííîãî äåðåâà(Ðóáëåâà Î.Â., [1.2]) Ïóñòü (G, ω), G = (V, E) âçâåøåííîå äåðåâîñ âåñîâîé ôóíêöèåé ω, à d ðàññòîÿíèå, ïîðîæäåííîå âåñîì ω. Òîãäà êðèâèçíàÐè÷÷è ìåæäó ëþáûìè ðàçëè÷íûìè âåðøèíàìè äåðåâà G âû÷èñëÿåòñÿ ïî ñëåäóþùåé ôîðìóëå:Òåîðåìà 2.)1 ∑1 ( 1 ∑kz · d(z, x) +kz · d(z, y) ,k(x, y) =d(x, y) deg(x) z∼xdeg(y) z∼yãäå kz = 1 , åñëè ðåáðî xz âõîäèò â ïóòü xy, è kz = −1, åñëè íå âõîäèò.30Äîêàçàòåëüñòâî.

Íàéäåìêðèâèçíó Ðè÷÷è ìåæäó âåðøèíàìè x è y . Ïóñòüdeg(x) = m, deg(y) = n. Áåç îãðàíè÷åíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî n ≥ m. Òîãäà îáîçíà÷èì âåðøèíû, ñìåæíûå ñ x, ÷åðåç x1 , x2 , . . . , xm , à âåðøèíû, ñìåæíûå ñy ÷åðåç y1 , y2 , . . . , yn . Áåç îãðàíè÷åíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî x1 è y1 ëåæàòíà åäèíñòâåííîì ïóòè γ , ñîåäèíÿþùåì x è y .

Åñëè γ ñîñòîèò èç îäíîãî ðåáðà, òîïîëîæèì x1 = y è y1 = x, à åñëè èç äâóõ, òî x1 = y1 .Ðàññòîÿíèå òðàíñïîðòèðîâîê ìåæäó ôóíêöèÿìè mαx è mαy â ñäåëàííûõ âûøå îáîçíà÷åíèÿõ èìååò ñëåäóþùèé âèä:Ëåììà 4.W (mαx , mαy )+=[ ()α f (x) − f (y) +supf 1-ëèïøèöåâà ôóíêöèÿ))1 − α(1 − α(f (x1 ) − f (y1 ) + . . . +f (xm ) − f (ym ) +nnmm))]1 − α ∑(1 − α ∑(+f (xi ) − f (ym+1 ) + . . . +f (xi ) − f (yn ) .nm i=1nm i=1.Äîêàçàòåëüñòâî. Ïîñ÷èòàåì ðàññòîÿíèåì ìåæäó ôóíêöèÿìè mαx è mαy:W (mαx , mαy ) =∑supf 1-ëèïøèöåâà ôóíêöèÿ v∈Vf (v)(mαx (v) − mαy (v)) =[1−α1−α=supf (x1 ) + . . . +f (xm )−αf (x) +mmf 1-ëèïøèöåâà ôóíêöèÿ]1−α1−α−αf (y) −f (y1 ) − .

. . −f (yn ) =nn[=supf 1-ëèïøèöåâà ôóíêöèÿ+αf (x) +1−α1−αf (x1 ) + . . . +f (xm )+nn(n − m)(1 − α)(n − m)(1 − α)f (x1 ) + . . . +f (xm )−nmnm31(2.3.1)−αf (y) −1−α1−αf (y1 ) − . . . −f (ym )−nn]1−α1−α−f (ym+1 ) − . . . −f (yn ) =nn=+[α(f (x) − f (y))+supf 1-ëèïøèöåâà ôóíêöèÿ1−α1−α(f (x1 ) − f (y1 )) + . .

. +(f (xm ) − f (ym )))+nn]1−α∑1−α∑+(f (xi ) − f (ym+1 )) + . . . +(f (xi ) − f (yn )) .nm i=1nm i=1mmËåììà äîêàçàíà.Ïîäáåðåì 1-ëèïøèöåâó ôóíêöèþ f òàê, ÷òîáû ìàêñèìèçèðîâàòü âûðàæåíèå(2.3.1). Äëÿ ýòîãî îïðåäåëÿåì 1-ëèïøèöåâó ôóíêöèþ f (x) ñëåäóþùèì îáðàçîì.Ðàçðåæåì èñõîäíîå äåðåâî íà äâà ïîääåðåâà ïî ðåáðó yy1 .

 ðåçóëüòàòå, ìíîæåñòâîâåðøèí V èñõîäíîãî äåðåâà ðàçáèâàåòñÿ íà äâà ïîäìíîæåñòâà. Îáîçíà÷èì ÷åðåçX òî èç íèõ, êîòîðîå ñîäåðæèò âåðøèíó x, à âòîðîå, ñîäåðæàùåå y , îáîçíà÷èì÷åðåç Y . Íà ìíîæåñòâå X îïðåäåëèì ôóíêöèþ f (v) = d(v, y) ðàññòîÿíèå îòïðîèçâîëüíîé âåðøèíû v ∈ X äî âåðøèíû y . Íà ìíîæåñòâå Y îïðåäåëèì ôóíêöèþf òàê, ÷òî äëÿ ëþáîé òî÷êè z ∈ Y èìååì f (z) = − d(z, y).Îïðåäåëåííàÿ íàìè ôóíêöèÿ f ÿâëÿåòñÿ 1-ëèïøèöåâîé, ò.å.

äëÿ ëþáûõ âåðøèí v, z ∈ V , |f (v) − f (z)| ≤ d(v, z).Äîêàçàòåëüñòâî. 1. Ïóñòü ñíà÷àëà v ∈ X , à z ∈ Y , òîãäà |f (v) − f (z)| = d(v, y) +Ëåììà 5.d(y, z) = d(v, z). Ïîñëåäíåå ðàâåíñòâî âûïîëíÿåòñÿ, ò.ê. ìû ðàññìàòðèâàåì äåðåâî,â êîòîðîì ïóòü èç îäíîé âåðøèíû â äðóãóþ åäèíñòâåííûé, è âåðøèíà y ëåæèò íàïóòè èç v â z .2. Ïóñòü v ∈ X , à z ∈ X . Áåç îãðàíè÷åíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî d(v, y) ≥d(z, y). Òîãäà |f (v) − f (z)| = | d(v, y) − d(z, y)| ≤ d(v, z) + d(z, y) − d(z, y) = d(v, z).323. Ïóñòü v ∈ Y è z ∈ Y , òîãäà |f (v) − f (z)| = | − d(v, y) − d(z, y)| = d(v, y) +d(z, y) = d(v, z). Ïîñëåäíåå ðàâåíñòâî âûïîëíÿåòñÿ, ò.ê.

ìû ðàññìàòðèâàåì äåðåâî,â êîòîðîì ïóòü èç îäíîé âåðøèíû â äðóãóþ åäèíñòâåííûé, è âåðøèíà y ëåæèò íàïóòè èç v â z .Ëåììà äîêàçàíà.Ôóíêöèÿ f ìàêñèìèçèðóåò âûðàæåíèå (2.3.1).Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà ëåììû äîñòàòî÷íî ïîêàçàòü, ÷òî âñå ñëàãà-Ëåììà 6.åìûå â (2.3.1) ìàêñèìàëüíû, òî åñòü âûïîëíÿþòñÿ ðàâåíñòâà:f (x) − f (y) = d(x, y),f (xi ) − f (yi ) = d(xi , yj ), i = 1, . . . m,f (xi ) − f (ym+l ) = d(xi , ym+l ), i = 1, .

. . m, l = 1, . . . n − m.Ïåðâîå ðàâåíñòâî íåïîñðåäñòâåííî ñëåäóåò èç îïðåäåëåíèÿ ôóíêöèè f . Ïîëîæèì, ÷òî âåðøèíû x1 è y1 ÿâëÿþòñÿ âíóòðåííèìè âåðøèíàìè ïóòè xy , òîãäà âåðøèíû xi , y1 ∈ X , y, yj ∈ Y äëÿ j ̸= 1. Èç îïðåäåëåíèÿ ôóíêöèè f âòîðîå ðàâåíñòâîäëÿ i = 1 ïåðåïèøåòñÿ òàê: f (x1 ) − f (y1 ) = d(x1 , y) − d(y1 , y) = d(x1 , y1 ), ò.ê. âðàññìàòðèâàåìîì äåðåâå âåðøèíû xi , y1 è y ïîñëåäîâàòåëüíûå âåðøèíû â ïóòè xi y .