Характеристики конечных метрических пространств, порожденных графами (1105193), страница 3
Текст из файла (страница 3)
Àâòîð ãëóáîêî ïðèçíàòåëåí âñåìó êîëëåêòèâó12êàôåäðû äèôôåðåíöèàëüíîé ãåîìåòðèè è ïðèëîæåíèé Ìåõàíèêî-ìàòåìàòè÷åñêîãîôàêóëüòåòà ÌÃÓ çà òåïëóþ àòìîñôåðó, ïîääåðæêó è âíèìàíèå.13Ãëàâà 1Àääèòèâíûå êîíå÷íûå ìåòðè÷åñêèåïðîñòðàíñòâà è ìèíèìàëüíûå çàïîëíåíèÿ1.1Îñíîâíûå îïðåäåëåíèÿÌåòðè÷åñêèì ïðîñòðàíñòâîì M íàçûâàåòñÿ ïàðà (M, ρ), ãäå M ìíîæåñòâî, ýëåìåíòû êîòîðîãî íàçûâàþòñÿ òî÷êàìè, à ρ : M × M → R ôóíêöèÿ ðàññòîÿíèÿ èëè ìåòðèêà íà ìíîæåñòâå M , òî åñòü äëÿ ôóíêöèè ρ èÎïðåäåëåíèå.ëþáûõ òðåõ òî÷åê x, y, z ∈ M âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:1.
ρ(x, y) ≥ 0;2. ρ(x, y) = 0 ⇔ x = y ;ñèììåòðèÿ );4. ρ(x, z) ≤ ρ(x, y) + ρ(y, z) (íåðàâåíñòâî òðåóãîëüíèêà ).3. ρ(x, y) = ρ(y, x) (Îïðåäåëåíèå.Ïñåâäîìåòðèêîé íà ìíîæåñòâå Míàçûâàåòñÿ ôóíêöèÿ d : M ×M → R, óäîâëåòâîðÿþùàÿ óñëîâèÿì äëÿ ïðîèçâîëüíûõ òî÷åê x, y, z ∈ M :1. d(x, y) ≥ 02. åñëè x = y , òî d(x, y) = 0;ñèììåòðèÿ );4. d(x, z) ≤ d(x, y) + d(y, z) (íåðàâåíñòâî òðåóãîëüíèêà ).3. d(x, y) = d(y, x) ( îòëè÷èå îò ìåòðèêè, äëÿ ïñåâäîìåòðèêè òî÷êè íå îáÿçàíû ñîâïàäàòü ïðèíóëåâîì ðàññòîÿíèè ìåæäó íèìè.14Îïðåäåëåíèå.Ïñåâäîìåòðè÷åñêèì ïðîñòðàíñòâîìíàçûâàåòñÿ ïàðà M =(M, d), ãäå M íåêîòîðîå ìíîæåñòâî, ýëåìåíòû êîòîðîãî íàçûâàþòñÿ òî÷êàìè, àd ïñåâäîìåòðèêà íà ýòîì ìíîæåñòâå.Îïðåäåëåíèå.Ãðàôîì G íàçûâàåòñÿ ïàðà (V, E), ãäå V ìíîæåñòâî âåðøèíãðàôà, à E ⊂ V (2) ìíîæåñòâî ðåáåð ãðàôà, ãäå ÷åðåç V (2) îáîçíà÷åíî ìíîæåñòâî äâóõýëåìåíòíûõ ïîäìíîæåñòâ ìíîæåñòâà V . Îáû÷íî òàêîé ãðàô íàçûâàåòñÿïðîñòûì.Îïðåäåëåíèå.Öèêëîì â ãðàôå íàçûâàþò ïîñëåäîâàòåëüíîñòü åãî âåðøèí, â êî-òîðîé êàæäàÿ âåðøèíà ñîåäèíåíà ñî ñëåäóþùåé ðåáðîì, ïðè÷åì âñå ðåáðà â öèêëåðàçëè÷íû, à ïåðâàÿ è ïîñëåäíÿÿ âåðøèíû ïîñëåäîâàòåëüíîñòè ñîâïàäàþò.
Öèêëãðàôà, ñîñòîÿùèé èç ïîñëåäîâàòåëüíîñòè íåïîâòîðÿþùèõñÿ âåðøèí, íàçûâàåòñÿïðîñòûì öèêëîì.Îïðåäåëåíèå.Ïóòåìâ ãðàôå íàçûâàåòñÿ íàçûâàåòñÿ ïîñëåäîâàòåëüíîñòü åãîâåðøèí, â êîòîðîé êàæäàÿ âåðøèíà ñîåäèíåíà ñî ñëåäóþùåé ðåáðîì. Åñëè äëÿäâóõ ïðîèçâîëüíûõ âåðøèíû ãðàôà ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü åãî âåðøèíòàêàÿ, ÷òî êàæäàÿ âåðøèíà ñîåäèíåíà ñî ñëåäóþùåé ðåáðîì, âñå ðåáðà ðàçëè÷íû,à ïåðâûì è ïîñëåäíèì ýëåìåíòàìè ýòîé ïîñëåäîâàòåëüíîñòè ÿâëÿþòñÿ çàäàííûåâåðøèíû, òî ãîâîðÿò, ÷òî ýòè äâå âåðøèíûñîåäèíåíû íåêîòîðûì ïóòåì.Îïðåäåëåíèå. Ãðàô G = (V, E) íàçûâàåòñÿñâÿçíûì, åñëè ëþáûå äâå âåðøèíûãðàôà ìîæíî ñîåäèíèòü õîòÿ áû îäíèì ïóòåì.Îïðåäåëåíèå. Ïóñòü G = (V, E) ïðîèçâîëüíûé ãðàô, à v, w ∈ V , e = {v, w} ∈E , òîãäà ãîâîðÿò, ÷òî âåðøèíà v (èëè w) è ðåáðî eÎïðåäåëåíèå.Ñòåïåíüþ âåðøèíûèíöèäåíòíû.ãðàôà íàçûâàåòñÿ êîëè÷åñòâî ðåáåð, èíöè-äåíòíûõ ýòîé âåðøèíå.Îïðåäåëåíèå.
Ñâÿçíûé àöèêëè÷íûé, ò.å. áåç öèêëîâ, ãðàô íàçûâàåòñÿÄåðåâî íàçîâåìáèíàðíûì, åñëè ñòåïåíè âåðøèí äåðåâà ðàâíû 1 èëè 3.15äåðåâîì.Òàê êàê â äàëüíåéøåì ðå÷ü ïîéäåò î ãðàíè÷íûõ çàäà÷àõ, òàêèõ êàê çàäà÷à îáîïòèìàëüíîì ñîåäèíåíèè, óäîáíî ïðåäïîëàãàòü, ÷òî ó êàæäîãî ãðàôà G ôèêñèðîâàíî íåêîòîðîå ïîäìíîæåñòâî ìíîæåñòâà âåðøèí (âîçìîæíî, ïóñòîå), êîòîðîå ìûáóäåì íàçûâàòüãðàíè÷íûì è îáîçíà÷àòü ∂G.Îïðåäåëåíèå. Âçâåøåííûì ãðàôîì íàçûâàåòñÿ ïàðà G = (G, ω), ãäå G = (V, E) ñâÿçíûé ãðàô, à ω : E → R+ ôóíêöèÿ, êîòîðàÿ êàæäîìó ðåáðó ãðàôà G ñòàâèò â ñîîòâåòñòâèå íåîòðèöàòåëüíîå âåùåñòâåííîå ÷èñëî.
Ýòó ôóíêöèþ íàçûâàþòâåñîâîé ôóíêöèåé.Äëÿ êàæäîãî ïóòè γ è êàæäîãî ïîäãðàôà H âî âçâåøåííîì ãðàôå G îïðåäåëåíû èõâåñà ω(γ) è ω(H) ñîîòâåòñòâåííî, ðàâíûå ñóììå âåñîâ âñåõ âõîäÿùèõ â íèõðåáåð. Ýòî ïîçâîëÿåò ïðåâðàòèòü ìíîæåñòâî âåðøèí ñâÿçíîãî âçâåøåííîãî ãðàôà G â ïñâäîìåòðè÷åñêîå ïðîñòðàíñòâî, ïîëîæèâ ðàññòîÿíèå ìåæäó âåðøèíàìèãðàôà G ðàâíûì íàèìåíüøåìó âîçìîæíîìó âåñó ñîåäèíÿþùåãî èõ â G ïóòè. Òàêîïðåäåëåííóþ ôóíêöèþ ðàññòîÿíèÿ îáîçíà÷èì ÷åðåç dω è íàçîâåìðàññòîÿíèåì,ïîðîæäåííûì âåñîâîé ôóíêöèåé ω.
Äîêàçàòåëüñòâî àêñèîì ïñåâäîìåòðè÷åñêîãîïðîñòðàíñòâà ñëåäóåò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ ôóíêöèè dω .1.2Àääèòèâíûå ïðîñòðàíñòâà. Îïðåäåëåíèÿ, ïðèìåðû, ñâîéñòâàÎïðåäåëåíèå. Êîíå÷íîå ìåòðè÷åñêîå ïðîñòðàíñòâî M = (M, ρ) íàçûâàåòñÿ àääèòèâíûì, åñëè ñóùåñòâóåò âçâåøåííîå äåðåâî G = (G, ω), G = (V, E), òàêîå ÷òî∂G ⊂ M ⊂ V , è ìåòðèêà ρ ñîâïàäàåò ñ îãðàíè÷åíèåì íà M ìåòðèêè dω . Äåðåâî Gâ ýòîì ñëó÷àå íàçûâàåòñÿ ïîðîæäàþùèì äëÿ M.1.2.1 Câîéñòâà àääèòèâíûõ ïðîñòðàíñòâÊðèòåðèåì àääèòèâíîñòè ïðîñòðàíñòâà ÿâëÿåòñÿ ñëåäóþùåå èçâåñòíîå ïðàâèëî,íàçûâàåìîåïðàâèëîì ÷åòûðåõ òî÷åê.16Òåîðåìà 3.
([5])Ïñåâäîìåòðè÷åñêîå ïðîñòðàíñòâî M = (M, ρ) àääèòèâíî,åñëè è òîëüêî åñëè äëÿ ëþáûõ ÷åòûðåõ òî÷åê pi, pj , pk , pl èç M âåëè÷èíûρ(pi , pj ) + ρ(pk , pl ), ρ(pi , pk ) + ρ(pj , pl ), ρ(pi , pl ) + ρ(pj , pk ) ÿâëÿþòñÿ äëèíàìè ñòîðîí íåêîòîðîãî ðàâíîáåäðåííîãî òðåóãîëüíèêà ñ îñíîâàíèåì, íå ïðåâîñõîäÿùèìáîêîâîé ñòîðîíû. ðàáîòàõ [15, 17] äîêàçàíà åäèíñòâåííîñòü ïîðîæäàþùåãî äåðåâà ñ ðåáåð íåíó-íåâûðîæäåííûì.Òåîðåìà 4. ([15, 17]) Åñëè îãðàíè÷èòüñÿ ðàññìîòðåíèåì íåâûðîæäåííûõ äåðåâüåâ, òî ïîðîæäàþùåå äåðåâî àääèòèâíîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà åäèíñòâåííî.ëåâîãî âåñà, íàçûâàåìîãîÑëåäóþùèé ðåçóëüòàò, ñôîðìóëèðîâàííûé è äîêàçàííûé â ðàáîòå [1], ïîëíîñòüþ ðåøàåò çàäà÷ó î ìèíèìàëüíûõ çàïîëíåíèÿõ àääèòèâíûõ ïðîñòðàíñòâ.( [1]) Ìèíèìàëüíûìè çàïîëíåíèÿìè àääèòèâíîãî ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà ÿâëÿþòñÿ åãî ïîðîæäàþùèå äåðåâüÿ è òîëüêî îíè.Òåîðåìà 5.1.2.2 Ïðèìåðû àääèòèâíûõ è íåàääèòèâíûõ ïðîñòðàíñòâÏðèìåð 1.Íåàääèòèâíûì ïðîñòðàíñòâîìÿâëÿåòñÿ, íàïðèìåð, ÷åòûðåõòî÷å÷íîå ïðî-ñòðàíñòâî (M, ρ) òàêîå, ÷òî òðè åãî òî÷êè â äàííîé ìåòðèêå îáðàçóþò íà ïëîñêîñòèòðåóãîëüíèê ñî ñòîðîíàìè 2, 3, 4, à ÷åòâåðòàÿ òî÷êà ëåæèò â öåíòðå îïèñàííîéîêðóæíîñòè.Îáîçíà÷èì öåíòð îïèñàííîé îêðóæíîñòè p1 , à îñòàëüíûå òî÷êè ýòîãî ïðîñòðàíñòâà p2 , p3 , p4 òàê, ÷òî ρ(p1 , pi ) = r äëÿ i = 2, 3, 4, à ρ(p2 , p3 ) = 2, ρ(p3 , p4 ) =4, ρ(p2 , p4 ) = 3.Èìååìρ(p1 , p2 ) + ρ(p3 , p4 ) = r + 4,ρ(p1 , p3 ) + ρ(p2 , p4 ) = r + 3,17ρ(p1 , p4 ) + ρ(p2 , p3 ) = r + 2.Äëÿ àääèòèâíîñòè ïðîñòðàíñòâà (M, ρ) íåîáõîäèìî ðàâåíñòâî äâóõ èç òðåõ âåëè÷èí.
Íî â äàííîì ïðèìåðå ýòî óñëîâèå íå âûïîëíÿåòñÿ, ñëåäîâàòåëüíî, ïðîñòðàíñòâî íåàääèòèâíî.Ïðèìåð 2.Àääèòèâíûì ïðîñòðàíñòâîì ÿâëÿåòñÿ, íàïðèìåð, ÷åòûðåõòî÷å÷íîå ïðîñòðàíñòâî (M, ρ), òðè òî÷êè êîòîðîãî îáðàçóþò ðàâíîñòîðîííèé òðåóãîëüíèê ñî ñòîðîíîé 1, à ðàññòîÿíèå îò ÷åòâåðòîé òî÷êè äî âåðøèí ýòîãî òðåóãîëüíèêà ðàâíî 12 .Ïîðîæäàþùèì äåðåâîì ýòîãî ïðîñòðàíñòâà áóäåò çâåçäà ñ âåðøèíîé â ýòîé ÷åòâåðòîé òî÷êå è ðàññòîÿíèÿìè äî îñòàëüíûõ 21 .Îáîçíà÷èì âåðøèíû òðåóãîëüíèêà p1 , p2 , p3 , à ÷åòâåðòóþ òî÷êó p4 òàê, ÷òîρ(p4 , pi ) =i4äëÿ i = 1, 2, 3, à ρ(p1 , p2 ) = ρ(p2 , p3 ) = ρ(p1 , p3 ) = 1. Èìååì3ρ(p1 , p2 ) + ρ(p3 , p4 ) = ,23ρ(p1 , p3 ) + ρ(p2 , p4 ) = ,23ρ(p1 , p4 ) + ρ(p2 , p3 ) = .2Ïðàâèëî ÷åòûðåõ òî÷åê äëÿ ýòîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà âûïîëíåíî, ñëåäîâàòåëüíî ïðîñòðàíñòâî àääèòèâíî.1.3Îäíîìåðíàÿ çàäà÷à Ãðîìîâà î ìèíèìàëüíîì çàïîëíåíèè.Îïðåäåëåíèå.
Ñâÿçíûé âçâåøåííûé ãðàô G = (G, ω), ãäå G = (V, E), íàçûâàåòñÿçàïîëíåíèåì ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà M = (M, ρ), åñëè M ⊂ Vèäëÿ ëþáîé ïàðû òî÷åê x è y èç M âûïîëíåíî íåðàâåíñòâî ρ(x, y) ≤ dω (x, y).Îïðåäåëåíèå. Âåëè÷èíà ω(G) íàçûâàåòñÿ âåñîìçàïîëíåíèÿ G . Èíôèìóì âåñîââñåâîçìîæíûõ çàïîëíåíèé ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà M îáîçíà÷àåòñÿ ÷åðåç mf(M) è íàçûâàåòñÿâåñîì ìèíèìàëüíîãî çàïîëíåíèÿ ïðîñòðàíñòâà M.18ìèíèìàëüíûì çàïîëíåíèåì ïðîñòðàíñòâà M, à G òèïîì ìèíèìàëüíîãî çàïîëíåíèÿ.Îïðåäåëåíèå.
Çàïîëíåíèå G , äëÿ êîòîðîãî ω(G) = mf(M), íàçûâàåòñÿÎïðåäåëåíèå. Ïóñòü M = (M, ρ) ïðîèçâîëüíîå êîíå÷íîå ìåòðè÷åñêîå ïðîñòðàíñòâî, è G = (G, ω) íåêîòîðîå åãî çàïîëíåíèå. Ïóòü, ñîåäèíÿþùèé ãðàíè÷íûå âåðøèíû äåðåâà G , áóäåì íàçûâàòüãðàíè÷íûì, à ãðàíè÷íûé ïóòü, âåñêîòîðîãî ðàâåí ðàññòîÿíèþ ìåæäó åãî êîíöåâûìè âåðøèíàìè â ïðîñòðàíñòâå M,òî÷íûì.1.3.1 Ïðèìåðû ìèíèìàëüíûõ çàïîëíåíèéÏîíÿòèå ìèíèìàëüíîãî çàïîëíåíèÿ ðàçðàáîòàíî â [1], òàì æå ïðèâåäåí ðÿä ïðîñòûõ ïðèìåðîâ.Ïðèìåð 1.
ÒðåóãîëüíèêÏóñòü M = (M, ρ) ñîñòîèò è òðåõ òî÷åê p1 , p2 , p3 . Ïîëîæèì ρij = ρ(pi , pj ).Ðàññìîòðèì äåðåâî G = (V, E), ó êîòîðîãî V = M∪{v} è E =∪3i=1 vpi .Äëÿãðàôà G îïðåäåëèì âåñîâóþ ôóíêöèþ ω íà E ïî ôîðìóëå:ρij + ρik − ρjk,2ãäå {i, j, k} = {1, 2, 3}. ßñíî, ÷òî ôóíêöèÿ dω , îãðàíè÷åííàÿ íà M , ñîâïàäàåò ñ ρ,ω(ei ) =ïîýòîìó G ìèíèìàëüíîå çàïîëíåíèå ïðîñòðàíñòâà M.Ïðèìåð 2. ×åòûðåõòî÷å÷íîåïðîñòðàíñòâîÓòâåðæäåíèå 1. ([1], óòâåðæäåíèå 11.3) Ïóñòü M = {p1 , p2 , p3 , p4 }, è ρ ïðî-èçâîëüíàÿ ïñåâäîìåòðèêà íà M .
Ïîëîæèì ρij = ρ(pi, pj ). Òîãäà âåñ ìèíèìàëüíîãî çàïîëíåíèÿ G = (G, ω) ïðîñòðàíñòâà M = (M, ρ) äàåòñÿ ôîðìóëîé1(min(ρ12 + ρ34 , ρ13 + ρ24 , ρ14 + ρ23 )+2)+ max(ρ12 + ρ34 , ρ13 + ρ24 , ρ14 + ρ23 ) .Åñëè ìèíèìóì â ýòîé ôîðìóëå ðàâåí ρij + ρkl , òî òèï ìèíèìàëüíîãî çàïîëíåíèÿ áèíàðíîå äåðåâî, óñû êîòîðîãî ñóòü {pi, pj } è {pk , pl}.19Ïðèìåð 3.
ÏðàâèëüíûéñèìïëåêñÏóñòü M = (M, ρ) ñîñòîèò è n òî÷åê p1 , p2 . . . pn , ðàññòîÿíèå ìåæäó êîòîðûìè ïîñòîÿííî è ðàâíî d, ò.å. M òàê íàçûâàåìûé ïðàâèëüíûé ñèìïëåêñ. Òîãäàâçâåøåííîå äåðåâî G = (G, ω), G = (V, E) ñ ìíîæåñòâîì âåðøèí V = M∪{v} èðåáðàìè vm, m ∈ M , âåñà êîòîðûõ ðàâíû d/2, ÿâëÿåòñÿ ïîðîæäàþùèì äëÿ M,ñëåäîâàòåëüíî ïðîñòðàíñòâî M àääèòèâíî è G åãî åäèíñòâåííîå íåâûðîæäåííîåìèíèìàëüíîå çàïîëíåíèå (ïî òåîðåìå 3), âåñ êîòîðîãî ðàâåídn2 .1.3.2 Ñâîéñòâà ìèíèìàëüíûõ çàïîëíåíèé ðàáîòå [1] ïîêàçàíî, ÷òî ìèíèìàëüíîå çàïîëíåíèå êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà âñåãäà ñóùåñòâóåò, ïðè÷åì ïðè ïîèñêå ìèíèìàëüíîãî çàïîëíåíèÿ äëÿM = (M, ρ) ìîæíî îãðàíè÷èòüñÿ ðàññìîòðåíèåì äåðåâüåâ G = (V, E), M ⊂ V , óêîòîðûõ âñå âåðøèíû ñòåïåíè 1 è 2 ïðèíàäëåæàò M .([1]) Äëÿ ëþáîãî êîíå÷íîãî ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâà Mñóùåñòâóåò ìèíèìàëüíîå çàïîëíåíèå, ÿâëÿþùååñÿ áèíàðíûì äåðåâîì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
