Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (1185330), страница 54

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 54)

éÌÓ ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ ‡ÒÒÚÓflÌ˲ „·ÏÂÌÚËÓ‚‡ÌÌÓ„Ó ‰‡ÍÚËÓ‚‡ÌËfl, „‰Â ‚Ò ‚ÒÚ‡‚ÍË ‰ÓÎÊÌ˚ Ô‰¯ÂÒÚ‚Ó‚‡Ú¸ Û‰‡ÎÂÌËflÏ.ùÚÓ ÓÁ̇˜‡ÂÚ, ˜ÚÓ Ï˚ ‚ÒÚ‡‚ÎflÂÏ ÔÓ·ÂÎ˚, Ú.Â. ‚Â¯ËÌ˚, Ó·ÓÁ̇˜ÂÌÌ˚ ÒËÏ‚ÓÎÓÏ Ôӷ· λ, ‚ ‰Â‚¸fl T 1 Ë T 2 Ú‡Í, ˜ÚÓ·˚ ÓÌË ÒÚ‡ÎË ËÁÓÏÓÙÌ˚ ÔË Ë„ÌÓËÓ-É·‚‡ 15. ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË „‡ÙÓ‚241‚‡ÌËË Ë̉ÂÍÒÓ‚; ÔÓÎÛ˜ÂÌÌ˚ ‚ ÂÁÛθڇÚ ‰Â‚¸fl ̇Í·‰˚‚‡˛ÚÒfl ‰Û„ ̇ ‰Û„‡ ˉ‡˛Ú ‚˚‡‚ÌË‚‡ÌË T A , – ‰Â‚Ó, ‚ ÍÓÚÓÓÏ Í‡Ê‰‡fl ‚Â¯Ë̇ ÔÓÎÛ˜Â̇ Ô‡ÓÈË̉ÂÍÒÓ‚. ñÂ̇ TA – ÒÛÏχ ˆÂÌ ‚ÒÂı Ô‡ ÔÓÚË‚ÓÔÓÎÓÊÂÌÌ˚ı Ë̉ÂÍÒÓ‚ ‚ TA.ê‡ÒÒÚÓflÌË ‡Á·ËÂÌËÈ-ÒÓ‚Ï¢ÂÌËÈê‡ÒÒÚÓflÌË ‡Á·ËÂÌËÈ-ÒÓ‚Ï¢ÂÌËÈ ([ChLu85]) ÂÒÚ¸ ‡ÒÒÚÓflÌË ̇ ÏÌÓÊÂÒÚ‚Â rlo‚ÒÂı ÍÓÌ‚˚ı ÔÓϘÂÌÌ˚ı ÛÔÓfl‰Ó˜ÂÌÌ˚ı ‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌÌÓ ‰Îfl β·˚ı T1 ,T 2 ∈ rlo Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ ‡Á·ËÂÌËÈ Ë ÒÓ‚Ï¢ÂÌËÈ ‚Â¯ËÌ, ÌÂÓ·ıÓ‰ËÏ˚ı‰Îfl ÔÂÓ·‡ÁÓ‚‡ÌËfl T 1 ‚ T2.ê‡ÒÒÚÓflÌË 2-ÒÚÂÔÂÌËê‡ÒÒÚÓflÌË 2-ÒÚÂÔÂÌË ÂÒÚ¸ ÏÂÚË͇ ̇ ÏÌÓÊÂÒÚ‚Â l ‚ÒÂı ÔÓϘÂÌÌ˚ı ‰Â‚¸Â‚(ÔÓϘÂÌÌ˚ı Ò‚Ó·Ó‰Ì˚ı ‰Â‚¸Â‚), ÓÔ‰ÂÎÂÌ̇fl Í‡Í ÏËÌËχθÌÓ ‚Á‚¯ÂÌÌÓ˜ËÒÎÓ ÓÔÂ‡ˆËÈ ‰‡ÍÚËÓ‚‡ÌËfl (ÔÂÂË̉ÂÍÒ‡ˆËÂÈ, ‚ÒÚ‡‚ÓÍ Ë Û‰‡ÎÂÌËÈ), ÔÂ‚Ӊfl˘Ëı T1 ‚ T2, ÂÒÎË Î˛·‡fl ‚ÒÚ‡‚ÎflÂχfl (Û‰‡ÎflÂχfl) ‚Â¯Ë̇ ËÏÂÂÚ Ì ·ÓΠ‰‚ÛıÒÓÒ‰ÌËı ‚Â¯ËÌ.

