Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf), страница 4
Описание файла
PDF-файл из архива "Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
„Î. 6) fl‚ÎflÂÚÒfl ‚ÍÎˉӂÓÈ ÚÓ„‰‡ ËÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ Ó̇ fl‚ÎflÂÚÒfl ÔÚÓÎÂÏ‚ÓÈ.20ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈd ( x, y), fl‚ÎflÂÚÒfld ( x, z )d ( y, z )ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ ‰Îfl β·Ó„Ó z ∈ X ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ d fl‚ÎflÂÚÒfl ÔÚÓÎÂÏ‚ÓÈ ÏÂÚËÍÓÈ ([FoSC06]).ÑÎfl β·ÓÈ ÏÂÚËÍË d ‡ÒÒÚÓflÌË d fl‚ÎflÂÚÒfl ÔÚÓÎÂÏ‚ÓÈ ÏÂÚËÍÓÈ([FoSC06]).àÌ‚ÓβÚË‚ÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X \z, d z), „‰Â d ( x, y) =ë··‡fl ÛθڇÏÂÚË͇ë··ÓÈ ÛθڇÏÂÚËÍÓÈ (ËÎË ë-ÔÒ‚‰Ó‡ÒÒÚÓflÌËÂÏ) ̇Á˚‚‡ÂÚÒfl ‡ÒÒÚÓflÌËÂd ̇ ï, ‰Îfl ÍÓÚÓÓ„Ó ÔË ÌÂÍÓÚÓÓÈ ÍÓÌÒÚ‡ÌÚ ë ≥ 1, ̇‚ÂÌÒÚ‚Ó0 < d(x, y) ≤ C max{d(x, z), d(z, y)}‚˚ÔÓÎÌflÂÚÒfl ‰Îfl ‚ÒÂı x, y, z ∈ X, ı ≠ Û.
ÑÎfl Ú‡ÍÓ„Ó ‡ÒÒÚÓflÌËfl d ‡ÒÒÚÓflÌË d(x, y) == infd ( z i , z i +1 ), „‰Â ËÌÙËÏÛÏ ·ÂÂÚÒfl ÔÓ ‚ÒÂÏ ÔÓÒΉӂ‡ÚÂθÌÓÒÚflÏ∑ix = z0 , ..., zn+1), fl‚ÎflÂÚÒfl ÔÓÎÛÏÂÚËÍÓÈ.íÂÏËÌ ÔÒ‚‰Ó‡ÒÒÚÓflÌË ËÒÔÓθÁÛÂÚÒfl Ú‡ÍÊ ‚ ÌÂÍÓÚÓ˚ı ÔËÎÓÊÂÌËflı ‰ÎflÓ·ÓÁ̇˜ÂÌËfl ÔÒ‚‰ÓÏÂÚËÍË, Í‚‡ÁˇÒÒÚÓflÌËfl, ÔÓ˜ÚË-ÏÂÚËÍË, ‡ÒÒÚÓflÌËfl, ÍÓÚÓÓ ÏÓÊÂÚ ·˚Ú¸ ·ÂÒÍÓ̘Ì˚Ï, ‡ÒÒÚÓflÌËfl Ò Ó¯Ë·ÍÓÈ Ë Ú.Ô.ìθڇÏÂÚË͇ìθڇÏÂÚËÍÓÈ (ËÎË Ì‡ıËωӂÓÈ ÏÂÚËÍÓÈ) ̇Á˚‚‡ÂÚÒfl ÏÂÚË͇ d ̇ ï,ÍÓÚÓ‡fl Û‰Ó‚ÎÂÚ‚ÓflÂÚ ÛÒËÎÂÌÌÓÈ ‚ÂÒËË Ì‡‚ÂÌÒÚ‚‡ ÚÂÛ„ÓθÌË͇:d(x, y) ≤ max{d(x, z), d(z, y)}‰Îfl ‚ÒÂı x, y, z ∈ X. í‡ÍËÏ Ó·‡ÁÓÏ, ÔÓ Í‡ÈÌÂÈ Ï ‰‚‡ Á̇˜ÂÌËfl ËÁ d(x, y), d(z, y) Ëd(x, z) ÒÓ‚Ô‡‰‡˛Ú.åÂÚË͇ d fl‚ÎflÂÚÒfl ÛθڇÏÂÚËÍÓÈ ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡  ÒÚÂÔÂÌÌÓÂÔÂÓ·‡ÁÓ‚‡ÌË (ÒÏ. „Î. 4) d α fl‚ÎflÂÚÒfl ÏÂÚËÍÓÈ ‰Îfl β·Ó„Ó ÔÓÎÓÊËÚÂθÌÓ„Ó‰ÂÈÒÚ‚ËÚÂθÌÓ„Ó ˜ËÒ· α.
ã˛·‡fl ÛθڇÏÂÚË͇ Û‰Ó‚ÎÂÚ‚ÓflÂÚ Ì‡‚ÂÌÒÚ‚Û˜ÂÚ˚Âı ÚÓ˜ÂÍ. åÂÚË͇ d fl‚ÎflÂÚÒfl ÛθڇÏÂÚËÍÓÈ ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ÓÌÓ fl‚ÎflÂÚÒfl ÏÂÚËÍÓÈ ÔÂÓ·‡ÁÓ‚‡ÌËfl î‡ËÒ‡ (ÒÏ. „Î. 4) ÏÂÚËÍË Ì‡‚ÂÌÒÚ‚‡˜ÂÚ˚Âı ÚÓ˜ÂÍ.åÂÚË͇ ̇‚ÂÌÒÚ‚‡ ˜ÂÚ˚Âı ÚÓ˜ÂÍåÂÚË͇ d ̇ ï Û‰Ó‚ÎÂÚ‚ÓflÂÚ ÛÒÎӂ˲ ̇‚ÂÌÒÚ‚‡ ˜ÂÚ˚Âı ÚÓ˜ÂÍ (ËÎË Ì‡Á˚‚‡ÂÚÒfl ‡‰‰ËÚË‚ÌÓÈ ÏÂÚËÍÓÈ), ÂÒÎË ËÏÂÂÚ ÏÂÒÚÓ ÛÒËÎÂÌ̇fl ‚ÂÒËfl ̇‚ÂÌÒÚ‚‡ÚÂÛ„ÓθÌË͇: ‰Îfl ‚ÒÂı x, y, z, u ∈ Xd(x, y) + d(z, u) ≤ max{d(x, z) + d(y, u), d(x, u) + d(y, z)}.ÑÛ„ËÏË ÒÎÓ‚‡ÏË, ËÁ ÚÂı ÒÛÏÏ d(x, y) + d(z, u), d(x, z) + d(y, u) Ë d(x, u) + d(y, z) ‰‚Â̇˷Óθ¯Ë ÒÓ‚Ô‡‰‡˛Ú.åÂÚË͇ Û‰Ó‚ÎÂÚ‚ÓflÂÚ Ì‡‚ÂÌÒÚ‚Û ˜ÂÚ˚Âı ÚÓ˜ÂÍ ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡Ó̇ fl‚ÎflÂÚÒfl ‰Â‚ӂˉÌÓÈ ÏÂÚËÍÓÈ.ã˛·‡fl ÏÂÚË͇, Û‰Ó‚ÎÂÚ‚Ófl˛˘‡fl ̇‚ÂÌÒÚ‚Û ˜ÂÚ˚Âı ÚÓ˜ÂÍ, fl‚ÎflÂÚÒflÔÚÓÎÂÏ‚ÓÈ ÏÂÚËÍÓÈ Ë l1 -ÏÂÚËÍÓÈ.äÛÒÚ‡ÌËÍÓ‚‡fl ÏÂÚË͇ – ÏÂÚË͇, ‰Îfl ÍÓÚÓÓÈ ‚Ҡ̇‚ÂÌÒÚ‚‡ ˜ÂÚ˚Âı ÚÓ˜ÂÍfl‚Îfl˛ÚÒfl ‡‚ÂÌÒÚ‚‡ÏË, Ú.Â.
‡‚ÂÌÒÚ‚Ó d(x, y) + d(u, z) = d(x, u) + d(y, z) ÒÔ‡‚‰ÎË‚ÓÔË Î˛·˚ı Á̇˜ÂÌËflı u, x, y, z ∈ X.21É·‚‡ 1. 鷢ˠÓÔ‰ÂÎÂÌËflåÂÚË͇ ÓÒ··ÎÂÌÌÓ„Ó Ì‡‚ÂÌÒÚ‚‡ ˜ÂÚ˚Âı ÚÓ˜ÂÍåÂÚË͇ d ̇ ï Û‰Ó‚ÎÂÚ‚ÓflÂÚ ÛÒÎӂ˲ ÓÒ··ÎÂÌÌÓ„Ó Ì‡‚ÂÌÒÚ‚‡ ˜ÂÚ˚ÂıÚÓ˜ÂÍ, ÂÒÎË, ‰Îfl ‚ÒÂı x, y, z ∈ X ËÁ ÚÂı ÒÛÏÏd(x, y) + d(z, u), d(x, z) + d(y, u), d(x, u) + d(y, z)ÔÓ Í‡ÈÌÂÈ Ï ‰‚ (Ì ӷflÁ‡ÚÂθÌÓ Ì‡Ë·Óθ¯ËÂ) ÒÓ‚Ô‡‰‡˛Ú.åÂÚË͇ Û‰Ó‚ÎÂÚ‚ÓflÂÚ ÓÒ··ÎÂÌÌÓÏÛ Ì‡‚ÂÌÒÚ‚Û ˜ÂÚ˚Âı ÚÓ˜ÂÍ ÚÓ„‰‡ ËÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ Ó̇ fl‚ÎflÂÚÒfl ÓÒ··ÎÂÌÌÓÈ ‰Â‚ӂˉÌÓÈ ÏÂÚËÍÓÈ.␦-„ËÔ·Ó΢ÂÒ͇fl ÏÂÚË͇ÖÒÎË δ ≥ 0, ÚÓ ÏÂÚË͇ d ̇ ÏÌÓÊÂÒÚ‚Â ï ̇Á˚‚‡ÂÚÒfl ␦-„ËÔ·Ó΢ÂÒÍÓÈ, ÂÒÎËÓ̇ Û‰Ó‚ÎÂÚ‚ÓflÂÚ ␦-„ËÔ·Ó΢ÂÒÍÓÏÛ Ì‡‚ÂÌÒÚ‚Û ÉÓÏÓ‚‡ (¢ ӉÌÓ ÓÒ··ÎÂÌˠ̇‚ÂÌÒÚ‚‡ ˜ÂÚ˚Âı ÚÓ˜ÂÍ): ‰Îfl ‚ÒÂı x, y, z, u ∈ Xd(x, y) + d(z, u) ≤ 2δ + max{d(x, z) + d(y, u), d(x, u) + d(y, z)}.åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) fl‚ÎflÂÚÒfl δ-„ËÔ·Ó΢ÂÒÍËÏ ÚÓ„‰‡ Ë ÚÓθÍÓÚÓ„‰‡, ÍÓ„‰‡{}( x. y) x 0 ≥ min ( x.z ) x 0 , ( y.z ) x 0 − δ1( d ( x 0 , x ) + d ( x 0 , y) − d ( x, y)) –2ÔÓËÁ‚‰ÂÌË ÉÓÏÓ‚‡ ÚÓ˜ÂÍ ı Ë Û ËÁ ï ÓÚÌÓÒËÚÂθÌÓ ·‡ÁÓ‚ÓÈ ÚÓ˜ÍË x 0 ∈ X.åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (ï, d) fl‚ÎflÂÚÒfl 0-„ËÔ·Ó΢ÂÒÍËÏ ÚÓ„‰‡ Ë ÚÓθÍÓÚÓ„‰‡, ÍÓ„‰‡ d Û‰Ó‚ÎÂÚ‚ÓflÂÚ Ì‡‚ÂÌÒÚ‚Û ˜ÂÚ˚Âı ÚÓ˜ÂÍ.
ä‡Ê‰Ó ӄ‡Ì˘ÂÌÌÓÂÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, Ëϲ˘Â ‰Ë‡ÏÂÚ D, fl‚ÎflÂÚÒfl D-„ËÔ·Ó΢ÂÒÍËÏ. nÏÂÌÓ „ËÔ·Ó΢ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó fl‚ÎflÂÚÒfl ln 3-„ËÔ·Ó΢ÂÒÍËÏ.‰Îfl ‚ÒÂı x, y, z ∈ X Ë ‰Îfl β·Ó„Ó x0 ∈ X, „‰Â ( x, y) x 0 =èÓ‰Ó·ÌÓÒÚ¸ ÔÓËÁ‚‰ÂÌËfl ÉÓÏÓ‚‡èÛÒÚ¸ (ï, d) – ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ò ÙËÍÒËÓ‚‡ÌÌÓÈ ÚÓ˜ÍÓÈ x0 ∈ X.èÓ‰Ó·ÌÓÒÚ¸˛ ÔÓËÁ‚‰ÂÌËfl ÉÓÏÓ‚‡ (ËÎË ÔÓËÁ‚‰ÂÌËÂÏ ÉÓÏÓ‚‡, ÍÓ‚‡Ë‡ÌÚÌÓÒÚ¸˛) (.) x 0 ̇Á˚‚‡ÂÚÒfl ÔÓ‰Ó·ÌÓÒÚ¸ ̇ ï, ÓÔ‰ÂÎflÂχfl ÔÓ ÙÓÏÛÎÂ( x. y ) x 0 =1( d ( x 0 , x ) + d ( x 0 , y) − d ( x, y)).2ÖÒÎË (ï, d) fl‚ÎflÂÚÒfl ‰Â‚ÓÏ, ÚÓ ( x. y) x 0 = d ( x 0 [ x, y]).
ÖÒÎË (X,d) –ÔÓÎÛÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó ÏÂ˚, Ú.Â. d(x, y) = µ(x∆y) ‰Îfl ·ÓÂ΂ÓÈ ÏÂ˚ µ ̇ï , ÚÓ (x.y)ø = µ(x ∩ y). ÖÒÎË d fl‚ÎflÂÚÒfl ‡ÒÒÚÓflÌËÂÏ ÓÚˈ‡ÚÂθÌÓ„Ó ÚËÔ‡, Ú.Â.d ( x, y) = d E2 ( x, y) ‰Îfl ÔÓ‰ÏÌÓÊÂÒÚ‚‡ ï ‚ÍÎˉӂ‡ ÔÓÒÚ‡ÌÒÚ‚‡ n, ÚÓ (ı.Û)0 ·Û‰ÂÚÓ·˚˜Ì˚Ï Ò͇ÎflÌ˚Ï ÔÓËÁ‚‰ÂÌËÂÏ Ì‡ n (ÒÏ. åÂÚË͇ ÔÂÓ·‡ÁÓ‚‡ÌËfl î‡ËÒ‡,„Î. 4).1.2. éëçéÇçõÖ èéçüíàü, ëÇüáÄççõÖ ë êÄëëíéüçàÖå,à óàëãéÇõÖ àçÇÄêàÄçíõåÂÚ˘ÂÒÍËÈ ¯‡èÛÒÚ¸ (X,d) – ÔÓËÁ‚ÓθÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó.
åÂÚ˘ÂÒÍËÏ ¯‡ÓÏ(ËÎË Á‡ÏÍÌÛÚ˚Ï ÏÂÚ˘ÂÒÍËÏ ¯‡ÓÏ) Ò ˆÂÌÚÓÏ x0 ∈ X Ë ‡‰ËÛÒÓÏ r > 0̇Á˚‚‡ÂÚÒfl ÏÌÓÊÂÒÚ‚Ó B ( x 0 , r ) = {x ∈ X : d ( x 0 , x ) ≤ r}. éÚÍ˚Ú˚Ï ÏÂÚ˘ÂÒÍËÏ22ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËȯ‡ÓÏ Ò ˆÂÌÚÓÏ x0 ∈ X Ë ‡‰ËÛÒÓÏ r > 0 ̇Á˚‚‡ÂÚÒfl ÏÌÓÊÂÒÚ‚Ó B(x0, r) == {x0 ∈ X : d(x 0 , x) < r}.åÂÚ˘ÂÒÍÓÈ ÒÙÂÓÈ Ò ˆÂÌÚÓÏ x0 ∈ X Ë ‡‰ËÛÒÓÏ r > 0 ̇Á˚‚‡ÂÚÒfl ÏÌÓÊÂÒÚ‚ÓS(x 0 , r) = {x0 ∈ X : d(x 0 , x) = r}.ÑÎfl ÏÂÚËÍË ÌÓÏ˚ ̇ n-ÏÂÌÓÏ ÌÓÏËÓ‚‡ÌÌÓÏ ‚ÂÍÚÓÌÓÏ ÔÓÒÚ‡ÌÒÚ‚Â(V,|| ⋅ ||) ÏÂÚ˘ÂÒÍËÈ ¯‡ B n = {x ∈ X : x ≤ 1} ̇Á˚‚‡ÂÚÒfl ‰ËÌ˘Ì˚Ï ¯‡ÓÏ, ‡ÏÌÓÊÂÒÚ‚Ó Sn–1 = {x ∈ V : || x || = 1} – ‰ËÌ˘ÌÓÈ ÒÙÂÓÈ (ËÎË Â‰ËÌ˘ÌÓÈ„ËÔÂÒÙÂÓÈ). Ç ‰‚ÛÏÂÌÓÏ ‚ÂÍÚÓÌÓÏ ÔÓÒÚ‡ÌÒÚ‚Â ÏÂÚ˘ÂÒÍËÈ ¯‡ (ÓÚÍ˚Ú˚ÈËÎË Á‡ÏÍÌÛÚ˚È) ̇Á˚‚‡ÂÚÒfl ÏÂÚ˘ÂÒÍËÏ ‰ËÒÍÓÏ (ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ ÓÚÍ˚Ú˚Ï ËÎËÁ‡ÏÍÌÛÚ˚Ï).åÂÚ˘ÂÒ͇fl ÚÓÔÓÎÓ„ËflåÂÚ˘ÂÒ͇fl ÚÓÔÓÎÓ„Ëfl – ÚÓÔÓÎÓ„Ëfl ̇ ï, ÔÓÓʉ‡Âχfl ÏÂÚËÍÓÈ d ̇ ï.ÖÒÎË (X,d) – ÔÓËÁ‚ÓθÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, ÓÔ‰ÂÎËÏ ÓÚÍ˚ÚÓÂÏÌÓÊÂÒÚ‚Ó ‚ ï Í‡Í ÔÓËÁ‚ÓθÌÓ ӷ˙‰ËÌÂÌË (ÍÓ̘ÌÓ„Ó ËÎË ·ÂÒÍÓ̘ÌÓ„Ó˜ËÒ·) ÓÚÍ˚Ú˚ı ÏÂÚ˘ÂÒÍËı ¯‡Ó‚ B(x, r) = {y ∈ X : d(x, y) < r}, x ∈ X, r ∈ ,r > 0.
á‡ÏÍÌÛÚÓ ÏÌÓÊÂÒÚ‚Ó ÓÔ‰ÂÎflÂÚÒfl ÚÂÔ¸ Í‡Í ‰ÓÔÓÎÌÂÌË ÓÚÍ˚ÚÓ„ÓÏÌÓÊÂÒÚ‚‡. åÂÚ˘ÂÒÍÓÈ ÚÓÔÓÎÓ„ËÂÈ Ì‡ (X,d) ̇Á˚‚‡ÂÚÒfl ÏÌÓÊÂÒÚ‚Ó ‚ÒÂıÓÚÍ˚Ú˚ı ‚ ï ÏÌÓÊÂÒÚ‚. íÓÔÓÎӄ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, ÍÓÚÓÓ ÏÓÊÂÚ ·˚Ú¸ÔÓÎÛ˜ÂÌÓ Ú‡ÍËÏ Ó·‡ÁÓÏ ËÁ ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡, ̇Á˚‚‡ÂÚÒfl ÏÂÚËÁÛÂÏ˚ÏÔÓÒÚ‡ÌÒÚ‚ÓÏ.åÂÚËÁ‡ˆËÓÌÌ˚ ÚÂÓÂÏ˚ – ÚÂÓÂÏ˚, ‰‡˛˘Ë ‰ÓÒÚ‡ÚÓ˜Ì˚ ÛÒÎÓ‚Ëfl ÏÂÚËÁÛÂÏÓÒÚË ÚÓÔÓÎӄ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡.ë ‰Û„ÓÈ ÒÚÓÓÌ˚, ÚÂÏËÌ ÏÂÚË͇ Û͇Á˚‚‡ÂÚ ÒÍÓ ̇ Ò‚flÁ¸ Ò ÏÂÓÈ, ÌÂÊÂÎË Ò‡ÒÒÚÓflÌËÂÏ, ÔËÏÂÌËÚÂθÌÓ Í fl‰Û ‚‡ÊÌÂȯËı χÚÂχÚ˘ÂÒÍËı ÓÔ‰ÂÎÂÌËÈ,̇ÔËÏÂ, ‚ ÏÂÚ˘ÂÒÍÓÈ ÚÂÓËË ˜ËÒÂÎ, ÏÂÚ˘ÂÒÍÓÈ ÚÂÓËË ÙÛÌ͈ËÈ, ÏÂÚ˘ÂÒÍÓÈ Ú‡ÌÁËÚË‚ÌÓÒÚË.á‡ÏÍÌÛÚ˚È ÏÂÚ˘ÂÒÍËÈ ËÌÚ‚‡ÎèÛÒÚ¸ x, Û ∈ X – ‰‚ ‡Á΢Ì˚ ÚÓ˜ÍË ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d).
á‡ÏÍÌÛÚ˚Ï ÏÂÚ˘ÂÒÍËÏ ËÌÚ‚‡ÎÓÏ ÏÂÊ‰Û ı Ë Û Ì‡Á˚‚‡ÂÚÒfl ÏÌÓÊÂÒÚ‚ÓI(x, y) = {z ∈ X : d(x, y) = d(x, z) + d(z, y)}.éÒÌÓ‚ÌÓÈ „‡Ù ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡éÒÌÓ‚ÌÓÈ „‡Ù (ËÎË „‡Ù ÒÓÒ‰ÒÚ‚‡) ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) – „‡Ù ÒÏÌÓÊÂÒÚ‚ÓÏ ‚¯ËÌ ï, ‚ ÍÓÚÓÓÏ ıÛ fl‚ÎflÂÚÒfl ·ÓÏ, ÂÒÎË I(x, y) = {x, y}, Ú.Â. ÌÂÒÛ˘ÂÒÚ‚ÛÂÚ ÚÂÚ¸ÂÈ ÚÓ˜ÍË z ∈ X, ‰Îfl ÍÓÚÓÓÈ ‚˚ÔÓÎÌflÎÓÒ¸ ·˚ ‡‚ÂÌÒÚ‚Ód(x, y) = d(x, z) + d(z, y).åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, ÏÓÌÓÚÓÌÌÓ ÓÚÌÓÒËÚÂθÌÓ ‡ÒÒÚÓflÌËflåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl ÔÓÒÚ‡ÌÒÚ‚ÓÏ, ÏÓÌÓÚÓÌÌ˚ÏÓÚÌÓÒËÚÂθÌÓ ‡ÒÒÚÓflÌËfl, ÂÒÎË ‰Îfl β·Ó„Ó ËÌÚ‚‡Î‡ Ë ÒÛ˘ÂÒÚ‚ÛÂÚ I(x, x')Ë y ∈ X\I(x, x') ÒÛ˘ÂÒÚ‚ÛÂÚ x" ∈ X(x, x') Ú‡ÍÓ ˜ÚÓ d(y, x") > d(x, x').åÂÚ˘ÂÒÍËÈ ÚÂÛ„ÓθÌËÍíË ‡Á΢Ì˚ ÚÓ˜ÍË x, y, z ∈ X ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) Ó·‡ÁÛ˛ÚÏÂÚ˘ÂÒÍËÈ ÚÂÛ„ÓθÌËÍ, ÂÒÎË Á‡ÏÍÌÛÚ˚ ÏÂÚ˘ÂÒÍË ËÌÚ‚‡Î˚ I (x, y), I(z, x)Ë I(z, x) ÔÂÂÒÂ͇˛ÚÒfl ÚÓθÍÓ ‚ Ó·˘Ëı ÍÓ̈‚˚ı ÚӘ͇ı.É·‚‡ 1.
鷢ˠÓÔ‰ÂÎÂÌËfl23åÓ‰ÛÎflÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚ÓåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl ÏÓ‰ÛÎflÌ˚Ï, ÂÒÎË ‰Îfl β·˚ı ÚÂı‡Á΢Ì˚ı ÚÓ˜ÂÍ x, y, z ∈ X ÒÛ˘ÂÒÚ‚ÛÂÚ u ∈ I(x, y) ∩ I(y, z) ∩ I(z, x).ç ÒΉÛÂÚ Òϯ˂‡Ú¸ ˝ÚÓ Ò ÏÓ‰ÛÎflÌ˚Ï ‡ÒÒÚÓflÌËÂÏ (ÒÏ. „Î. 10) Ë ÏÂÚËÍÓÈÏÓ‰ÛÎ˛Ò‡ (ÒÏ. „Î. 6).åÂÚ˘ÂÒÍËÈ ˜ÂÚ˚ÂıÛ„ÓθÌËÍóÂÚ˚ ‡Á΢Ì˚ ÚÓ˜ÍË x, y, z, u ∈ X ÔÓËÁ‚ÓθÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) Ó·‡ÁÛ˛Ú ÏÂÚ˘ÂÒÍËÈ ˜ÂÚ˚ÂıÛ„ÓθÌËÍ, ÂÒÎË x, z ∈ I(y, u)Ë y , u ∈ I(x, z). ÑÎfl Ú‡ÍÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ˜ÂÚ˚ÂıÛ„ÓθÌË͇ ·Û‰ÛÚ ËÏÂÚ¸ ÏÂÒÚÓ‡‚ÂÌÒÚ‚‡ d(x, y) = d(z, u) Ë d(x, u) = d(y, z).åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl Ò··Ó ÒÙ¢ÂÒÍËÏ, ÂÒÎË ‰Îfl β·˚ıÚÂı ‡Á΢Ì˚ı ÚÓ˜ÂÍ x, y, z ∈ X Ò y ∈ I(x, z) ÒÛ˘ÂÒÚ‚ÛÂÚ u ∈ X, Ú‡ÍÓ ˜ÚÓx, y, z, u Ó·‡ÁÛ˛Ú ÏÂÚ˘ÂÒÍËÈ ˜ÂÚ˚ÂıÛ„ÓθÌËÍ.ë‚flÁÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚ÓåÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) ̇Á˚‚‡ÂÚÒfl Ò‚flÁÌ˚Ï, ÂÒÎË Â„Ó ÌÂθÁfl ‡Á·Ëڸ̇ ‰‚‡ ÌÂÔÛÒÚ˚ı ÓÚÍ˚Ú˚ı ÏÌÓÊÂÒÚ‚‡ (ÒÏ.
ë‚flÁÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó, „Î. 2).ÅÓΠÒËθÌ˚Ï Ò‚ÓÈÒÚ‚ÓÏ fl‚ÎflÂÚÒfl ÔÛÚ¸ – Ò‚flÁÌÓÒÚ¸, ÔË ÍÓÚÓÓÈ Î˛·˚ ‰‚ÂÚÓ˜ÍË ÏÓ„ÛÚ ·˚Ú¸ ÒÓ‰ËÌÂÌ˚ ÔÛÚÂÏ.åÂÚ˘ÂÒ͇fl ÍË‚‡flåÂÚ˘ÂÒ͇fl ÍË‚‡fl (ËÎË ÔÓÒÚÓ ÍË‚‡fl) γ ‚ ÏÂÚ˘ÂÒÍÓÏ ÔÓÒÚ‡ÌÒÚ‚Â (X,d)Ô‰ÒÚ‡‚ÎflÂÚ ÒÓ·ÓÈ ÌÂÔÂ˚‚ÌÓ ÓÚÓ·‡ÊÂÌË γ : I → X ËÌÚ‚‡Î‡ I ËÁ ‚ ï .äË‚‡fl ̇Á˚‚‡ÂÚÒfl ‰Û„ÓÈ (ËÎË ÔÛÚÂÏ, ÔÓÒÚÓÈ ÍË‚ÓÈ), ÂÒÎË Ó̇ fl‚ÎflÂÚÒflËÌ˙ÂÍÚË‚ÌÓÈ. äË‚‡fl γ : [a, b] → X ̇Á˚‚‡ÂÚÒfl ÊÓ‰‡ÌÓ‚ÓÈ ÍË‚ÓÈ (ËÎË ÔÓÒÚÓÈÁ‡ÏÍÌÛÚÓÈ ÍË‚ÓÈ), ÂÒÎË Ó̇ Ì ÔÂÂÒÂ͇ÂÚ Ò‡ÏÛ Ò·fl Ë γ(a) = γ(b).ÑÎË̇ l(γ) ÍË‚ÓÈ γ : [a, b] → X ÓÔ‰ÂÎflÂÚÒfl ÙÓÏÛÎÓÈl( γ ) = sup d ( γ (ti ), γ (ti −1 )) : n ∈ , a = t0 < ... < tn = b .1≤ i ≤ n∑ëÔflÏÎflÂχfl ÍË‚‡fl – ˝ÚÓ ÍË‚‡fl ÍÓ̘ÌÓÈ ‰ÎËÌ˚. åÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó(X,d), ‚ ÍÓÚÓÓÏ Í‡Ê‰˚ ‰‚ ÚÓ˜ÍË ÏÓ„ÛÚ ·˚Ú¸ ÒÓ‰ËÌÂÌ˚ ÒÔflÏÎflÂÏÓÈ ÍË‚ÓÈ,̇Á˚‚‡ÂÚÒfl ë-Í‚‡ÁË‚˚ÔÛÍÎ˚Ï ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ ÔË Ì‡Î˘ËË ÌÂÍÓÚÓÓÈÍÓÌÒÚ‡ÌÚ˚ C ≥ 1, Ú‡ÍÓÈ ˜ÚÓ Í‡Ê‰‡fl Ô‡‡ x, y ∈ X ÏÓÊÂÚ ·˚Ú¸ ÒÓ‰ËÌÂ̇ÒÔflÏÎflÂÏÓÈ ÍË‚ÓÈ Ï‡ÍÒËχθÌÓÈ ‰ÎËÌ˚ ëd(x, y).
ÖÒÎË ë = 1, ÚÓ ˝Ú‡ ‰ÎË̇ ‡‚̇d(x, y), Ú.Â. ÔÓÒÚ‡ÌÒÚ‚Ó (X,d) fl‚ÎflÂÚÒfl „ÂÓ‰ÂÁ˘ÂÒÍËÏ (ËÎË ÒÚÓ„Ó ‚ÌÛÚÂÌÌËÏ)ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ.ÉÂÓ‰ÂÁ˘ÂÒ͇flÑÎfl ÔÓËÁ‚ÓθÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) „ÂÓ‰ÂÁ˘ÂÒÍÓÈ Ì‡Á˚‚‡ÂÚÒflÎÓ͇θÌÓ Í‡Ú˜‡È¯‡fl ÏÂÚ˘ÂÒ͇fl ÍË‚‡fl, Ú.Â. ÎÓ͇θÌÓ ËÁÓÏÂÚ˘ÂÒÍÓ‚ÎÓÊÂÌË ‚ ï.ÉÂÓ‰ÂÁ˘ÂÒÍËÏ ÓÚÂÁÍÓÏ (ËÎË Í‡Ú˜‡È¯ËÏ ÔÛÚÂÏ) [x, y] ÓÚ ı ‰Ó Û fl‚ÎflÂÚÒflËÁÓÏÂÚ˘ÂÒÍÓ ‚ÎÓÊÂÌË γ : [a, b] → X Ò γ(a) = x Ë γ(b) = y.åÂÚ˘ÂÒ͇fl Ôflχfl – „ÂÓ‰ÂÁ˘ÂÒ͇fl, ÍÓÚÓ‡fl fl‚ÎflÂÚÒfl ÏËÌËχθÌÓÈ ÏÂʉۉ‚ÛÏfl β·˚ÏË Â ÚӘ͇ÏË; Ó̇ Ô‰ÒÚ‡‚ÎflÂÚ ÒÓ·ÓÈ ËÁÓÏÂÚ˘ÂÒÍÓ ‚ÎÓÊÂÌË‚ÒÂ„Ó ‚ ï .
åÂÚ˘ÂÒÍËÈ ÎÛ˜ Ë ÏÂÚ˘ÂÒÍËÈ ·Óθ¯ÓÈ ÍÛ„ Ô‰ÒÚ‡‚Îfl˛Ú ÒÓ·ÓÈËÁÓÏÂÚ˘ÂÒÍË ‚ÎÓÊÂÌËfl ‚ ï ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ ÔÓÎÛÔflÏÓÈ ≥0 Ë ÓÍÛÊÌÓÒÚËS(0, r).24ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈÉÂÓ‰ÂÁ˘ÂÒÍËÏ ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ Ì‡Á˚‚‡ÂÚÒfl ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó, ‚ ÍÓÚÓÓÏ ‰‚ β·˚ ÚÓ˜ÍË ÒÓ‰ËÌÂÌ˚ „ÂÓ‰ÂÁ˘ÂÒÍËÏ ÓÚÂÁÍÓÏ. éÌÓ̇Á˚‚‡ÂÚÒfl „ÂÓ‰ÂÁ˘ÂÒÍË ÔÓÎÌ˚Ï, ÂÒÎË Í‡Ê‰˚È Ú‡ÍÓÈ ÓÚÂÁÓÍ fl‚ÎflÂÚÒfl ÔÓ‰‰Û„ÓÈÏÂÚ˘ÂÒÍÓÈ ÔflÏÓÈ.ÉÂÓ‰ÂÁ˘ÂÒ͇fl ‚˚ÔÛÍÎÓÒÚ¸ÑÎfl ÔÓËÁ‚ÓθÌÓ„Ó „ÂÓ‰ÂÁ˘ÂÒÍÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X,d) Ë ÔÓ‰ÏÌÓÊÂÒÚ‚‡ å ⊂ X ÏÌÓÊÂÒÚ‚Ó å ̇Á˚‚‡ÂÚÒfl „ÂÓ‰ÂÁ˘ÂÒÍË ‚˚ÔÛÍÎ˚Ï (ËÎË‚˚ÔÛÍÎ˚Ï), ÂÒÎË ‰Îfl β·˚ı ‰‚Ûı ÚÓ˜ÂÍ ËÁ å ÒÛ˘ÂÒÚ‚ÛÂÚ ÒÓ‰ËÌfl˛˘ËÈ Ëı„ÂÓ‰ÂÁ˘ÂÒÍËÈ ÓÚÂÁÓÍ, ÍÓÚÓ˚È ÔÓÎÌÓÒÚ¸˛ ÔË̇‰ÎÂÊËÚ å; ÓÌÓ Ì‡Á˚‚‡ÂÚÒflÎÓ͇θÌÓ ‚˚ÔÛÍÎ˚Ï, ÂÒÎË Ú‡ÍÓÈ ÓÚÂÁÓÍ ÒÛ˘ÂÒÚ‚ÛÂÚ ‰Îfl β·˚ı ‰‚Ûı ‰ÓÒÚ‡ÚÓ˜ÌÓ·ÎËÁÍËı ÚÓ˜ÂÍ ÏÌÓÊÂÒÚ‚‡ å.ꇉËÛÒÓÏ ËÌ˙ÂÍÚË‚ÌÓÒÚË ÏÌÓÊÂÒÚ‚‡ å ̇Á˚‚‡ÂÚÒfl ̇ËÏÂ̸¯Â ˜ËÒÎÓ r, Ú‡ÍÓ˜ÚÓ ‰Îfl ‰‚Ûı β·˚ı ÚÓ˜ÂÍ ËÁ å, ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÍÓÚÓ˚ÏË <r, ÒÛ˘ÂÒÚ‚ÛÂÚ‰ËÌÒÚ‚ÂÌÌ˚È ÒÓ‰ËÌfl˛˘ËÈ Ëı „ÂÓ‰ÂÁ˘ÂÒÍËÈ ÓÚÂÁÓÍ, ÍÓÚÓ˚È ÔÓÎÌÓÒÚ¸˛ÔË̇‰ÎÂÊËÚ å.åÌÓÊÂÒÚ‚Ó å ̇Á˚‚‡ÂÚÒfl ‚ÔÓÎÌ ‚˚ÔÛÍÎ˚Ï, ÂÒÎË ‰Îfl β·˚ı ‰‚Ûı Â„Ó ÚÓ˜ÂÍ͇ʉ˚È ÒÓ‰ËÌfl˛˘ËÈ Ëı „ÂÓ‰ÂÁ˘ÂÒÍËÈ ÓÚÂÁÓÍ ÔÓÎÌÓÒÚ¸˛ ÔË̇‰ÎÂÊËÚ å.