Характеристики конечных метрических пространств, порожденных графами (1105193), страница 4
Текст из файла (страница 4)
Åñëè æåïðîñòðàíñòâî M ìåòðè÷åñêîå, òî äëÿ íåãî ñóùåñòâóåò òàê æå ìèíèìàëüíîå çàïîëíåíèå, ÿâëÿþùååñÿ äåðåâîì ñ íåíóëåâîé âåñîâîé ôóíêöèåé. Îáðàòíî, åñëè äëÿ M ñóùåñòâóåò íåâûðîæäåííîå ìèíèìàëüíîå çàïîëíåíèå, òî M ìåòðè÷åñêîå ïðîñòðàíñòâî.Äëÿ ëþáîãî êîíå÷íîãî ïîäìíîæåñòâà M ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâàñóùåñòâóåò ñîåäèíÿþùåå M êðàò÷àéøåå áèíàðíîå äåðåâî. Åñëè ðàññòîÿíèÿìåæäó ðàçëè÷íûìè òî÷êàìè èç M îòëè÷íû îò íóëÿ, òî ñóùåñòâóåò ñîåäèíÿþùåå M êðàò÷àéøåå íåâûðîæäåííîå äåðåâî. Îáðàòíî, åñëè äëÿ M ñóùåñòâóåòíåâûðîæäåííîå êðàò÷àéøåå äåðåâî, òî ðàññòîÿíèå ìåæäó ðàçëè÷íûìè òî÷êàìèèç M îòëè÷íî îò íóëÿ.Òåîðåìà 6.Ýòà òåîðåìà îáúÿñíÿåò ñëåäóþùåå ñîãëàøåíèå, ïðèíÿòîå â â [1], êîòîðîìó ìûòàêæå áóäåì ñëåäîâàòü.Ïðè èçó÷åíèè ìèíèìàëüíûõ çàïîëíåíèé âñåãäà ìîæíî îãðàíè÷èòüñÿ ðàññìîòðåíèåì äåðåâüåâ, ó êîòîðûõ âñå âåðøèíû ñòåïåíè 1 è 2 ïðèíàäëåæàò ãðàíèöå.20 äàëüíåéøåì, åñëè íå îãîâîðåíî ïðîòèâíîå, ìû âñåãäà áóäåì ïðåäïîëàãàòü, ÷òîýòè óñëîâèÿ âûïîëíåíû.1.4Ïåðèìåòðû ìåòðè÷åñêèõ ïðîñòðàíñòâ.
Îïðåäåëåíèÿ, ïðèìåðû, ñâîéñòâà1.4.1 ÎïðåäåëåíèÿÏóñòü G = (V, E) ïðîèçâîëüíîå äåðåâî ñ íåêîòîðîé ãðàíèöåé M . Íàïîìíèì,÷òî â ñèëó ñäåëàííîãî ñîãëàøåíèÿ, M ñîäåðæèò âñå âåðøèíû äåðåâà G ñòåïåíè 1è 2. Âûáðîñèì èç G íåêîòîðîå ðåáðî e, è ïóñòü G1 è G2 ñâÿçíûå êîìïîíåíòûïîëó÷åííîãî ëåñà. Ïîëîæèì Mi = M ∩ Gi . Ëåãêî ïðîâåðèòü, ÷òî ìíîæåñòâà Mi íåïóñòû. Ïîëó÷åííîå ðàçáèåíèå {M1 , M2 } ìíîæåñòâà M îáîçíà÷èì ÷åðåç PG (e).Îïðåäåëåíèå.
Ïóñòü S ìíîæåñòâî, ñîäåðæàùåå k ýëåìåíòîâ. Íàçîâåìöèê-ëè÷åñêèì ïîðÿäêîì íà ìíîæåñòâå S ïðîèçâîëüíóþ öèêëè÷åñêóþ ïåðåñòàíîâêóπ : S → S . Äâà ýëåìåíòà èç S íàçîâåì ñîñåäíèìè â ñìûñëå öèêëè÷åñêîãî ïîðÿäêàπ , åñëè îäèí èç íèõ ÿâëÿåòñÿ π -îáðàçîì äðóãîãî.
Íóìåðàöèþ (s1 , . . . , sk ) ýëåìåíòîâ èç S íàçîâåìñîãëàñîâàííîéñ öèêëè÷åñêèì ïîðÿäêîì π , åñëè π(si ) = si+1äëÿ êàæäîãî i, i < k . ßñíî, ÷òî íóìåðàöèÿ (s1 , . . . , sk ), k = |S|, ñîãëàñîâàíà ñöèêëè÷åñêèì ïîðÿäêîì π , åñëè è òîëüêî åñëè si+1 = π i (s1 ) äëÿ âñåõ i, i < k . Äëÿêàæäîãî öèêëè÷åñêîãî ïîðÿäêà íà ìíîæåñòâå S ñóùåñòâóåò k ñîãëàñîâàííûõ ñ íèìíóìåðàöèé.Îïðåäåëåíèå. Öèêëè÷åñêèé ïîðÿäîê π íà ãðàíèöå M äåðåâà G íàçîâåì ïëàíàð-íûì ïî îòíîøåíèþ ê G èëè îáõîäîì G, åñëè äëÿ êàæäîãî e ∈ E è Mi ∈ PG(e)ñóùåñòâóåò åäèíñòâåííàÿ âåðøèíà p ∈ Mi , äëÿ êîòîðîé π(p) ̸∈ Mi . Ïîñëåäíååîçíà÷àåò, ÷òî èìååòñÿ òàêàÿ íóìåðàöèÿ ìíîæåñòâà M , ñîãëàñîâàííàÿ ñ π , ÷òî âíåé ýëåìåíòû ìíîæåñòâà M1 ïðåäøåñòâóþò ýëåìåíòàì ìíîæåñòâà M2 .Ïðèâåäåì ýêâèâàëåíòíîå, ñì.
[1], îïðåäåëåíèå ïëàíàðíîãî ïîðÿäêà íà M â òåðìèíàõ óêëàäîê. Ïóñòü G′ íåêîòîðàÿ óêëàäêà (âëîæåíèå) äåðåâà G íà ïëîñêîñòü.21Ðàññìîòðèì îáõîä âîêðóã äåðåâà G′ . Èçîáðàçèì ïîñëåäîâàòåëüíî âñòðå÷àþùèåñÿïðè òàêîì îáõîäå òî÷êè, ñîîòâåòñòâóþùèå âåðøèíàì èç M , ïîñëåäîâàòåëüíûìèòî÷êàìè íà îðèåíòèðîâàííîé îêðóæíîñòè S 1 . Îòìåòèì, ÷òî êàæäàÿ âåðøèíà p èçM âñòðå÷àåòñÿ deg p ðàç, ãäå deg p ñòåïåíü âåðøèíû p. Äëÿ êàæäîé âåðøèíûp ∈ M ñòåïåíè áîëüøå 1, èç âñåõ ñîîòâåòñòâóþùèõ åé òî÷åê îêðóæíîñòè îñòàâèìîäíó ïðîèçâîëüíóþ. Òåì ñàìûì, ìû ïîñòðîèëè èíúåêöèþ ν : M → S 1 .
Îïðåäåëèì öèêëè÷åñêóþ ïåðåñòàíîâêó π , ïîëîæèâ π(p) = q , ãäå ν(q) ñëåäóåò çà ν(p)íà îêðóæíîñòè S 1 . Áóäåì ãîâîðèòü, ÷òî ïîñòðîåííûé öèêëè÷åñêèé ïîðÿäîê πðîæäåí óêëàäêîé G′. ßñíî, ÷òî óêëàäêà G′ ïîðîæäàåò 2∏p∈Mïî-deg p öèêëè÷åñêèõïîðÿäêîâ.Îïðåäåëåíèå. Ïóñòü M = (M, ρ) êîíå÷íîå ïñåâäîìåòðè÷åñêîå ïðîñòðàíñòâî,è π ïðîèçâîëüíûé öèêëè÷åñêèé ïîðÿäîê íà M .ïî îòíîøåíèþ ê ïîðÿäêó π íàçîâåì âåëè÷èíóP (M, π) =Ïåðèìåòðîì ïðîñòðàíñòâà M∑ ()ρ p, π(p) ,p∈Mà minπ P (M, π), ãäå ìèíèìóì áåðåòñÿ ïî âñåâîçìîæíûì öèêëè÷åñêèì ïîðÿäêàìïåðèìåòðîì ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà M è îáîçíà÷èì÷åðåç P (M). Ïîëóïåðèìåòðîì ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà M ïî îòíîøåíèþ ê ïîðÿäêó π íàçîâåì âåëè÷èíó p(M, π) = 21 P (M, π).π íà M , íàçîâåìÊðîìå òîãî, â äàëüíåéøåì íàì ïîíàäîáèòñÿ ñëåäóþùåå îáîçíà÷åíèå. ÅñëèG = (G, ω) íåêîòîðîå âçâåøåííîå äåðåâî, ñîåäèíÿþùèé òî÷êè êîíå÷íîãî ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà M = (M, ρ), òî ìíîæåñòâî âñåõ öèêëè÷åñêèõ ïîðÿäêîâíà M , ïëàíàðíûõ ïî îòíîøåíèþ ê äåðåâó G, ò.å.
âñåõ îáõîäîâ G, áóäåì îáîçíà÷àòü÷åðåç O(G) èëè ÷åðåç O(G). Áóäåì òàêæå ãîâîðèòü, ÷òî êàæäûé òàêîé ïëàíàðíûéïîðÿäîê îïðåäåëåí íà M.1.4.2 ÏðèìåðûÐàññìîòðèì â êà÷åñòâå ìåòðè÷åñêîãî ïðîñòðàíñòâà M âåðøèíû êâàäðàòà x1 , x2 ,x3 è x4 ñî ñòîðîíîé 1 íà åâêëèäîâîé ïëîñêîñòè(ðàññòîÿíèå ìåæäó äèàãîíàëüíûìè22òî÷êàìè ðàâíî√2). Íóìåðàöèÿ âåðøèí ïî ÷àñîâîé ñòðåëêå, íà÷èíàÿ ñ ëåâîé âåðõ-íåé âåðøèíû. Çàäàäèì ïåðâûé îáõîä ïî ïîðÿäêó, ñîãëàñíî çàäàííîé íóìåðàöèèâåðøèí.  ýòîì ñëó÷àå ïåðèìåòð ñ÷èòàåòñÿ òàê:P (M, π1 ) = ρ(x1 , x2 ) + ρ(x2 , x3 ) + ρ(x3 , x4 ) + ρ(x4 , x1 ) == 1 + 1 + 1 + 1 = 4.Ìîæíî çàäàòü äðóãîé îáõîä íà ìíîæåñòâå M ñëåäóþùèì îáðàçîì: π2 : x1 →x3 → x2 → x4 .
 ýòîì ñëó÷àå ïåðèìåòð ïðîñòðàíñòâà ñ÷èòàåòñÿ ñëåäóþùèì îáðàçîì:P (M, π2 ) = ρ(x1 , x3 ) + ρ(x3 , x2 ) + ρ(x2 , x4 ) + ρ(x4 , x1 ) =√√√= 2+1+ 2+1=2+2 2Îòñþäà íàéäåì ïåðèìåòð äàííîãî ìåòðè÷åñêîãî ïðîñòðàíñòâàP (M) = min P (M, π) = 4.πÏî óòâåðæäåíèþ 1 âåñ ìèíèìàëüíîãî çàïîëíåíèÿ ïðîñòðàíñòâà M ðàâåí1(ω(G) =min(ρ(x1 , x2 ) + ρ(x3 , x4 ), ρ(x1 , x3 ) + ρ(x2 , x4 ),2ρ(x1 , x4 ) + ρ(x3 , x2 )) + max(ρ(x1 , x2 ) + ρ(x3 , x4 ),)√ρ(x1 , x3 ) + ρ(x2 , x4 ), ρ(x1 , x4 ) + ρ(x3 , x2 )) = 1 + 2.Òàê êàê âåñ ìèíèìàëüíîãî çàïîëíåíèÿ ìåòðè÷åñêîãî ïðîñòðàíñòâà íå ðàâåí åãîïîëóïåðèìåòðó, òî ýòî ïðîñòðàíñòâî íå ÿâëÿåòñÿ àääèòèâíûì (Òåîðåìà 7).1.4.3 ÑâîéñòâàÏóñòü G = (G, ω) âçâåøåííîå äåðåâî ñ ãðàíèöåé M , è π ïðîèçâîëüíûé öèêëè÷åñêèé ïîðÿäîê íà M . ÒîãäàÒåîðåìà 7 ([1], óòâåðæäåíèå 7.2).∑()dω p, π(p) ≥ 2ω(G).p∈M23Áîëåå òîãî, ðàâåíñòâî äîñòèãàåòñÿ, åñëè è òîëüêî åñëè π íåêîòîðûé ïëàíàðíûé ïîðÿäîê ïî îòíîøåíèþ ê G.Òåîðåìà 8 ([1], ñëåäñòâèå 7.1).