í‡Í‡fl ÏÂÚË͇ fl‚ÎflÂÚÒfl ÂÒÚÂÒÚ‚ÂÌÌ˚Ï ‡Ò¯ËÂÌËÂÏ ‡ÒÒÚÓflÌËfl‰‡ÍÚËÓ‚‡ÌËfl ‰Â‚‡ Ë ‡ÒÒÚÓflÌËfl ëÂÎÍÓÛ.îËÎÓ„ÂÌÂÚ˘ÂÒÍÓ ï-‰ÂÂ‚Ó – ÌÂÛÔÓfl‰Ó˜ÂÌÌÓ ‰ÂÂ‚Ó ·ÂÁ ÍÓÌfl Ò ÏÌÓÊÂÒÚ‚ÓÏÔÓϘÂÌÌ˚ı ÎËÒڸ‚ ï, Ì Ëϲ˘Â ‚Â¯ËÌ ÔÓfl‰Í‡ 2. ÖÒÎË Í‡Ê‰‡fl ‚ÌÛÚÂÌÌflfl‚Â¯Ë̇ ËÏÂÂÚ ÔÓfl‰ÓÍ 3, ÚÓ ‰ÂÂ‚Ó Ì‡Á˚‚‡ÂÚÒfl ·Ë̇Ì˚Ï (ËÎË ‚ÔÓÎÌ ‡Á¯ÂÌÌ˚Ï).ê‡ÁÂÁ Ä|Ç ÏÌÓÊÂÒÚ‚‡ ï ÂÒÚ¸ ‡Á·ËÂÌË ÏÌÓÊÂÒÚ‚‡ ï ̇ ‰‚‡ ÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ä Ë Ç(ÒÏ. èÓÎÛÏÂÚË͇ ‡ÁÂÁ‡). 쉇ÎÂÌË ·‡  ËÁ ÙËÎÓ„ÂÌÂÚ˘ÂÒÍÓ„Ó ï-‰Â‚‡ ‚ΘÂÚ ‡ÁÂÁ ÏÌÓÊÂÒÚ‚‡ ÎËÒڸ‚ ï, ̇Á˚‚‡ÂÏ˚È ‡ÁÂÁÓÏ, ‡ÒÒÓˆËËÓ‚‡ÌÌ˚Ï Ò Â.åÂÚË͇ êÓ·ËÌÁÓ̇–îÓÛΉ҇åÂÚË͇ êÓ·ËÌÁÓ̇-îÓÛΉ҇ (ËÎË ÏÂÚË͇ ·ÎËÊ‡È¯Â„Ó ‡Á·ËÂÌËfl, ‡ÒÒÚÓflÌËÂ‡ÁÂÁ‡) ÂÒÚ¸ ÏÂÚË͇ ̇ ÏÌÓÊÂÒÚ‚Â (X) ‚ÒÂı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚,ÓÔ‰ÂÎÂÌ̇fl ͇Í111Σ(T1 )∆Σ(T2 ) = Σ(T1 ) − Σ(T2 ) + Σ(T2 ) − Σ(T1 ) .222‰Îfl ‚ÒÂı T1, T2 ∈ (X), „‰Â Σ(T) – ÒÓ‚ÓÍÛÔÌÓÒÚ¸ ‚ÒÂı ‡ÁÂÁÓ‚ ï, ‡ÒÒÓˆËËÓ‚‡ÌÌ˚ı Ò·‡ÏË í.ÇÁ‚¯ÂÌ̇fl ÏÂÚË͇ êÓ·ËÌÁÓ̇–îÓÛΉ҇ÇÁ‚¯ÂÌ̇fl ÏÂÚË͇ êÓ·ËÌÁÓ̇–îÓÛΉ҇ – ÏÂÚË͇ ̇ ÏÌÓÊÂÒÚ‚Â (X) ‚ÒÂı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌ̇fl ͇Í∑w1 ( A | B) − w2 ( A | B)A| B ∈Σ ( T1 ) ∪ Σ ( T2 )‰Îfl ‚ÒÂı T1, T2 ∈ (X), „‰Â wi = ( w(e))e ∈E ( Ti ) – ÒÓ‚ÓÍÛÔÌÓÒÚ¸ ÔÓÎÓÊËÚÂθÌ˚ı·ÂÌ˚ı ‚ÂÒÓ‚ ï-‰Â‚‡ Ti, Σ(Ti) – ÒÓ‚ÓÍÛÔÌÓÒÚ¸ ‚ÒÂı ‡ÁÂÁÓ‚ ï, ‡ÒÒÓˆËËÓ‚‡ÌÌ˚ı Ò ·‡ÏË T i, Ë wi(A|B) – ‚ÂÒ ·‡, ‡ÒÒÓˆËËÓ‚‡ÌÌÓ„Ó Ò ‡ÁÂÁÓÏ Ä|ÇÏÌÓÊÂÒÚ‚‡ ïi, i = 1, 2.åÂÚË͇ Ó·ÏÂ̇ ·ÎËʇȯËÏË ÒÓÒ‰flÏËåÂÚË͇ Ó·ÏÂ̇ ·ÎËʇȯËÏË ÒÓÒ‰flÏË (ËÎË ÏÂÚË͇ ÍÓÒÒÓ‚Â‡) ÂÒÚ¸ ÏÂÚË͇̇ ÏÌÓÊÂÒÚ‚Â (X) ‚ÒÂı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌ̇fl ‰Îfl ‚ÒÂıT 1 , T 2 ∈ (X) Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ Ó·ÏÂÌÓ‚ ·ÎËʇȯËÏË ÒÓÒ‰flÏË, ÌÂÓ·ıÓ‰ËÏ˚ı‰Îfl ÔÂÓ·‡ÁÓ‚‡ÌËfl T 1 ‚ T2.242ó‡ÒÚ¸ IV.

