Характеристики конечных метрических пространств, порожденных графами
Описание файла
PDF-файл из архива "Характеристики конечных метрических пространств, порожденных графами", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст из PDF
ÔÃÁÎÓ ÂÎ ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉÓÍÈÂÅÐÑÈÒÅÒ ÈÌÅÍÈ Ì. Â. ËÎÌÎÍÎÑÎÂÀÌÅÕÀÍÈÊÎ-ÌÀÒÅÌÀÒÈ×ÅÑÊÈÉ ÔÀÊÓËÜÒÅÒÍà ïðàâàõ ðóêîïèñèÐÓÁËÅÂÀÎËÜÃÀ ÂËÀÄÈÌÈÐÎÂÍÀÓÄÊ 514.774.8+515.124.4+519.17+519.224.22ÕÀÐÀÊÒÅÐÈÑÒÈÊÈ ÊÎÍÅ×ÍÛÕ ÌÅÒÐÈ×ÅÑÊÈÕÏÐÎÑÒÐÀÍÑÒÂ, ÏÎÐÎÆÄÅÍÍÛÕ ÃÐÀÔÀÌÈ01.01.04 ãåîìåòðèÿ è òîïîëîãèÿÄèññåðòàöèÿ íà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÍàó÷íûé ðóêîâîäèòåëü:ä.ô.-ì.í., ïðîôåññîð À. Î. ÈâàíîâÌîñêâà 2016ÎãëàâëåíèåÂâåäåíèå41 Àääèòèâíûå êîíå÷íûå ìåòðè÷åñêèå ïðîñòðàíñòâà è ìèíèìàëüíûåçàïîëíåíèÿ141.1Îñíîâíûå îïðåäåëåíèÿ .
. . . . . . . . . . . . . . . . . . . . . . . . .141.2Àääèòèâíûå ïðîñòðàíñòâà. Îïðåäåëåíèÿ, ïðèìåðû, ñâîéñòâà . . . .161.2.1Câîéñòâà àääèòèâíûõ ïðîñòðàíñòâ . . . . . . . . . . . . . . .161.2.2Ïðèìåðû àääèòèâíûõ è íåàääèòèâíûõ ïðîñòðàíñòâ . . . . .17Îäíîìåðíàÿ çàäà÷à Ãðîìîâà î ìèíèìàëüíîì çàïîëíåíèè.
. . . . . .181.3.1Ïðèìåðû ìèíèìàëüíûõ çàïîëíåíèé . . . . . . . . . . . . . .191.3.2Ñâîéñòâà ìèíèìàëüíûõ çàïîëíåíèé . . . . . . . . . . . . . .201.31.41.5Ïåðèìåòðû ìåòðè÷åñêèõ ïðîñòðàíñòâ. Îïðåäåëåíèÿ, ïðèìåðû, ñâîéñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211.4.1Îïðåäåëåíèÿ . . . . . . . .
. . . . . . . . . . . . . . . . . . .211.4.2Ïðèìåðû. . . . . . . . . . . . . . . . . . . . . . . . . . . . .221.4.3Ñâîéñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23Êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà . . .242 Êðèâèçíà Ðè÷÷è âçâåøåííîãî äåðåâà2.1Îïðåäåëåíèÿ . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .2.1.12.1.22626Òðàíñïîðòíàÿ çàäà÷à, êàê çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26Îáîáùåíèå òðàíñïîðòíîé çàäà÷è. . . . . . . . . . . . . . . . .2722.1.3Äâîéñòâåííàÿ òðàíñïîðòíàÿ çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.4Îáîáùåííàÿ äâîéñòâåííàÿ òðàíñïîðòíàÿ çàäà÷à è ôóíêöèÿÂàññåðøòåéíà 1 ïîðÿäêà . . . . . . . . . . . . . . . . . . . . .2.1.52728Êðèâèçíû Ðè÷÷è äëÿ ìåòðè÷åñêèõ ïðîñòðàíñòâ ñî ñëó÷àéíûìáëóæäàíèåì. . .
. . . . . . . . . . . . . . . . . . . . . . . . .292.2Ïðåäâàðèòåëüíûå ðåçóëüòàòû . . . . . . . . . . . . . . . . . . . . . .302.3Ôîðìóëà êðèâèçíû Ðè÷÷è äëÿ âçâåøåííîãî äåðåâà . . . . . . . . . .302.4Ñëåäñòâèÿ èç ôîðìóëû êðèâèçíû Ðè÷÷è äëÿ âçâåøåííîãî äåðåâà .352.4.1Ñëó÷àé áèíàðíîãî äåðåâà ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé. .352.4.2Ñâÿçü ñòðóêòóðû áèíàðíîãî äåðåâà ñ êðèâèçíàìè Ðè÷÷è íàåãî âåðøèíàõ. . . .
. . . . . . . . . . . . . . . . . . . . . . . .2.4.32.52.635Îöåíêà ñóììû êðèâèçí Ðè÷÷è íà ïàðàõ ñìåæíûõ âåðøèí äåðåâà. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36Äîêàçàòåëüñòâà ñëåäñòâèé . . . . . . . . . . . . . . . . . . . . . . . .362.5.1Äîêàçàòåëüñòâî ñëåäñòâèÿ 1. .
. . . . . . . . . . . . . . . . .362.5.2Äîêàçàòåëüñòâî ñëåäñòâèÿ 2. . . . . . . . . . . . . . . . . . .372.5.3Äîêàçàòåëüñòâî ñëåäñòâèÿ 3. . . . . . . . . . . . . . . . . . .40Îöåíêà êðèâèçíû Ðè÷÷è . . . . . . . . . . . . . . . . . . . . . . . . .42Çàêëþ÷åíèå45Ñïèñîê ïóáëèêàöèé ïî òåìå äèññåðòàöèè47Ëèòåðàòóðà483ÂâåäåíèåÄèññåðòàöèÿ ïîñâÿùåíà èçó÷åíèþ õàðàêòåðèñòèê êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ, ïîðîæäåííûõ ãðàôàìè, òàêèõ êàê ìèíèìàëüíûå çàïîëíåíèÿ è êðèâèçíàÐè÷÷è.Ïåðâàÿ ãëàâà äèññåðòàöèè ïîñâÿùåíà èññëåäîâàíèþ îäíîìåðíûõ ìèíèìàëüíûõçàïîëíåíèé êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ.
Ïîíÿòèå îäíîìåðíîãî ìèíèìàëüíîãî çàïîëíåíèÿ êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà âïåðâûå âîçíèêëî â ðàáîòåÈâàíîâà è Òóæèëèíà ([1]) ïðè èçó÷åíèè äâóõ çàäà÷ ïðîáëåìû Øòåéíåðà î êðàò÷àéøèõ ñåòÿõ è çàäà÷è Ãðîìîâà î ìèíèìàëüíîì çàïîëíåíèè.Ïðîáëåìà Øòåéíåðà î êðàò÷àéøèõ ñåòÿõ ýòî çàäà÷à î íàõîæäåíèè îïòèìàëüíîãî ñîåäèíåíèÿ êîíå÷íîãî ïîäìíîæåñòâà ìåòðè÷åñêîãî ïðîñòðàíñòâà. Âïåðâûåýòîò âîïðîñ, ïî-âèäèìîìó, âîçíèê â XVII âåêå â ðàáîòàõ Ïüåðà Ôåðìà, è ïåðâîíà÷àëüíî çàäà÷à ôîðìóëèðîâàëàñü òàê: äëÿ òðåõ çàäàííûõ òî÷åê íà ïëîñêîñòèíóæíî íàéòè òàêóþ ÷åòâåðòóþ, ÷òîáû ñóììà ðàññòîÿíèé îò íåå äî òðåõ çàäàííûõòî÷åê áûëà ìèíèìàëüíîé ([2]).Ïîñòàâëåííàÿ Ï. Ôåðìà çàäà÷à ðåøàëàñü â òå÷åíèå íåñêîëüêèõ ñòîëåòèé. Ïåðâûå ðåøåíèÿ è ðàñïîëîæåíèÿ òî÷åê ïðåäëîæèëè Ý.
Òîððè÷åëëè è Á. Êàâàëüåðè(â XVII â.), çàòåì èõ êîíñòðóêöèþ óñîâåðøåíñòâîâàë ñïóñòÿ ñòîëåòèå Ò. Ñèìïñîí.Íàêîíåö â êîíöå XIX âåêà Ô. Õàéíåí è Æ. Áåðòðàì ïðåäëîæèëè ïîëíîå ðåøåíèåçàäà÷è Ôåðìà ([3]). Îäíèì èç îáîáùåíèé çàäà÷è Ôåðìà ÿâëÿåòñÿ òðàíñïîðòíàÿçàäà÷à î ñîåäèíåíèè ÷åòûðåõ ãîðîäîâ êðàò÷àéøåé ñèñòåìîé äîðîã, êîòîðóþ ðåøèë Ê.Ô. Ãàóññ, ïðåäëîæèâ ââåñòè äâå òî÷êè-ðàçâèëêè.
Òàêæå îáîáùåíèå çàäà÷èÔåðìà äëÿ ìíîæåñòâ, ñîñòîÿùèõ èç 4 è 5 òî÷åê, ðàññìàòðèâàëè ôðàíöóçñêèå ìàòåìàòèêè Æ.Ä. Æåðãîíí, Á.Ï.Ý. Êëàéïåðîí è Ã. Ëàìå.Îáîáùåíèå çàäà÷è Ôåðìà äëÿ n òî÷åê íà÷àë èññëåäîâàòü åùå Øòåéíåð. Îí4ïðåäëîæèë ðàññìîòðåòü åäèíñòâåííóþ äîïîëíèòåëüíóþ òî÷êó ñ ìèíèìàëüíîé ñóììîé ðàññòîÿíèé îò ýòîé òî÷êè äî çàäàííûõ. Íî â 1934 ã. Â.ßðíèê è Î.Êåñëåð ([4])ïðåäëîæèëè óâåëè÷èòü êîëè÷åñòâî âñïîìîãàòåëüíûõ òî÷åê, êàê ýòî äåëàëè â ÷àñòíûõ ñëó÷àÿõ Ãàóññ è Æåðãîíí, äëÿ ìèíèìèçàöèè ñóììû ðàññòîÿíèé ìåæäó âñåìèòî÷êàìè.
 íàñòîÿùèå äíè èìåííî ýòó çàäà÷ó ïðèíÿòî íàçûâàòü ïðîáëåìîé Øòåéíåðà.Ðàññìîòðèì çàäà÷ó Ãðîìîâà. Ïóñòü M ãëàäêîå çàìêíóòîå ìíîãîîáðàçèå, íàêîòîðîì çàäàíà ôóíêöèÿ ðàññòîÿíèÿ ρ. Ðàññìîòðèì âñåâîçìîæíûå ïëåíêè W , çàòÿãèâàþùèå M , ò.å. çàìêíóòûå êîìïàêòíûå ìíîãîîáðàçèÿ ñ êðàåì, ðàâíûì M .Ðàññìîòðèì íà ìíîãîîáðàçèè W ôóíêöèþ ðàññòîÿíèÿ d, íå óìåíüøàþùóþ ðàññòîÿíèÿ ìåæäó òî÷êàìè èç M . Òàêîå ïðîñòðàíñòâî W = (W, d) áóäåì íàçûâàòüçàïîëíåíèåì ìåòðè÷åñêîãî ïðîñòðàíñòâà M = (M, ρ).