Ïóñòü G = (G, ω) ïðîèçâîëüíîå çàïîëíåíèåïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà M, è π íåêîòîðûé ïëàíàðíûé ïîðÿäîê èçO(G). Òîãäà ω(G) ≥ p(M, π).1.5Êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâàÎñíîâíûì ðåçóëüòàòîì ïåðâîé ãëàâû ÿâëÿåòñÿ ñëåäóþùèé êðèòåðèé àääèòèâíîñòè.(Ðóáë¼âà Î.Â., [1.1]) Âåñ ìèíèìàëüíîãî çàïîëíåíèÿ ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà ðàâåí ïîëóïåðèìåòðó ýòîãî ïðîñòðàíñòâà òîãäà è òîëüêîòîãäà, êîãäà ïðîñòðàíñòâî àääèòèâíî.Òåîðåìà 1.Äëÿ äîêàçàòåëüñòâà êðèòåðèÿ ïîíàäîáèòñÿ íåñêîëüêî âñïîìîãàòåëüíûõ ëåìì.Ïóñòü G = (G, ω) ìèíèìàëüíîå çàïîëíåíèå ïñåâäîìåòðè÷åñêîãîïðîñòðàíñòâà M.
Ïðåäïîëîæèì, ÷òî âåñ ìèíèìàëüíîãî çàïîëíåíèÿ ðàâåí ïîëóïåðèìåòðó äàííîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà, ò.å. p(M) = ω(G). Òîãäàp(π, M) = p(M) äëÿ ëþáîãî ïëàíàðíîãî ïîðÿäêà π ∈ O(G).Äîêàçàòåëüñòâî. Ïî òåîðåìå 6 äëÿ ïðîèçâîëüíîãî ïëàíàðíîãî ïîðÿäêà π ∈ O(G)Ëåììà 1.âûïîëíÿåòñÿ íåðàâåíñòâî p(π, M) ≤ ω(G). Ñëåäîâàòåëüíî, òàê êàê p(M) íàèìåíüøèé ïîëóïåðèìåòð, èìååì p(M) ≤ p(π, M) ≤ ω(G).
Íî ïî óñëîâèþ ëåììûp(M) = ω(G), îòêóäà p(π, M) = p(M), ÷òî è òðåáîâàëîñü äîêàçàòü. ìèíèìàëüíîå çàïîëíåíèå ìåòðè÷åñêîãî ïðîñòðàíñòâà M = (M, ρ). Ïðåäïîëîæèì, ÷òî p(M) = ω(G). Ïóñòü π ∈ O(G) ïðîèçâîëüíûé ïëàíàðíûé ïîðÿäîê. Òîãäà âñå ãðàíè÷íûå ïóòè, ñîåäèíÿþùèåñîñåäíèå îòíîñèòåëüíî ïîðÿäêà π âåðøèíû, òî÷íû.Ëåììà 2.ÏóñòüG = (G, ω)24Äîêàçàòåëüñòâî. Ïî òåîðåìå7 èìååò ìåñòî ðàâåíñòâî2ω(G) = ñèëó ëåììû 1,∑dω (p, π(p)).p∈M∑p∈Mρ(p, π(pi )) = P (π, M) = P (M). Ïî îïðåäåëåíèþ çàïîëíå-íèÿ dω ≥ ρ, ñëåäîâàòåëüíî2ω(G) =∑dω (p, π(p)) ≥p∈M∑ρ(p, π(pi )) = P (M).p∈MÒàê êàê ïî óñëîâèþ 2ω(G) = P (M), òî âñå íåðàâåíñòâà âûïîëíåíû â ôîðìå ðàâåíñòâ, à èìåííî, ρ(p, π(p)) = dω (p, π(p)) äëÿ âñåõ p, ò.å.
âñå ïóòè êîòîðûå, ñîåäèíÿþò âåðøèíû p è π(p) òî÷íûå. Ëåììà äîêàçàíà.Ëåììà 3. Ïóñòü G äåðåâî ñ ãðàíèöåé M . Ëþáûå äâå ãðàíè÷íûå âåðøèíû äåðåâàÿâëÿþòñÿ ñîñåäíèìè îòíîñèòåëüíî íåêîòîðîãî ïëàíàðíîãî ïîðÿäêà èç O(G).Äîêàçàòåëüñòâî. Ïóñòü p, q ∈ M . ßñíî, ÷òî ñóùåñòâóåò òàêîå âëîæåíèå G′ äåðåGâà G â ïëîñêîñòü, ÷òî ãðàíè÷íûé ïóòü, ñîåäèíÿþùèé p è q ïåðåõîäèò â îòðåçîêíåêîòîðîé ïðÿìîé ℓ, à âñå îñòàëüíîå äåðåâî ðàñïîëîæåíî â îäíîé ïîëóïëîñêîñòè,îãðàíè÷åííîé ℓ. Òîãäà ïðè îáõîäå ïëîñêîãî äåðåâà G′ âåðøèíû p è q áóäóò ñîñåäíèìè.
Ëåììà äîêàçàíà.Äîêàçàòåëüñòâî òåîðåìû.  [1, ñëåäñòâèå 8.5], äîêàçàíî, ÷òî åñëè ìåòðè÷åñêîåïðîñòðàíñòâî àääèòèâíî, òî äëèíà ìèíèìàëüíîãî çàïîëíåíèÿ ýòîãî ïðîñòðàíñòâàðàâíà åãî ïîëóïåðèìåòðó. Äîêàæåì îáðàòíîå. Ïóñòü âåñ ìèíèìàëüíîãî çàïîëíåíèÿG = (G, ω) ðàâåí ïîëóïåðèìåòðó ïðîñòðàíñòâà M = (M, ρ). Âîçüìåì ëþáûå äâåòî÷êè p è q èç M , è ïóñòü π ∈ O(G) íåêîòîðûé ïëàíàðíûé ïîðÿäîê, â êîòîðîìp è q ÿâëÿþòñÿ ñîñåäíèìè (òàêîé ïîðÿäîê ñóùåñòâóåò â ñèëó ëåììû 3). Òîãäà èçëåììû 2 âûòåêàåò òî÷íîñòü ãðàíè÷íîãî ïóòè â G , ñîåäèíÿþùåãî p è q , ïîýòîìódω (p, q) = ρ(p, q).
 ñèëó ïðîèçâîëüíîñòè âûáîðà òî÷åê p è q èç M äåðåâî Gÿâëÿåòñÿ ïîðîæäàþùèì äëÿ M, ÷òî è îçíà÷àåò àääèòèâíîñòü ïîñëåäíåãî. Òåîðåìàäîêàçàíà.25Ãëàâà 2Êðèâèçíà Ðè÷÷è âçâåøåííîãî äåðåâà2.1Îïðåäåëåíèÿ2.1.1 Òðàíñïîðòíàÿ çàäà÷à, êàê çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ.Òåðìèí ¾òðàíñïîðòíàÿ çàäà÷à¿ îáúåäèíÿåò øèðîêèé ñïåêòð çàäà÷, ñâÿçàííûõ ñïîèñêîì îïòèìàëüíûõ ñòðàòåãèé ïåðåðàñïðåäåëåíèÿ ðåñóðñîâ.  ëèíåéíîì ïðîãðàììèðîâàíèè ðàññìàòðèâàåòñÿ ñëåäóþùàÿ ìîäåëü ïîñòàâîê îäíîðîäíîãî òîâàðàîò ïîñòàâùèêîâ ê ïîòðåáèòåëÿì ïðè èçâåñòíûõ òàðèôàõ íà ïåðåâîçêó ìåæäó ïóíêòàìè îòïðàâëåíèÿ è íàçíà÷åíèÿ.Èìååòñÿ n ïóíêòîâ îòïðàâëåíèÿ è m ïóíêòîâ íàçíà÷åíèÿ. Öåíà ïåðåâîçêè åäèíèöû òîâàðà èç i-ãî ïóíêòà îòïðàâëåíèÿ â j -é ïóíêò íàçíà÷åíèÿ îáîçíà÷àåòñÿ÷åðåç cij . Íåîáõîäèìî íàéòè òàêèå îáúåìû ïåðåâîçèìîãî ãðóçà xij , ÷òîáû ìèíèìèçèðîâàòü îáùèå çàòðàòû íà ïåðåâîçêè, ò.å.F =∑∑cij xij → min,ïðè óñëîâèè∑xij = ai ,j∑xij = bj .i26Âåëè÷èíû ai ïðè i = 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