ê‡ÒÒÚÓflÌËfl ‚ ÔËÍ·‰ÌÓÈ Ï‡ÚÂχÚËÍÂé·ÏÂÌ ·ÎËʇȯËÏË ÒÓÒ‰flÏË – Á‡ÏÂ̇ ‰‚Ûı ÔÓ‰‰Â‚¸Â‚ ‚ ‰Â‚Â, ÒÏÂÊÌ˚ıÒ Ó‰ÌËÏ Ë ÚÂÏ Ê ‚ÌÛÚÂÌÌËÏ ·ÓÏ; ÔË ˝ÚÓÏ ÓÒڇθ̇fl ˜‡ÒÚ¸ ‰Â‚‡ ÓÒÚ‡ÂÚÒfl·ÂÁ ËÁÏÂÌÂÌËÈ.ê‡ÒÒÚÓflÌË ÛÔÓ˘ÂÌËfl Ë ÔÂÂÒ‡‰ÍË ÔÓ‰‰Â‚‡ê‡ÒÒÚÓflÌË ÛÔÓ˘ÂÌËfl Ë ÔÂÂÒ‡‰ÍË ÔÓ‰‰Â‚‡ ÂÒÚ¸ ÏÂÚË͇ ̇ ÏÌÓÊÂÒÚ‚Â (X)‚ÒÂı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌ̇fl ‰Îfl ‚ÒÂı T1, T2 ∈ (X) Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ ÛÔÓ˘ÂÌËÈ Ë ÔÂÂÒ‡‰ÍË ÔÓ‰‰Â‚‡, ÌÂÓ·ıÓ‰ËÏ˚ı ‰Îfl ÔÂÓ·‡ÁÓ‚‡ÌËfl T1 ‚ T2.èÂÓ·‡ÁÓ‚‡ÌË ÛÔÓ˘ÂÌËfl Ë ÔÂÂÒ‡‰ÍË ÔÓ‰‰Â‚‡ ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ‚ ÚË ˝Ú‡Ô‡:Ò̇˜‡Î‡ ‚˚·Ë‡ÂÚÒfl Ë Û‰‡ÎflÂÚÒfl ·Ó uv ‰Â‚‡, ÚÂÏ Ò‡Ï˚Ï ‰ÂÂ‚Ó ‡Á‰ÂÎflÂÚÒfl ̇‰‚‡ ÔÓ‰‰Â‚‡ T u (ÒÓ‰Âʇ˘Â u) Ë Tv (ÒÓ‰Âʇ˘Â v); Á‡ÚÂÏ ‚˚·Ë‡ÂÚÒfl Ë ÔÓ‰‡Á‰ÂÎflÂÚÒfl ·Ó ÔÓ‰‰Â‚‡ Tv, ˜ÚÓ ‰‡ÂÚ Ì‡Ï ÌÓ‚Û˛ ‚Â¯ËÌÛ w; ̇ÍÓ̈, ‚Â¯ËÌ˚ u Ëw ÒÓ‰ËÌfl˛ÚÒfl ·ÓÏ, ‡ ‚Ò ‚Â¯ËÌ˚ ÒÚÂÔÂÌË ‰‚‡ Û‰‡Îfl˛ÚÒfl.åÂÚË͇ ‡ÒÒ˜ÂÌËfl-‚ÓÒÒÚ‡ÌÓ‚ÎÂÌËfl ‰Â‚‡åÂÚË͇ ‡ÒÒ˜ÂÌËfl-‚ÓÒÒÚ‡ÌÓ‚ÎÂÌËfl ‰Â‚‡ – ÏÂÚË͇ ̇ ÏÌÓÊÂÒÚ‚Â (X) ‚ÒÂıÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌ̇fl ‰Îfl ‚ÒÂı T 1 , T 2 ∈ (X) Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ ÔÂÓ·‡ÁÓ‚‡ÌËÈ ‡ÒÒ˜ÂÌËfl – ‚ÓÒÒÚ‡ÌÓ‚ÎÂÌËfl ‰Â‚‡, ÌÂÓ·ıÓ‰ËÏ˚ı‰Îfl Ó·‡˘ÂÌËfl T 1 ‚ T2.èÂÓ·‡ÁÓ‚‡ÌË ‡ÒÒ˜ÂÌËfl – ‚ÓÒÒÚ‡ÌÓ‚ÎÂÌËfl ‰Â‚‡ ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ‚ Ú˽ڇԇ: Ò̇˜‡Î‡ ‚˚·Ë‡ÂÚÒfl Ë Û‰‡ÎflÂÚÒfl ·Ó uv ‰Â‚‡, ÚÂÏ Ò‡Ï˚Ï ‰ÂÂ‚Ó ‡Á‰ÂÎflÂÚÒfl ̇ ‰‚‡ ÔÓ‰‰Â‚‡ T u (ÒÓ‰Âʇ˘Â u) Ë T v (ÒÓ‰Âʇ˘Â v); Á‡ÚÂÏ ‚˚·Ë‡˛ÚÒflË ÔÓ‰‡Á‰ÂÎfl˛ÚÒfl ·Ó ÔÓ‰‰Â‚‡ T v, ˜ÚÓ ‰‡ÂÚ Ì‡Ï ÌÓ‚Û˛ ‚Â¯ËÌÛ w, Ë ·ÓÔÓ‰‰Â‚‡ Tu, ˜ÚÓ ‰‡ÂÚ Ì‡Ï ÌÓ‚Û˛ ‚Â¯ËÌÛ z; ̇ÍÓ̈, ‚Â¯ËÌ˚ w Ë z ÒÓ‰ËÌfl˛ÚÒfl·ÓÏ, ‡ ‚Ò ‚Â¯ËÌ˚ ÒÚÂÔÂÌË ‰‚‡ Û‰‡Îfl˛ÚÒfl.ê‡ÒÒÚÓflÌË ͂‡ÚÂÚ‡ê‡ÒÒÚÓflÌË ͂‡ÚÂÚ‡ ([EMM85]) – ‡ÒÒÚÓflÌË ̇ ÏÌÓÊÂÒÚ‚Â b (X) ‚ÒÂı ·Ë̇Ì˚ı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌÌÓ ‰Îfl ‚ÒÂı T1, T 2 ∈ b (X) ͇͘ËÒÎÓ ÌÂÒÓ‚Ô‡‰‡˛˘Ëı Í‚‡ÚÂÚÓ‚ (ËÁ Ó·˘Â„Ó ˜ËÒ· ( n4 ) ‚ÓÁÏÓÊÌ˚ı Í‚‡ÚÂÚÓ‚) ‰ÎflT 1 Ë T2 .чÌÌÓ ‡ÒÒÚÓflÌË ÓÒÌÓ‚‡ÌÓ Ì‡ ÚÓÏ Ù‡ÍÚÂ, ˜ÚÓ ‰Îfl ˜ÂÚ˚Âı ÎËÒڸ‚ {1, 2, 3, 4}‰Â‚‡ ÒÛ˘ÂÒÚ‚ÛÂÚ ÚÓθÍÓ ÚË ‡Á΢Ì˚ı ÒÔÓÒÓ·‡ Ëı Ó·˙‰ËÌÂÌËfl ̇ ·Ë̇ÌÓÏÔÓ‰‰Â‚Â: (12|34), (13|24) ËÎË (14|23): ÒËÏ‚ÓÎÓÏ (12|34) Ó·ÓÁ̇˜‡ÂÚÒfl ·Ë̇ÌÓ‰ÂÂ‚Ó Ò ÏÌÓÊÂÒÚ‚ÓÏ ÎËÒڸ‚ {1, 2, 3, 4}, ËÁ ÍÓÚÓÓ„Ó ÔÓÒΠۉ‡ÎÂÌËfl ‚ÌÛÚÂÌÌ„Ó·‡ ÔÓÎÛ˜‡˛ÚÒfl ‰Â‚¸fl Ò ÏÌÓÊÂÒÚ‚‡ÏË ÎËÒڸ‚ {1, 2} Ë {3, 4}.ê‡ÒÒÚÓflÌË ÚËÔÎÂÚ‡ê‡ÒÒÚÓflÌËÂÏ ÚËÔÎÂÚ‡ ([CPQ96]) ̇Á˚‚‡ÂÚÒfl ‡ÒÒÚÓflÌË ̇ ÏÌÓÊÂÒÚ‚Â b(X) ‚ÒÂı·Ë̇Ì˚ı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌÌÓ ‰Îfl ‚ÒÂı T1, T2 ∈ b(X) ͇͘ËÒÎÓ ÚÓÂÍ (ËÁ Ó·˘Â„Ó ˜ËÒ· ( 3n ) ‚ÓÁÏÓÊÌ˚ı ÚÓÂÍ), ÍÓÚÓ˚ ‡Á΢‡˛ÚÒfl (̇ÔËÏÂ, ÔÓ ‡ÒÔÓÎÓÊÂÌ˲ ÎËÒÚ‡) ‰Îfl T 1 Ë T2 .ê‡ÒÒÚÓflÌË ÒÓ‚Â¯ÂÌÌÓ„Ó Ô‡ÓÒÓ˜ÂÚ‡ÌËflê‡ÒÒÚÓflÌË ÒÓ‚Â¯ÂÌÌÓ„Ó Ô‡ÓÒÓ˜ÂÚ‡ÌËfl – ‡ÒÒÚÓflÌË ̇ ÏÌÓÊÂÒÚ‚Â b (X) ‚ÒÂıÍÓÌ‚˚ı ·Ë̇Ì˚ı ÙËÎÓ„ÂÌÂÚ˘ÂÒÍËı X-‰Â‚¸Â‚ Ò ÏÌÓÊÂÒÚ‚ÓÏ ï n ÔÓϘÂÌÌ˚ıÎËÒڸ‚, ÓÔ‰ÂÎÂÌÌÓ ‰Îfl β·˚ı T1 , T 2 ∈ b(X) Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ ÔÂÂÒÚ‡ÌÓ‚ÓÍ, ÌÂÓ·ıÓ‰ËÏ˚ı ‰Îfl ÚÓ„Ó, ˜ÚÓ·˚ ÔÂ‚ÂÒÚË ÒÓ‚Â¯ÂÌÌÓ ԇÓÒÓ˜ÂÚ‡ÌˉÂ‚‡ T 1 ‚ ÒÓ‚Â¯ÂÌÌÓ ԇÓÒÓ˜ÂÚ‡ÌË ‰Â‚‡ T 2 .É·‚‡ 15.

ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË „‡ÙÓ‚243ÑÎfl ÏÌÓÊÂÒÚ‚‡ A = {1,..., 2k}, ÒÓÒÚÓfl˘Â„Ó ËÁ 2k ÚÓ˜ÂÍ, ÒÓ‚Â¯ÂÌÌ˚Ï Ô‡ÓÒÓ˜ÂÚ‡ÌËÂÏ A ̇Á˚‚‡ÂÚÒfl ‡Á·ËÂÌË A ̇ k Ô‡. äÓÌ‚Ó ·Ë̇ÌÓ ÙËÎÓ„ÂÌÂÚ˘ÂÒÍÓ ‰ÂÂ‚Ó Ò n ÔÓϘÂÌÌ˚ÏË ÎËÒÚ¸flÏË ËÏÂÂÚ ÍÓÂ̸ Ë n – 2 ‚ÌÛÚÂÌÌË‚Â¯ËÌ˚, ÓÚ΢‡˛˘ËıÒfl ÓÚ ÍÓÌfl. Ö„Ó ÏÓÊÌÓ ÓÚÓʉÂÒÚ‚ËÚ¸ Ò ÒÓ‚Â¯ÂÌÌ˚ÏÔ‡ÓÒÓ˜ÂÚ‡ÌËÂÏ Ì‡ 2n – 2 ÓÚ΢‡˛˘ËıÒfl ÓÚ ÍÓÌfl ‚Â¯ËÌ Ò ÔÓÏÓ˘¸˛ ÒÎÂ‰Û˛˘Â„ÓÔÓÒÚÓÂÌËfl: Ó·ÓÁ̇˜ËÏ ‚ÌÛÚÂÌÌË ‚Â¯ËÌ˚ ˜ËÒ·ÏË n + 1,..., 2n – 2, ÔÓÒÚ‡‚˂̇ËÏÂ̸¯ËÈ Ëϲ˘ËÈÒfl Ë̉ÂÍÒ ‚ ͇˜ÂÒÚ‚Â Ó‰ËÚÂθÒÍÓÈ ‚Â¯ËÌ˚ Ô‡˚ ÔÓϘÂÌÌ˚ı ‰Ó˜ÂÌËı ˝ÎÂÏÂÌÚÓ‚, ËÁ ÍÓÚÓ˚ı Ó‰ËÌ ËÏÂÂÚ Ì‡ËÏÂ̸¯ËÈ Ë̉ÂÍÒ Ò‰ËÔÓϘÂÌÌ˚ı ‰Ó˜ÂÌËı ˝ÎÂÏÂÌÚÓ‚; ÚÂÔÂ¸ Ô‡ÓÒÓ˜ÂÚ‡ÌË ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ÔÓÒ‰ÒÚ‚ÓÏ ÓÚÒÎÓÂÌËfl ÔÓ ‰‚Ó ‰Ó˜ÂÌËı ˝ÎÂÏÂÌÚÓ‚ ËÎË Ô‡ ‚Â¯ËÌ-ÒÂÒÚÂ.åÂÚËÍË ‡ÚË·ÛÚË‚ÌÓ„Ó ‰Â‚‡ÄÚË·ÛÚË‚Ì˚Ï ‰Â‚ÓÏ Ì‡Á˚‚‡ÂÚÒfl ÚÓÈ͇ (V, E, α), „‰Â T = (V, E) – ËÒıÓ‰ÌÓ‰ÂÂ‚Ó Ë α – ÙÛÌ͈Ëfl, ÍÓÚÓ‡fl ÒÚ‡‚ËÚ ‚ ÒÓÓÚ‚ÂÚÒÚ‚Ë ͇ʉÓÈ ‚Â¯ËÌ v ∈ V ‚ÂÍÚÓ‡ÚË·ÛÚÓ‚ α(v). ÑÎfl ‰‚Ûı ‡ÚË·ÛÚË‚Ì˚ı ‰Â‚¸Â‚ (V1 , E1 , α) Ë (V2 , E2 , β) ‡ÒÒÏÓÚËÏÏÌÓÊÂÒÚ‚Ó ‚ÒÂı ËÁÓÏÓÙËÁÏÓ‚ ÔÓ‰‰Â‚¸Â‚ ÏÂÊ‰Û ÌËÏË, Ú.Â.

