Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf), страница 15
Описание файла
PDF-файл из архива "Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 15 страницы из PDF
ÌÂÔÛÒÚÓÈ ÒÓ‚ÓÍÛÔÌÓÒÚ¸˛ ÒÂÏÂÈÒÚ‚ ÔÓ‰ÏÌÓÊÂÒÚ‚ÏÌÓÊÂÒÚ‚‡ ï, ̇Á˚‚‡ÂÏ˚ı ÒÂÏÂÈÒÚ‚‡ÏË ÔË·ÎËÊÂÌÌÓÒÚË, ÒÓ ÒÎÂ‰Û˛˘ËÏË Ò‚ÓÈÒÚ‚‡ÏË:1) ͇ʉÓ ÒÂÏÂÈÒÚ‚Ó, ÔÓ‰‡Á‰ÂÎfl˛˘Â ÒÂÏÂÈÒÚ‚Ó Ó ÔË·ÎËÊÂÌÌÓÒÚË, fl‚ÎflÂÚÒflÒÂÏÂÈÒÚ‚ÓÏ ÔË·ÎËÊÂÌÌÓÒÚË;2) ͇ʉÓ ÒÂÏÂÈÒÚ‚Ó Ò ÌÂÔÛÒÚ˚Ï ÔÂÂÒ˜ÂÌËÂÏ fl‚ÎflÂÚÒfl ÒÂÏÂÈÒÚ‚ÓÏ ÔË·ÎËÊÂÌÌÓÒÚË;É·‚‡ 3. é·Ó·˘ÂÌËfl ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚653) V ∈ , ÂÒÎË {cl(A): A ∈ V} ∈ , „‰Â Òl(A) = {x ∈ X : {{x}, A ∈ };4) 0/ ∈, ‚ ÚÓ ‚ÂÏfl Í‡Í ÏÌÓÊÂÒÚ‚Ó ê(ï) ‚ÒÂı ÔÓ‰ÏÌÓÊÂÒÚ‚ ÏÌÓÊÂÒÚ‚‡ ï ÌÂfl‚ÎflÂÚÒfl ÒÂÏÂÈÒÚ‚ÓÏ ÔË·ÎËÊÂÌÌÓÒÚË;5) ÂÒÎË {A ∪ B : A ∈ ∞, B ∈ ε ∈ , ÚÓ ∞ ∈ ËÎË ε ∈ .ꇂÌÓÏÂÌ˚ ÔÓÒÚ‡ÌÒÚ‚‡ fl‚Îfl˛ÚÒfl ‚ ÚÓ˜ÌÓÒÚË Ô‡‡ÍÓÏÔ‡ÍÚÌ˚ÏË ÔÓÒÚ‡ÌÒÚ‚‡ÏË ÔË·ÎËÊÂÌÌÓÒÚË.èÓÒÚ‡ÌÒÚ‚Ó ÔË·ÎËÊÂÌËÈùÚË ÚÓÔÓÎӄ˘ÂÒÍË ÔÓÒÚ‡ÌÒÚ‚‡ ‰‡˛Ú Ó·Ó·˘ÂÌËfl ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚,ÓÒÌÓ‚‡ÌÌ˚ ̇ ‡ÒÒÚÓflÌËË ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ.èÓÒÚ‡ÌÒÚ‚Ó ÔË·ÎËÊÂÌËÈ (ãÓÛ, 1989) ÂÒÚ¸ Ô‡‡ (ï, D), „‰Â ï – ÌÂÍÓÚÓÓ ÏÌÓÊÂÒÚ‚Ó, ‡ D – ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ, Ú.Â. ÙÛÌ͈ËflX × P(X) → [0, ∞] („‰Â ê(ï) fl‚ÎflÂÚÒfl ÏÌÓÊÂÒÚ‚ÓÏ ‚ÒÂı ÔÓ‰ÏÌÓÊÂÒÚ‚ ï), Û‰Ó‚ÎÂÚ‚Ófl˛˘‡fl ‰Îfl ‚ÒÂı x ∈ X Ë ‚ÒÂı A, B ∈ P(X) ÒÎÂ‰Û˛˘ËÏ ÛÒÎÓ‚ËflÏ:1) D(x,{x}) = 0;2) D(x,{x}) = ∞;3) D(x, A ∪ B) = min{D(x, A), D(x, B)};4) D(x, A) ≤ D(x, A ε) + ε ‰Îfl β·˚ı ε ∈ [0, ∞], „‰Â Aε = {x : D(x, A) ≤ ε} ÂÒÚ¸ "ε-¯‡"Ò ˆÂÌÚÓÏ ‚ ı.ã˛·Ó ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó (ï, d) (·ÓΠÚÓ„Ó, β·Ó ‡Ò¯ËÂÌÌÓÂÍ‚‡ÁËÔÓÎÛÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó) ÂÒÚ¸ ÔÓÒÚ‡ÌÒÚ‚Ó ÔË·ÎËÊÂÌËÈ Ò D(x, A),fl‚Îfl˛˘ËÏÒfl Ó·˚˜Ì˚Ï ‡ÒÒÚÓflÌËÂÏ ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ.ÖÒÎË Ï˚ ËÏÂÂÏ ÎÓ͇θÌÓ ÍÓÏÔ‡ÍÚÌÓ ÒÂÔ‡‡·ÂθÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó(ï, d) Ë ÒÂÏÂÈÒÚ‚Ó Â„Ó ÌÂÔÛÒÚ˚ı Á‡ÏÍÌÛÚ˚ı ÔÓ‰ÏÌÓÊÂÒÚ‚, ÚÓ ÙÛÌ͈Ëfl Å˝‰‰ÎË–åÓΘ‡ÌÓ‚‡ ‰‡ÂÚ ËÌÒÚÛÏÂÌÚ ‰Îfl ‰Û„Ó„Ó Ó·Ó·˘ÂÌËfl.
ùÚÓ – ÙÛÌ͈Ëfl D : X × → ,ÍÓÚÓ‡fl fl‚ÎflÂÚÒfl ÌËÊÌÂÈ ÔÓÎÛÌÂÔÂ˚‚ÌÓÈ ÔÓ ÓÚÌÓ¯ÂÌ˲ Í Â Ô‚ÓÈ ÔÂÂÏÂÌÌÓÈ, ËÁÏÂÂÌÌÓÈ ÓÚÌÓÒËÚÂθÌÓ ‚ÚÓÓÈ, Ë Û‰Ó‚ÎÂÚ‚ÓflÂÚ ÒÎÂ‰Û˛˘ËÏ ‰‚ÛÏ ÛÒÎÓ‚ËflÏ:F = {x ∈ X : D(x, F) ≤ 0} ‰Îfl F ∈ Ë D(x, F1) ≥ D(x, F2 ) ‰Îfl x ∈ X ‚ÒflÍËÈ ‡Á, ÍÓ„‰‡ F1 ,F2 ∈ Ë F1 ⊂ F2.ÑÓÔÓÎÌËÚÂθÌ˚ ÛÒÎÓ‚Ëfl D(x, {y}) = D(y, {x}) Ë D(x, F) ≤ D(x, {y}) + D({y}F) ‰Îfl‚ÒÂı x, y ∈ X Ë ‚ÒÂı F ∈ ‰‡˛Ú Ì‡Ï ‡Ì‡ÎÓ„Ë ÒËÏÏÂÚËË Ë Ì‡‚ÂÌÒÚ‚‡ÚÂÛ„ÓθÌË͇. ëÎÛ˜‡È D(x, F) = d(x, F) ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ Ó·˚˜ÌÓÏÛ ‡ÒÒÚÓflÌ˲ ÏÂʉÛÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ ‰Îfl ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (ï, d); ÒÎÛ˜‡È D(x, F) = d(x, F)‰Îfl x ∈ X\F Ë D(x, F) = –d(x, F\F) ‰Îfl x ∈ X ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ ÙÛÌ͈ËË ‡ÒÒÚÓflÌËfl ÒÓÁ̇ÍÓÏ („Î. 1).åÂÚ˘ÂÒ͇fl ·ÓÌÓÎÓ„ËflèÛÒÚ¸ ï – ÚÓÔÓÎӄ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó.
ÅÓÌÓÎÓ„ËÂÈ Ì‡ ï ·Û‰ÂÚ Î˛·ÓÂÒÂÏÂÈÒÚ‚Ó ÒÓ·ÒÚ‚ÂÌÌ˚ı ÔÓ‰ÏÌÓÊÂÒÚ‚ Ä ÏÌÓÊÂÒÚ‚‡ ï, ‰Îfl ÍÓÚÓ˚ı ‚˚ÔÓÎÌfl˛ÚÒflÒÎÂ‰Û˛˘Ë ÛÒÎÓ‚Ëfl:1) ∪ A∈ A = X;2) fl‚ÎflÂÚÒfl ˉ‡ÎÓÏ, Ú.Â. ÒÓ‰ÂÊËÚ ‚Ò ÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ë ÍÓ̘Ì˚ ӷ˙‰ËÌÂÌËflÂ„Ó Ó·˙ÂÍÚÓ‚;ëÂÏÂÈÒÚ‚Ó fl‚ÎflÂÚÒfl ÏÂÚ˘ÂÒÍÓÈ ·ÓÌÓÎÓ„ËÂÈ ([Beer99]), ÂÒÎË, ·ÓΠÚÓ„Ó,ËÏÂ˛Ú ÏÂÒÚÓ ÛÒÎÓ‚Ëfl;3) ÒÓ‰ÂÊËÚ Ò˜ÂÚÌÛ˛ ·‡ÁÛ;4) ‰Îfl β·Ó„Ó Ä ∈ ÒÛ˘ÂÒÚ‚ÛÂÚ Ä ∈ , Ú‡ÍÓ ˜ÚÓ Á‡Ï˚͇ÌË ÏÌÓÊÂÒÚ‚‡ ÄÒÓ‚Ô‡‰‡ÂÚ Ò ÏÌÓÊÂÒÚ‚ÓÏ ‚ÌÛÚÂÌÌËı ÚÓ˜ÂÍ ÏÌÓÊÂÒÚ‚‡ Ä.åÂÚ˘ÂÒ͇fl ·ÓÌÓÎÓ„Ëfl ̇Á˚‚‡ÂÚÒfl Ú˂ˇθÌÓÈ, ÂÒÎË ÂÒÚ¸ ÏÌÓÊÂÒÚ‚Ó ê(ï)‚ÒÂı ÔÓ‰ÏÌÓÊÂÒÚ‚ ÏÌÓÊÂÒÚ‚‡ ï; ڇ͇fl ÏÂÚ˘ÂÒ͇fl ·ÓÌÓÎÓ„Ëfl ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ66ó‡ÒÚ¸ I. å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈÒÂÏÂÈÒÚ‚Û Ó„‡Ì˘ÂÌÌ˚ı ÏÌÓÊÂÒÚ‚ ÌÂÍÓÚÓÓÈ Ó„‡Ì˘ÂÌÌÓÈ ÏÂÚËÍË. ÑÎfl ‚ÒflÍÓ„ÓÌÂÍÓÏÔ‡ÍÚÌÓ„Ó ÏÂÚËÁÛÂÏÓ„Ó ÚÓÔÓÎӄ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ ï ÒÛ˘ÂÒÚ‚ÛÂÚ ÌÂÓ„‡Ì˘ÂÌ̇fl ÏÂÚË͇, ÒÓ‚ÏÂÒÚËχfl Ò ‰‡ÌÌÓÈ ÚÓÔÓÎÓ„ËÂÈ.
çÂÚ˂ˇθ̇fl ÏÂÚ˘ÂÒ͇fl·ÓÌÓÎÓ„Ëfl ̇ Ú‡ÍÓÏ ÔÓÒÚ‡ÌÒÚ‚Â ï ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ ÒÂÏÂÈÒÚ‚Û Ó„‡Ì˘ÂÌÌ˚ıÔÓ‰ÏÌÓÊÂÒÚ‚ ÔÓ ÓÚÌÓ¯ÂÌ˲ Í ÌÂÍÓÂÈ ÌÂÓ„‡Ì˘ÂÌÌÓÈ ÏÂÚËÍÂ. çÂÍÓÏÔ‡ÍÚÌÓÂÏÂÚËÁÛÂÏÓ ÚÓÔÓÎӄ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó ï ‰ÓÔÛÒ͇ÂÚ ·ÂÒÍÓ̘ÌÓ ÏÌÓ„ÓÌÂÚ˂ˇθÌ˚ı ÏÂÚ˘ÂÒÍËı ·ÓÌÓÎÓ„ËÈ.3.4. áÄ èêÖÑÖãÄåà óàëÖãÇÂÓflÚÌÓÒÚÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚ÓèÓÌflÚË ‚ÂÓflÚÌÓÒÚÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ fl‚ÎflÂÚÒfl Ó·Ó·˘ÂÌËÂÏÔÓÌflÚËfl ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (ÒÏ., ̇ÔËÏÂ, [ScSk83]) ÔÓ ‰‚ÛÏ Ì‡Ô‡‚ÎÂÌËflÏ: ‡ÒÒÚÓflÌËfl ÒÚ‡ÌÓ‚flÚÒfl ‡ÒÔ‰ÂÎÂÌËflÏË ‚ÂÓflÚÌÓÒÚË Ë ÒÛÏχ ‚̇‚ÂÌÒÚ‚Â ÚÂÛ„ÓθÌË͇ Ô‚‡˘‡ÂÚÒfl ‚ ÓÔ‡ˆË˛ ÚÂÛ„ÓθÌË͇.îÓχθÌÓ, ÔÛÒÚ¸ Ä – ÏÌÓÊÂÒÚ‚Ó ‚ÒÂı ÙÛÌ͈ËÈ ‡ÒÔ‰ÂÎÂÌËfl ‚ÂÓflÚÌÓÒÚË,ÌÂÒÛ˘Â ÏÌÓÊÂÒÚ‚Ó ÍÓÚÓÓ„Ó Ì‡ıÓ‰ËÚÒfl ‚ [0, ∞].
ÑÎfl β·Ó„Ó a ∈ [0, ∞] Á‡‰‡‰ËÏεa ∈ A Í‡Í ε a (x) = 1, ÂÒÎË x > a ËÎË x = ∞ Ë ε a = 0, Ë̇˜Â. îÛÌ͈ËË ‚ Ä ·Û‰ÛÚÛÔÓfl‰Ó˜ÂÌ˚: ·Û‰ÂÏ Ò˜ËÚ‡Ú¸, ˜ÚÓ F ≤ G, ÂÒÎË F(x) ≤ G(x) ‰Îfl ‚ÒÂı x ≥ 0. äÓÏÏÛÚ‡Ú˂̇fl Ë ‡ÒÒӈˇÚ˂̇fl ÓÔ‡ˆËfl τ ̇ Ä Ì‡Á˚‚‡ÂÚÒfl ÓÔ‡ˆËÂÈ ÚÂÛ„ÓθÌË͇,ÂÒÎË Ó̇ Û‰Ó‚ÎÂÚ‚ÓflÂÚ ÛÒÎӂ˲ τ(F, ε0 ) = F ‰Îfl β·Ó„Ó F ∈ A, Ë τ(F, E) ≤ τ(G, H),ÂÒÎË Ö ≤ G, F ≤ ç.ÇÂÓflÚÌÓÒÚÌÓ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó – ˝ÚÓ ÚÓÈ͇ (ï, d, τ), „‰Â ï –ÏÌÓÊÂÒÚ‚Ó, d – ÙÛÌ͈Ëfl X × X → A Ë τ – ÓÔ‡ˆËfl ÚÂÛ„ÓθÌË͇, ڇ͇fl ˜ÚÓ ‰Îflβ·˚ı p, q, r ∈ X ‚˚ÔÓÎÌfl˛ÚÒfl ÛÒÎÓ‚Ëfl:1) d(p, q) = ε 0 ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ p = q;2) d(p, q) = d(q, p);3) d(p, r) ≤ τ(d(p, q), d(q, r)).燂ÂÌÒÚ‚Ó 3 ÒÚ‡ÌÓ‚ËÚÒfl ̇‚ÂÌÒÚ‚ÓÏ ÚÂÛ„ÓθÌË͇, ÂÒÎË τ fl‚ÎflÂÚÒfl Ó·˚˜Ì˚ÏÒÎÓÊÂÌËÂÏ Ì‡ .ÑÎfl β·Ó„Ó ı ≥ 0 Á̇˜ÂÌË d(p, q) ‚ ÚӘ͠ı ÏÓÊÂÚ ·˚Ú¸ ËÌÚÂÔÂÚËÓ‚‡ÌÓ Í‡Í"‚ÂÓflÚÌÓÒÚ¸ ÚÓ„Ó, ˜ÚÓ ‡ÒÒÚÓflÌË ÏÂÊ‰Û Ë q ÏÂ̸¯Â, ˜ÂÏ ı"; åÂÌ„Â Ô‰ÎÓÊË΂ 1942 „. ̇Á˚‚‡Ú¸ ‰‡ÌÌÓ ÔÓÌflÚË ÒÚ‡ÚËÒÚ˘ÂÒÍËÏ ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒ Ú ‚ Ó Ï .
Ç ˝ÚÓÚ Ê ÔÂËÓ‰ ·˚ÎË ‚‚‰ÂÌ˚ ÔÓÌflÚËfl ̘ÂÚÍÓ ÓÔ‰ÂÎÂÌÌÓ„Ó(‡ÒÔÎ˚‚˜‡ÚÓ„Ó) ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (ÒÏ. Ú‡ÍÊ [Bloc99]).é·Ó·˘ÂÌ̇fl ÏÂÚË͇èÛÒÚ¸ ï – ÔÓËÁ‚ÓθÌÓ ÏÌÓÊÂÒÚ‚Ó. èÛÒÚ¸ (G, +, ≤) – ÛÔÓfl‰Ó˜ÂÌ̇fl ÔÓÎÛ„ÛÔÔ‡(Ì ӷflÁ‡ÚÂθÌÓ ÍÓÏÏÛÚ‡Ú˂̇fl), Ëϲ˘‡fl ̇ËÏÂ̸¯ËÈ ˝ÎÂÏÂÌÚ 0. îÛÌ͈Ëfld : X × X → G ̇Á˚‚‡ÂÚÒfl Ó·Ó·˘ÂÌÌÓÈ ÏÂÚËÍÓÈ, ÂÒÎË ‚˚ÔÓÎÌfl˛ÚÒfl ÒÎÂ‰Û˛˘ËÂÛÒÎÓ‚Ëfl:1) d(x, y) = 0 ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ x = y;2) d(x, y) ≤ d(x, z) + d(z, y) ‰Îfl ‚ÒÂı x, y ∈ X;3) d ( x, y) = d ( y, x ), „‰Â α fl‚ÎflÂÚÒfl ÙËÍÒËÓ‚‡ÌÌ˚Ï ËÌ‚ÓβÚË‚Ì˚Ï ÓÚÓ·‡ÊÂÌËÂÏ G, ÒÓı‡Ìfl˛˘ËÏ ÔÓfl‰ÓÍ.臇 (X, d) ̇Á˚‚‡ÂÚÒfl Ó·Ó·˘ÂÌÌ˚Ï ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ.ÖÒÎË ÛÒÎÓ‚Ë 2 Ë Ú·ӂ‡ÌË "ÚÓθÍÓ ÚÓ„‰‡" ‚ ÛÒÎÓ‚ËË 1 ÒÌËχ˛ÚÒfl, Ï˚ ÔÓÎÛ˜‡ÂÏ Ó·Ó·˘ÂÌÌÓ ‡ÒÒÚÓflÌË d Ë Ó·Ó·˘ÂÌÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó ‡ÒÒÚÓflÌËÈ (X, d).É·‚‡ 3.
é·Ó·˘ÂÌËfl ÏÂÚ˘ÂÒÍËı ÔÓÒÚ‡ÌÒÚ‚67ê‡ÒÒÚÓflÌË ̇ ÔÓÒÚÓÂÌËËÉÛÔÔ‡ äÓÍÒÚ‡ – „ÛÔÔ‡ (W, ⋅,1) ÔÓÓʉ‡Âχfl ˝ÎÂÏÂÌÚ‡ÏË {w1 ,…,wn : ( wi w j )mij= 1,1 ≤ i, j ≤ n}. á‰ÂÒ¸ M = ((m ij)) – χÚˈ‡ äÓÍÒÚ‡, Ú.Â. ÔÓËÁ-‚Óθ̇fl ÒËÏÏÂÚ˘̇fl (n × n)-χÚˈ‡, ڇ͇fl ˜ÚÓ m = 1, a ÓÒڇθÌ˚ Á̇˜ÂÌËfl –ÔÓÎÓÊËÚÂθÌ˚ ˆÂÎ˚ ˜ËÒ· ËÎË ∞. ÑÎË̇ l(x) ˝ÎÂÏÂÌÚ‡ x ∈ W ÂÒÚ¸ ̇ËÏÂ̸¯Â˜ËÒÎÓ ÔÓÓʉ‡˛˘Ëı ÓÔ‡ÚÓÓ‚ w 1 ,…, wn, ÌÂÓ·ıÓ‰ËÏ˚ı ‰Îfl Ô‰ÒÚ‡‚ÎÂÌËfl ı.èÛÒÚ¸ ï – ÔÓËÁ‚ÓθÌÓ ÏÌÓÊÂÒÚ‚Ó (W,⋅,1) – „ÛÔÔ‡ äÓÍÒÚ‡. 臇 (X, d)̇Á˚‚‡ÂÚÒfl ÔÓÒÚÓÂÌËÂÏ Ì‡‰ (W,⋅,1), ÂÒÎË ÙÛÌ͈Ëfl d : X × X → W, ̇Á˚‚‡Âχfl‡ÒÒÚÓflÌËÂÏ Ì‡ ÔÓÒÚÓÂÌËË, ӷ·‰‡ÂÚ ÒÎÂ‰Û˛˘ËÏË Ò‚ÓÈÒÚ‚‡ÏË:1) d(x, y) = 1 ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ x = y;2) d(x, y) = (d(x, y))–1;3) ÓÚÌÓ¯ÂÌË ~i, Á‡‰‡‚‡ÂÏÓ ÛÒÎÓ‚ËÂÏ x ~i y, ÂÒÎË d(x, y) = 1 ËÎË w i, ÂÒÚ¸ ÓÚÌÓ¯ÂÌË ˝Í‚Ë‚‡ÎÂÌÚÌÓÒÚË;4) ‰Îfl ‰‡ÌÌÓ„Ó x ∈ X Ë Í·ÒÒ‡ ˝Í‚Ë‚‡ÎÂÌÚÌÓÒÚË ë ËÁ ~i ÒÛ˘ÂÒÚ‚ÛÂÚ Â‰ËÌÒÚ‚ÂÌÌÓÂx ∈ C, Ú‡ÍÓ ˜ÚÓ d(x, y) ͇ژ‡È¯Â (Ú.Â.
̇ËÏÂ̸¯ÂÈ ‰ÎËÌ˚) Ë d(x, y) = d(x, y)w i ‰Îflβ·Ó„Ó y ∈ C, y ≠ y.ê‡ÒÒÚÓflÌË „‡ÎÂÂË Ì‡ ÔÓÒÚÓÂÌËË d ÂÒÚ¸ Ó·˚˜Ì‡fl ÏÂÚË͇ ̇ ï, Á‡‰‡‚‡ÂχflÍ‡Í l(d(x, y)). ê‡ÒÒÚÓflÌË d – ˝ÚÓ ÏÂÚË͇ ÔÛÚË Ì‡ „‡ÙÂ Ò ÏÌÓÊÂÒÚ‚ÓÏ ‚¯ËÌ ï ËıÛ ‚ ͇˜ÂÒڂ ·‡, ÂÒÎË d(x, y) = w i ‰Îfl ÌÂÍÓÚÓÓ„Ó 1 ≤ i ≤ n.
ê‡ÒÒÚÓflÌË „‡ÎÂÂË Ì‡ÔÓÒÚÓÂÌËË ÂÒÚ¸ ÓÒÓ·˚È ÒÎÛ˜‡È ÏÂÚËÍË „‡ÎÂÂË (͇ÏÂÌÓÈ ÒËÒÚÂÏ˚ ï).ÅÛÎÂ‚Ó ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚ÓÅÛ΂‡ ‡Î„·‡ (ËÎË ·Û΂‡ ¯ÂÚ͇) ÂÒÚ¸ ‰ËÒÚË·ÛÚ˂̇fl ¯ÂÚ͇ (B, ∨, ∧) Ò̇ËÏÂ̸¯ËÏ ˝ÎÂÏÂÌÚÓÏ 0 Ë Ì‡Ë·Óθ¯ËÏ ˝ÎÂÏÂÌÚÓÏ 1, ڇ͇fl ˜ÚÓ Í‡Ê‰˚È ˝ÎÂÏÂÌÚx ∈ B ӷ·‰‡ÂÚ ‰ÓÔÓÎÌËÚÂθÌ˚Ï ˝ÎÂÏÂÌÚÓÏ x, Ú‡ÍËÏ ˜ÚÓ x ∨ x = 1 Ë x ∧ x = 0.èÛÒÚ¸ ï – ÔÓËÁ‚ÓθÌÓ ÏÌÓÊÂÒÚ‚Ó Ë (B, ∨, ∧) – ·Û΂‡ ‡Î„·‡.
臇 (X, d)̇Á˚‚‡ÂÚÒfl ·Û΂˚Ï ÏÂÚ˘ÂÒÍËÏ ÔÓÒÚ‡ÌÒÚ‚ÓÏ Ì‡‰ Ç , ÂÒÎË ÙÛÌ͈Ëfld : X × X → B ӷ·‰‡ÂÚ ÒÎÂ‰Û˛˘ËÏË Ò‚ÓÈÒÚ‚‡ÏË:1) d(x, y) = 0 ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ x = y;2) d(x, y) ≤ d(x, z) ∨ d(z, y) ‰Îfl ‚ÒÂı x, y, z ∈ X.èÓÒÚ‡ÌÒÚ‚Ó Ì‡‰ ‡Î„·ÓÈèÓÒÚ‡ÌÒÚ‚Ó Ì‡‰ ‡Î„·ÓÈ ÂÒÚ¸ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ò ‰ËÙÙÂÂ̈ˇθÌÓ„ÂÓÏÂÚ˘ÂÒÍÓÈ ÒÚÛÍÚÛÓÈ, ÚÓ˜ÍË ÍÓÚÓÓ„Ó ÏÓ„ÛÚ ·˚Ú¸ Ò̇·ÊÂÌ˚ ÍÓÓ‰Ë̇ڇÏËËÁ ÌÂÍÓÚÓÓÈ ‡Î„·˚, Í‡Í Ô‡‚ËÎÓ, ‡ÒÒӈˇÚË‚ÌÓÈ Ë Ò Â‰ËÌ˘Ì˚Ï ˝ÎÂÏÂÌÚÓÏ.åÓ‰Ûθ ̇‰ ‡Î„·ÓÈ fl‚ÎflÂÚÒfl Ó·Ó·˘ÂÌËÂÏ ‚ÂÍÚÓÌÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ ̇‰ ÔÓÎÂÏ,Â„Ó ÓÔ‰ÂÎÂÌË ÏÓÊÂÚ ·˚Ú¸ ÔÓÎÛ˜ÂÌÓ ËÁ ÓÔ‰ÂÎÂÌËfl ‚ÂÍÚÓÌÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ÔÛÚÂÏ Á‡ÏÂÌ˚ ÔÓÎfl ̇ ‡ÒÒӈˇÚË‚ÌÛ˛ ‡Î„Â·Û Ò Â‰ËÌ˘Ì˚Ï ˝ÎÂÏÂÌÚÓÏ. ÄÙÙËÌÌÓÂÔÓÒÚ‡ÌÒÚ‚Ó Ì‡‰ ‡Î„·ÓÈ fl‚ÎflÂÚÒfl ‡Ì‡Îӄ˘Ì˚Ï Ó·Ó·˘ÂÌËÂÏ ‡ÙÙËÌÌÓ„ÓÔÓÒÚ‡ÌÒÚ‚‡ ̇‰ ÔÓÎÂÏ.
Ç ‡ÙÙËÌÌ˚ı ÔÓÒÚ‡ÌÒÚ‚‡ı ̇‰ ‡Î„·‡ÏË ÏÓÊÌÓÓÔ‰ÂÎËÚ¸ ˝ÏËÚÓ‚Û ÏÂÚËÍÛ, ‚ ÚÓ ‚ÂÏfl Í‡Í ‰Îfl ÍÓÏÏÛÚ‡ÚË‚Ì˚ı ‡Î„· ÏÓÊÂÚ·˚Ú¸ ÓÔ‰ÂÎÂ̇ ‰‡Ê ͂‡‰‡Ú˘̇fl ÏÂÚË͇. ÑÎfl ˝ÚÓ„Ó ‚ ÛÌËڇθÌÓÏ ÏÓ‰ÛÎÂÌÂÓ·ıÓ‰ËÏÓ ÓÔ‰ÂÎËÚ¸ Ò͇ÎflÌÓ ÔÓËÁ‚‰ÂÌË 〈x, y〉, ‚ Ô‚ÓÏ ÒÎÛ˜‡Â ÒÓÒ‚ÓÈÒÚ‚ÓÏ 〈x, y〉 = J(〈y, x〉), „‰Â J fl‚ÎflÂÚÒfl ËÌ‚ÓβÚË‚Ì˚Ï ÓÚÓ·‡ÊÂÌËÂÏ ‡Î„·˚, ‡‚Ó ‚ÚÓÓÏ ÒÎÛ˜‡Â ÒÓ Ò‚ÓÈÒÚ‚ÓÏ 〈x, y〉 = 〈y, x〉,n-åÂÌÓ ÔÓÂÍÚË‚ÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ì‡‰ ‡Î„·ÓÈ Á‡‰‡ÂÚÒfl Í‡Í ÏÌÓ„ÓÓ·‡ÁËÂÓ‰ÌÓÏÂÌ˚ı ÔÓ‰ÏÓ‰ÛÎÂÈ (n + 1)-ÏÂÌÓ„Ó ÛÌËڇθÌÓ„Ó ÏÓ‰ÛÎfl ̇‰ ˝ÚÓÈ ‡Î„·ÓÈ.ǂ‰ÂÌË Ò͇ÎflÌÓ„Ó ÔÓËÁ‚‰ÂÌËfl 〈x, y〉 ‚ ÛÌËڇθÌÓÏ ÏÓ‰ÛΠÔÓÁ‚ÓÎflÂÚ Á‡‰‡Ú¸ ‚ÔÓÒÚÓÂÌÌÓÏ Ò ÔÓÏÓ˘¸˛ ‰‡ÌÌÓ„Ó ÏÓ‰ÛÎfl ÔÓÂÍÚË‚ÌÓÏ ÔÓÒÚ‡ÌÒÚ‚Â ˝ÏËÚÓ‚Û ËÎË,‰Îfl ÒÎÛ˜‡fl ÍÓÏÏÛÚ‡ÚË‚ÌÓÈ ‡Î„·˚, Í‚‡‰‡Ú˘ÌÛ˛ ˝ÎÎËÔÚ˘ÂÒÍÛ˛ Ë „ËÔ·Ó-68ó‡ÒÚ¸ I.
å‡ÚÂχÚË͇ ‡ÒÒÚÓflÌËÈ΢ÂÒÍÛ˛ ÏÂÚËÍÛ. åÂÚ˘ÂÒÍËÈ ËÌ‚‡Ë‡ÌÚ ÚÓ˜ÂÍ ˝ÚËı ÔÓÒÚ‡ÌÒÚ‚ ÂÒÚ¸‡Ì„‡ÏÓÌ˘ÂÒÍÓ ÓÚÌÓ¯ÂÌË W = 〈x, x〉–1 〈x, y〉 〈y, y〉–1 〈x, y〉. ÖÒÎË W – ‰ÂÈÒÚ‚ËÚÂθÌÓ˜ËÒÎÓ, ÚÓ ËÌ‚‡Ë‡ÌÚ w, ‰Îfl ÍÓÚÓÓ„Ó W = cos2w, ̇Á˚‚‡ÂÚÒfl ‡ÒÒÚÓflÌËÂÏ ÏÂÊ‰Û ı ËÛ ‚ ÔÓÒÚ‡ÌÒڂ ̇‰ ‡Î„·ÓÈ.ó‡ÒÚ˘ÌÓ ÛÔÓfl‰Ó˜ÂÌÌÓ ‡ÒÒÚÓflÌËÂèÛÒÚ¸ ï – ÔÓËÁ‚ÓθÌÓ ÏÌÓÊÂÒÚ‚Ó. èÛÒÚ¸ (G, ≤) – ˜‡ÒÚ˘ÌÓ ÛÔÓfl‰Ó˜ÂÌÌÓÂÏÌÓÊÂÒÚ‚Ó Ò Ì‡ËÏÂ̸¯ËÏ ˝ÎÂÏÂÌÚÓÏ g0 , Ú‡ÍÓ ˜ÚÓ G = G\{g0 } ÌÂÔÛÒÚÓ, Ë ‰Îflβ·˚ı g1 , g2 ∈ G ÒÛ˘ÂÒÚ‚ÛÂÚ g3 ∈ G, Ú‡ÍÓ ˜ÚÓ g3 ≤ g1 Ë g3 ≤ g2 .ó‡ÒÚ˘ÌÓ ÛÔÓfl‰Ó˜ÂÌÌÓ ‡ÒÒÚÓflÌË ÂÒÚ¸ ÙÛÌ͈Ëfl d : X × X → G, ڇ͇fl ˜ÚÓ ‰Îflβ·˚ı x, y ∈ X ‡‚ÂÌÒÚ‚Ó d(x, y) = g0 ‚˚ÔÓÎÌflÂÚÒfl ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ x =y.ê‡ÒÒÏÓÚËÏ ÒÎÂ‰Û˛˘Ë ‚ÓÁÏÓÊÌ˚ ҂ÓÈÒÚ‚‡.1. ÑÎfl β·Ó„Ó g1 ∈ G ÒÛ˘ÂÒÚ‚ÛÂÚ g 2 ∈ G, Ú‡ÍÓ ˜ÚÓ ‰Îfl β·˚ı x, y ∈ X ËÁ̇‚ÂÌÒÚ‚‡ d(x, y) ≤ g2 ÒΉÛÂÚ Ì‡‚ÂÌÒÚ‚Ó d(x, y) ≤ g1 .2. ÑÎfl β·Ó„Ó g1 ∈ G ÒÛ˘ÂÒÚ‚Û˛Ú g2 , g3 ∈ G, Ú‡ÍË ˜ÚÓ ‰Îfl β·˚ı x, y, z ∈ X ËÁ̇‚ÂÌÒÚ‚ d(x, y) ≤ g2 Ë d(y, z) ≤ g2 ÒΉÛÂÚ Ì‡‚ÂÌÒÚ‚Ó (y, x) ≤ g1 .3. ÑÎfl β·Ó„Ó g1 ∈ G ÒÛ˘ÂÒÚ‚ÛÂÚ g 2 ∈ G, Ú‡ÍÓ ˜ÚÓ ‰Îfl β·˚ı x, y, z ∈ X ËÁ̇‚ÂÌÒÚ‚ d(x, y) ≤ g2 Ë d(y, z) ≤ g2 ÒΉÛÂÚ Ì‡‚ÂÌÒÚ‚Ó d(y, x) ≤ g1 .4. G Ì ËÏÂÂÚ ÔÂ‚Ó„Ó ˝ÎÂÏÂÌÚ‡.5. d(x, y) = d(y, x) ‰Îfl β·˚ı x, y ∈ X.6. ÑÎfl β·Ó„Ó g1 ∈ G ÒÛ˘ÂÒÚ‚ÛÂÚ g2 ∈ G, Ú‡ÍÓ ˜ÚÓ ‰Îfl β·˚ı x, y ∈ X ËÁ̇‚ÂÌÒÚ‚ d(x, y) <* g 2 Ë d(y, z) < * g 1 ÒΉÛÂÚ Ì‡‚ÂÌÒÚ‚Ó d(x, z) <* g 1 ; Á‰ÂÒ¸ p <* qÓÁ̇˜‡ÂÚ, ˜ÚÓ ÎË·Ó p < q, ÎË·Ó Ì ҇‚ÌËÏÓ Ò q.7. éÚÌÓ¯ÂÌË ÔÓfl‰Í‡ < fl‚ÎflÂÚÒfl ÎËÌÂÈÌ˚Ï ÔÓfl‰ÍÓÏ Ì‡ G.Ç ÚÂÏË̇ı Û͇Á‡ÌÌ˚ı ‚˚¯Â Ò‚ÓÈÒÚ‚ d ̇Á˚‚‡ÂÚÒfl: ˜‡ÒÚ˘ÌÓ ÛÔÓfl‰Ó˜ÂÌÌÓ‡ÒÒÚÓflÌË ÄÔÔÂÚ‡, ÂÒÎË ‚˚ÔÓÎÌfl˛ÚÒfl ÛÒÎÓ‚Ëfl 1 Ë 2; ˜‡ÒÚ˘ÌÓ ÛÔÓfl‰Ó˜ÂÌÌÓ‡ÒÒÚÓflÌË ÉÓÎÏÂÒ‡ ÔÂ‚Ó„Ó ÚËÔ‡, ÂÒÎË ‚˚ÔÓÎÌfl˛ÚÒfl ÛÒÎÓ‚Ëfl 4, 5 Ë 6; ˜‡ÒÚ˘ÌÓÛÔÓfl‰Ó˜ÂÌÌÓ ‡ÒÒÚÓflÌË ÉÓÎÏÂÒ‡ ‚ÚÓÓ„Ó ÚËÔ‡, ÂÒÎË ‚˚ÔÓÎÌfl˛ÚÒfl ÛÒÎÓ‚Ëfl 3, 4,Ë 5; ‡ÒÒÚÓflÌË äÛÂÔ‡–î¯Â, ÂÒÎË ‚˚ÔÓÎÌfl˛ÚÒfl ÛÒÎÓ‚Ëfl 3, 4, 5 Ë 7.àÏÂÌÌÓ, ÒÎÛ˜‡È G = ≥0 ‡ÒÒÚÓflÌËfl äÛÂÔ‡–ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ V-ÔÓÒÚ‡ÌÒÚ‚Û î¯Â, Ú.Â.