Çàäà÷à Ãðîìîâà ñîñòîèò âîïèñàíèè òî÷íîé íèæíåé ãðàíè îáúåìîâ çàïîëíåíèé, à òàêæå â ïîèñêå òåõ ïðîñòðàíñòâ W , íàçûâàåìûõìèíèìàëüíûìè çàïîëíåíèÿìè, íà êîòîðûõ ýòà íèæíÿÿãðàíü äîñòèãàåòñÿ. Ìèíèìàëüíûå çàïîëíåíèÿ íàøëè ïðèìåíåíèÿ â òåîðèè äèíàìè÷åñêèõ ñèñòåì, àñèìïòîòè÷åñêîé ãåîìåòðèè è ìàòåìàòè÷åñêîé ôèçèêå.À.Î. Èâàíîâ è À.À. Òóæèëèí ðàññìîòðåëè â êà÷åñòâå M êîíå÷íîå ìåòðè÷åñêîå ïðîñòðàíñòâî, à çàïîëíåíèÿìè ýòîãî ïðîñòðàíñòâà ñòàëè ìåòðè÷åñêîå ïðîñòðàíñòâà, èìåþùèå ñòðóêòóðó îäíîìåðíûõ ñòðàòèôèöèðîâàííûõ ìíîãîîáðàçèé,êîòîðûå ìîæíî ðàññìàòðèâàòü êàê ãðàôû ñ íåîòðèöàòåëüíîé âåñîâîé ôóíêöèåéíà ðåáðàõ. Òàêèì îáðàçîì, À.Î. Èâàíîâ è À.À.
Òóæèëèí â [1] ïîëó÷èëè îáîáùåíèå ïðîáëåìû Ãðîìîâà íà ñëó÷àé ñòðàòèôèöèðîâàííûõ ìíîãîîáðàçèé, êîòîðîåôîðìóëèðóåòñÿ òàê.Ïóñòü M ïðîèçâîëüíîå êîíå÷íîå ìíîæåñòâî, G = (V, E) íåêîòîðûé ñâÿçíûé ãðàô. Ãîâîðÿò, ÷òî ãðàô Gñîåäèíÿåò M , åñëè V⊃ M . Ïóñòü M = (M, ρ) êîíå÷íîå ïñåâäîìåòðè÷åñêîå ïðîñòðàíñòâî, à G = (V, E) ñâÿçíûé ãðàô, ñîåäèíÿþùèé M .
Íà ðåáðàõ ãðàôà çàäàäèì ôóíêöèþ ω : E → R+ , ãäå R+ íåîòðèöàòåëüíûå ÷èñëà. Êàê ïðàâèëî, ýòó ôóíêöèþ ω íàçûâàþòïàðó (G, ω) âåñîâîé ôóíêöèåé, àâçâåøåííûì ãðàôîì. Ôóíêöèÿ ω ïîðîæäàåò íà ìíîæåñòâå âåðøèí Vãðàôà G èíäóöèðîâàííóþ ïñåâäîìåòðèêó dω , êîòîðàÿ ïî îïðåäåëåíèþ ðàâíà íàè5ìåíüøåìó âåñó ïóòè ìåæäó äâóìÿ çàäàííûìè âåðøèíàìè ñâÿçíîãî ãðàôà. Åñëèäëÿ ëþáûõ òî÷åê p è q èç ìíîæåñòâà M ïñåâäîìåòðèêà dω íå óìåíüøàåò ðàññòîÿíèå ìåæäó ýòèìè òî÷êàìè îòíîñèòåëüíî ïñåâäîìåòðèêè ρ, ò.å. dω (p, q) ≥ ρ(p, q),òî âçâåøåííûé ãðàô G íàçûâàåòñÿçàïîëíåíèåì ìåòðè÷åñêîãî ïðîñòðàíñòâà M, àòèïîì ýòîãî çàïîëíåíèÿ. ×èñëî mf(M) = inf ω(G) ïî âñåì çàïîëíåíèÿì ìåòðè÷åñêîãî ïðîñòðàíñòâà M íàçûâàåòñÿ âåñîì ìèíèìàëüíîãî çàïîëíåíèÿ.ãðàô G Îäíîìåðíàÿ çàäà÷à Ãðîìîâà ñîñòîèò â íàõîæäåíèè çàïîëíåíèÿ G ñ âåñîì, ðàâíûìmf(M).
Òàêîå çàïîëíåíèå ìåòðè÷åñêîãî ïðîñòðàíñòâà íàçûâàåòñÿçàïîëíåíèåì ïðîñòðàíñòâà M.ìèíèìàëüíûìÎêàçàëîñü, ÷òî â òåîðèè ìèíèìàëüíûõ çàïîëíåíèé ïñåâäîìåòðè÷åñêèõ ïðîñòðàíñòâ âàæíóþ ðîëü èãðàþò òàê íàçûâàåìûå àääèòèâíûå è ïñåâäîàääèòèâíûåïðîñòðàíñòâà ([1]), êîòîðûå òàêæå ÷àñòî âñòðå÷àþòñÿ â ïðèëîæåíèÿõ, òàêèõ êàêáèîèíôîðìàòèêà è òåîðèÿ ýâîëþöèè (ñì., íàïðèìåð, [9]). Êîíå÷íîå ìåòðè÷åñêîåïðîñòðàíñòâî M = (M, ρ) íàçûâàåòñÿàääèòèâíûì, åñëè ñóùåñòâóåò âçâåøåííîåäåðåâî G = (G, ω), G = (V, E), òàêîå ÷òî M ⊂ V , è ìåòðèêà ρ ñîâïàäàåò ñ îãðàíè÷åíèåì íà M ìåòðèêè dω . Äåðåâî G â ýòîì ñëó÷àå íàçûâàåòñÿïîðîæäàþùèìäëÿ M. Íå âñÿêîå ïñåâäîìåòðè÷åñêîå ïðîñòðàíñòâî ÿâëÿåòñÿ àääèòèâíûì. Õîðîøî èçâåñòåí ñëåäóþùèé êðèòåðèé àääèòèâíîñòè [5], [6]: ïñåâäîìåòðè÷åñêîå ïðîñòðàíñòâî (M, ρ) àääèòèâíî, åñëè è òîëüêî åñëè äëÿ íåãî âûïîëíÿåòñÿ ñëåäóþùååïðàâèëî ÷åòûðåõ òî÷åê : äëÿ ëþáûõ ÷åòûðåõ òî÷åê pi, pj , pk , pl èç M âåëè÷èíûρ(pi , pj ) + ρ(pk , pl ), ρ(pi , pk ) + ρ(pj , pl ), ρ(pi , pl ) + ρ(pj , pk ) ÿâëÿþòñÿ äëèíàìè ñòîðîíðàâíîáåäðåííîãî òðåóãîëüíèêà ñ îñíîâàíèåì, íå ïðåâîñõîäÿùèì áîêîâîé ñòîðîíû. [1] áûëà ââåäåíà õàðàêòåðèñòèêà êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà åãîïîëóïåðèìåòð (ñì.
òî÷íîå îïðåäåëåíèå â ãëàâå 1), êîòîðàÿ õàðàêòåðèçóåò ìèíèìàëüíóþ äëèíó öèêëà, ïðîõîäÿùåãî ÷åðåç âñå òî÷êè ïðîñòðàíñòâà.  äèññåðòàöèèïîëó÷åí êðèòåðèé àääèòèâíîñòè êîíå÷íîãî ìåòðè÷åñêîãî ïðîñòðàíñòâà, îñíîâàííûé íà ñâîéñòâàõ ìèíèìàëüíûõ çàïîëíåíèé.Âåñ ìèíèìàëüíîãî çàïîëíåíèÿ ïñåâäîìåòðè÷åñêîãî ïðîñòðàíñòâàðàâåí ïîëóïåðèìåòðó ýòîãî ïðîñòðàíñòâà òîãäà è òîëüêî òîãäà, êîãäà ïðîñòðàíñòâî àääèòèâíî.Òåîðåìà 1.6Âòîðàÿ ãëàâà äèññåðòàöèè ïîñâÿùåíà äðóãîé õàðàêòåðèñòèêå êîíå÷íûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ, ïîðîæäåííûõ ãðàôàìè, êðèâèçíå Ðè÷÷è.Ïîíÿòèå êðèâèçíû Ðè÷÷è äëÿ ìåòðè÷åñêèõ ïðîñòðàíñòâ îáùåãî âèäà âïåðâûåâîçíèêëî â ðàáîòàõ Áàêðè è Ýìåðè [10]. Èìè áûëà òàêæå îïðåäåëåíà òàê íàçûâàåìàÿ ¾íèæíÿÿ ãðàíèöà¿ êðèâèçíû Ðè÷÷è íà êëàññå èçìåðèìûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ.
Áûëè íàéäåíû ñâîéñòâà èçìåðèìûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ, íåîáõîäèìûå äëÿ ñóùåñòâîâàíèÿ ¾íèæíåé ãðàíèöû¿ êðèâèçíû Ðè÷÷è ýòèõ ïðîñòðàíñòâ.Ñóùåñòâîâàíèå ¾íèæíåé ãðàíèöû¿ êðèâèçíû Ðè÷÷è ïîçâîëÿåò óñòàíîâèòü âåðõíþþ ãðàíèöó äëÿ äèàìåòðà ìåòðè÷åñêîãî ïðîñòðàíñòâà (òåîðåìà Áîííå-Ìàéåðà). ñëó÷àå, êîãäà ìåòðè÷åñêîå ïðîñòðàíñòâî ïîðîæäåíî ãðàôîì, ìîæíî óñòàíîâèòüâåðõíþþ ãðàíèöó äëÿ äèàìåòðà ãðàôà (àíàëîã òåîðåìû Áîííå-Ìàéåðà äëÿ ãðàôà), à òàêæå îöåíèòü êîëè÷åñòâî âåðøèí â ãðàôå. Îêàçûâàåòñÿ, ¾íèæíÿÿ ãðàíèöà¿ êðèâèçíû Ðè÷÷è ÿâëÿåòñÿ òàêæå íèæíåé ãðàíèöåé äëÿ ïåðâîãî íåíóëåâîãîñîáñòâåííîãî çíà÷åíèÿ ëàïëàñèàíà äëÿ G.  2009 ãîäó Îëèâüå [11] äàë îïðåäåëåíèå ãðóáîé êðèâèçíû Ðè÷÷è íà öåïÿõ Ìàðêîâà, êîòîðîå ìîæíî èñïîëüçîâàòü äëÿìåòðè÷åñêèõ ïðîñòðàíñòâ, ïîðîæäåííûõ ãðàôàìè.×àíã è ßó âïåðâûå ââåëè îïðåäåëåíèå êðèâèçíû Ðè÷÷è äëÿ ãðàôîâ â 1996 ãîäó( [14]).