ÏÌÓÊÂÒÚ‚Ó ‚ÒÂıËÁÓÏÓÙËÁÏÓ‚ f : H1 → H2, H 1 ⊂ V1 , H 2 ⊂ V2 ÏÂÊ‰Û Ëı Ë̉ۈËÓ‚‡ÌÌ˚ÏËÔÓ‰‰Â‚¸flÏË. ÖÒÎË Ì‡ ÏÌÓÊÂÒÚ‚Â ‡ÚË·ÛÚÓ‚ ËÏÂÂÚÒfl ÔÓ‰Ó·ÌÓÒÚ¸ s, ÚÓ ÔÓ‰Ó·ÌÓÒÚ¸ÏÂÊ‰Û ËÁÓÏÓÙÌ˚ÏË Ë̉ۈËÓ‚‡ÌÌ˚ÏË ÔÓ‰ ‰Â‚¸flÏË ÓÔ‰ÂÎflÂÚÒfl ͇ÍWs ( f ) =s(α( v), β( f ( v))). àÁÓÏÓÙËÁÏ φ Ò Ï‡ÍÒËχθÌÓÈ ÔÓ‰Ó·ÌÓÒÚ¸˛ Ws(φ) =∑v ∈H1= W(φ) ̇Á˚‚‡ÂÚÒfl ËÁÓÏÓÙËÁÏÓÏ ‰Â‚‡ Ò Ï‡ÍÒËχθÌÓÈ ÔÓ‰Ó·ÌÓÒÚ¸˛.ç‡ ÏÌÓÊÂÒÚ‚Â Tatt ‚ÒÂı ‡ÚË·ÛÚË‚Ì˚ı ‰Â‚¸Â‚ ËÒÔÓθÁÛ˛ÚÒfl ÒÎÂ‰Û˛˘Ë ÔÓÎÛÏÂÚËÍË:1. max{| V1 |,| V2 |} − W (φ);2. | V1 | + | V2 | −2W (φ);W ( φ)3. 1 −;max{| V1 |,| V2 |}W ( φ).4. 1 −| V1 | + | V2 | −W (φ)éÌË ÒÚ‡ÌÓ‚flÚÒfl ÏÂÚË͇ÏË Ì‡ ÏÌÓÊÂÒÚ‚Â Í·ÒÒÓ‚ ˝Í‚Ë‚‡ÎÂÌÚÌÓÒÚË ‡ÚË·ÛÚË‚Ì˚ı ‰Â‚¸Â‚: ‰‚‡ ‡ÚË·ÛÚË‚Ì˚ı ‰Â‚‡ (V1 , E1 , α ) Ë (V2 , E2 , β) ̇Á˚‚‡˛ÚÒfl˝Í‚Ë‚‡ÎÂÌÚÌ˚ÏË, ÂÒÎË ÓÌË ‡ÚË·ÛÚË‚ÌÓ-ËÁÓÏÓÙÌ˚, Ú.Â.

ÒÛ˘ÂÒÚ‚ÛÂÚ ËÁÓÏÓÙËÁÏg: V1 → V2 ÏÂÊ‰Û ‰Â‚¸flÏË T1 Ë T 2 , Ú‡ÍÓÈ ˜ÚÓ ‰Îfl β·ÓÈ ‚Â¯ËÌ˚ v ∈ V1 ËÏÂÂÚÒflα(v) = β(g(v)). íÓ„‰‡ |V1 | = |V2 | = W(g).ê‡ÒÒÚÓflÌË ÔÓ‰‰Â‚‡ ̇˷Óθ¯Â„Ó ÒıÓ‰ÒÚ‚‡ê‡ÒÒÚÓflÌË ÔÓ‰‰Â‚‡ ̇˷Óθ¯Â„Ó ÒıÓ‰ÒÚ‚‡ – ‡ÒÒÚÓflÌË ̇ ÏÌÓÊÂÒÚ‚Â í ‚ÒÂı‰Â‚¸Â‚, ÓÔ‰ÂÎÂÌÌÓ ‰Îfl β·˚ı T1, T 2 ∈ T Í‡Í ÏËÌËχθÌÓ ˜ËÒÎÓ ÎËÒڸ‚,ÍÓÚÓ˚ ÌÛÊÌÓ Û‰‡ÎËÚ¸ ‰Îfl ÔÓÎÛ˜ÂÌËfl ÔÓ‰‰Â‚‡ ̇˷Óθ¯Â„Ó ÒıÓ‰ÒÚ‚‡.èÓ‰‰ÂÂ‚Ó ÒıÓ‰ÒÚ‚‡ (ËÎË Ó·˘Â ÛÔÓ˘ÂÌÌÓ ‰Â‚Ó) ‰‚Ûı ‰Â‚¸Â‚ ÂÒÚ¸ ‰Â‚Ó,ÍÓÚÓÓ ÏÓÊÂÚ ·˚Ú¸ ÔÓÎÛ˜ÂÌÓ ËÁ Ó·ÂËı ‰Â‚¸Â‚ ÔÓÒ‰ÒÚ‚ÓÏ Û‰‡ÎÂÌËfl ÎËÒڸ‚ ÒÓ‰Ë̇ÍÓ‚˚Ï Ë̉ÂÍÒÓÏ.É·‚‡ 16ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË ÍÓ‰ËÓ‚‡ÌËflíÂÓËfl ÍÓ‰ËÓ‚‡ÌËfl Óı‚‡Ú˚‚‡ÂÚ ‚ÓÔÓÒ˚ ‡Á‡·ÓÚÍË Ë Ò‚ÓÈÒÚ‚ Í Ó ‰ Ó ‚ ÒËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ ‰Îfl Ó·ÂÒÔ˜ÂÌËfl ̇‰ÂÊÌÓÈ ÔÂ‰‡˜Ë ËÌÙÓχˆËË ÔÓÍ‡Ì‡Î‡Ï Ò ‚˚ÒÓÍËÏ ÛÓ‚ÌÂÏ ¯ÛÏÓ‚ ‚ ÒËÒÚÂχı Ò‚flÁË Ë ÛÒÚÓÈÒÚ‚‡ı ı‡ÌÂÌËfl‰‡ÌÌ˚ı.

ñÂθ˛ ÚÂÓËË ÍÓ‰ËÓ‚‡ÌËfl fl‚ÎflÂÚÒfl ÔÓËÒÍ ÍÓ‰Ó‚, Ó·ÂÒÔ˜˂‡˛˘Ëı·˚ÒÚÛ˛ ÔÂ‰‡˜Û Ë ‰ÂÒÍÓ‰ËÓ‚‡ÌË ËÌÙÓχˆËË, ÒÓ‰Âʇ˘Ëı ÏÌÓ„Ó Á̇˜ËÏ˚ıÍÓ‰Ó‚˚ı ÒÎÓ‚ Ë ÒÔÓÒÓ·Ì˚ı ËÒÔ‡‚ÎflÚ¸ ËÎË, ÔÓ Í‡ÈÌÂÈ ÏÂÂ, ӷ̇ÛÊË‚‡Ú¸ ÏÌÓ„Óӯ˷ÓÍ. ùÚË ˆÂÎË fl‚Îfl˛ÚÒfl ‚Á‡ËÏÌÓ ËÒÍβ˜‡˛˘ËÏË; Ú‡ÍËÏ Ó·‡ÁÓÏ, ͇ʉÓ ËÁÔËÎÓÊÂÌËÈ ËÏÂÂÚ Ò‚ÓÈ ÒÓ·ÒÚ‚ÂÌÌ˚È ıÓÓ¯ËÈ ÍÓ‰.Ç Ó·Î‡ÒÚË ÍÓÏÏÛÌË͇ˆËÈ ÍÓ‰ÓÏ Ì‡Á˚‚‡ÂÚÒfl Ô‡‚ËÎÓ ‰Îfl ÔÂÓ·‡ÁÓ‚‡ÌËfl ÒÓÓ·˘ÂÌËÈ (̇ÔËÏÂ, ÔËÒÂÏ, ÒÎÓ‚ ËÎË Ù‡Á) ‚ ‰Û„Û˛ ÙÓÏÛ ËÎË Ô‰ÒÚ‡‚ÎÂÌËÂ, ÌÂÓ·flÁ‡ÚÂθÌÓ ÚÓ„Ó Ê ÚËÔ‡.

äÓ‰ËÓ‚‡ÌË – ÔÓˆÂÒÒ, ÔÓÒ‰ÒÚ‚ÓÏ ÍÓÚÓÓ„Ó ËÒÚÓ˜ÌËÍ(Ó·˙ÂÍÚ) ÓÒÛ˘ÂÒÚ‚ÎflÂÚ ÔÂÓ·‡ÁÓ‚‡ÌË ËÌÙÓχˆËË ‚ ‰‡ÌÌ˚Â, ÔÂ‰‡‚‡ÂÏ˚ Á‡ÚÂÏÔÓÎÛ˜‡ÚÂβ (̇·Î˛‰‡ÚÂβ), ̇ÔËÏÂ, ÒËÒÚÂÏ ӷ‡·ÓÚÍË ‰‡ÌÌ˚ı. ÑÂÍÓ‰ËÓ‚‡ÌËÂfl‚ÎflÂÚÒfl Ó·‡ÚÌ˚Ï ÔÓˆÂÒÒÓÏ ÔÂÓ·‡ÁÓ‚‡ÌËfl ‰‡ÌÌ˚ı, ÔÓÒÚÛÔË‚¯Ëı ÓÚ ËÒÚÓ˜ÌË͇,‚ ÔÓÌflÚÌ˚È ‰Îfl ÔÓÎÛ˜‡ÚÂÎfl ‚ˉ.äÓ‰ Ò ËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ – Ú‡ÍÓÈ ÍÓ‰, ‚ ÍÓÚÓÓÏ Í‡Ê‰˚È ÔÂ‰‡‚‡ÂÏ˚È˝ÎÂÏÂÌÚ ‰‡ÌÌ˚ı ÔÓ‰˜ËÌflÂÚÒfl ÒÔˆˇθÌ˚Ï Ô‡‚ËÎ‡Ï ÔÓÒÚÓÂÌËfl, Ò ÚÂÏ ˜ÚÓ·˚ÓÚÍÎÓÌÂÌËfl ÓÚ ‰‡ÌÌÓ„Ó ÔÓÒÚÓÂÌËfl ‚ ÔÓÎÛ˜ÂÌÌÓÏ Ò˄̇ΠÏÓ„ÎË ‡‚ÚÓχÚ˘ÂÒÍË‚˚fl‚ÎflÚ¸Òfl Ë ÍÓÂÍÚËÓ‚‡Ú¸Òfl. í‡Í‡fl ÚÂıÌÓÎÓ„Ëfl ËÒÔÓθÁÛÂÚÒfl ‚ ÍÓÏÔ¸˛ÚÂÌ˚ı̇ÍÓÔËÚÂθÌ˚ı ÛÒÚÓÈÒÚ‚‡ı, ̇ÔËÏÂ ‚ ‰Ë̇Ï˘ÂÒÍÓÈ Ô‡ÏflÚË RAM Ë ‚ ÒËÒÚÂχıÔÂ‰‡˜Ë ‰‡ÌÌ˚ı.

Характеристики

Список файлов книги