Овчаров Л.А. и др. Математические модели информационых процессов и управления
Подождите немного. Документ загружается.
97
Q = ε
n
∨ A ∨ A
[2]
∨ ... ∨ A
[n]
. (2.6)
ÑÎfl „‡Ù‡ Ò ˆËÍ·ÏË Ú‡ÍÓÈ ÔÓ‰ıÓ‰ Ú·ÛÂÚ ‡ÒÒÏÓÚÂÌËfl
·ÂÒÍÓ̘ÌÓ„Ó fl‰‡
QA
k
k
=
=
∞
∨
0
[]
. (2.7)
èÓ Ï‡Úˈ ÒÏÂÊÌÓÒÚË ÏÓÊÌÓ ÓÔ‰ÂÎflÚ¸ ̇΢ˠˆËÍÎÓ‚.
ÑÎfl ˝ÚÓ„Ó Ì‡‰Ó ̇ÈÚË Ï‡ÚˈÛ
ZAA A
k
k
= ∨∨∨
[] []
... ,
2
(2.8)
‰Ë‡„Ó̇θÌ˚È ˝ÎÂÏÂÌÚ ÍÓÚÓ ÓÈ
z
ii
k[]
Ó·‡˘‡ÂÚÒfl ‚ ‰ËÌËˆÛ ÚÓ„‰‡
Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ ÒÛ˘ÂÒÚ‚ÛÂÚ ˆËÍÎ ‰ÎËÌ˚ k, ÔÓıÓ‰fl˘ËÈ
˜ÂÂÁ ‚¯ËÌÛ v
i
.
Ñˇ„Ó̇θÌ˚ ˝ÎÂÏÂÌÚ˚ χÚˈ ÔÓÒΉӂ‡ÚÂθÌÓÒÚË Z
1
, Z
2
,
Z
3
,... ÌÂÒÛÚ ÔÓÎÌÛ˛ ËÌÙÓχˆË˛ Ó ˆËÍ·ı „‡Ù‡. éÔËÒ‡ÌÌ˚È
ÒÔÓÒÓ· ‡Ì‡ÎËÚ˘ÂÒÍÓ„Ó ËÒÒΉӂ‡ÌËfl ÔÛÚÂÈ ‰ÓÒÚËÊËÏÓÒÚË Ë
ˆËÍÎÓ‚ ‚ „‡Ù ËÏÂÂÚ ÒÍÓ ÚÂÓÂÚ˘ÂÒÍÓÂ, ˜ÂÏ Ô‡ÍÚ˘ÂÒÍÓÂ
Á̇˜ÂÌË ‰Îfl „‡ÙÓ‚ ·Óθ¯Ó„Ó ÔÓfl‰Í‡.
å‡Úˈ‡ ‰ÓÒÚËÊËÏÓÒÚË Q, Ú‡ÍÚÛÂχfl Í‡Í Ï‡Úˈ‡ ÒÏÂÊ-
ÌÓÒÚË „‡Ù‡, ‰‡ÂÚ „‡Ù, ̇Á˚‚‡ÂÏ˚È Ú‡ÌÁËÚË‚Ì˚Ï Á‡Ï˚͇-
ÌËÂÏ ËÒıÓ‰ÌÓ„Ó „‡Ù‡.
ê‡θÌ˚ „‡Ù˚ ‚ ̇ÒÚÓfl˘Â ‚ÂÏfl ‡Ì‡ÎËÁËÛ˛Ú Ì ‡Î„·-
‡Ë˜ÂÒÍËÏË, ‡ ÔflÏ˚ÏË ÔÂÂ·Ó Ì˚ÏË ÏÂÚÓ‰‡ÏË Ì‡ ùÇå.
èflÏ˚ ÏÂÚÓ‰˚ ‡Ì‡ÎËÁ‡ „‡ÙÓ‚. óËÒÎÂÌÌ˚ ı ‡‡ÍÚÂËÒÚË-
ÍË Ë Ô‡‡ÏÂÚ˚ ÙÛÌ͈ËÈ ÓÚ „ ‡ÙÓ‚ ÏÓÊÌÓ ÔÓÎÛ˜‡Ú¸ ̇ ÓÒÌÓ‚Â
‡Î„·‡Ë˜ÂÒÍËı ÏÂÚÓ‰Ó‚, Ò‚flÁ‡ÌÌ˚ı Ò ÔÂÓ·‡ÁÓ‚‡ÌËflÏË Ï‡Ú-
ˈ ÒÏÂÊÌÓÒÚË ËÎË Ë̈ˉÂÌÚÌÓÒÚË. é‰Ì‡ÍÓ ÓÔÚËÏËÁ‡ˆËÓÌÌ˚Â
Á‡‰‡˜Ë ËÏÂ˛Ú Ó·‡ÚÌÛ˛ ÔËÓ‰Û – Ú·ÛÂÚÒfl ̇ÈÚË „‡Ù ËÎË
˜‡ÒÚ¸ „Ó, ̇ ÍÓÚÓÓÈ ÙÛÌ͈Ëfl ÔËÌËχÂÚ ˝ÍÒÚÂχθÌÓ Á̇-
˜ÂÌËÂ. åÂÚÓ‰˚ ÔÓËÒ͇ ˝ÍÒÚÂÏÛχ, ‡Á‚ËÚ˚  ‚ χÚÂχÚ˘ÂÒÍÓÏ
‡Ì‡ÎËÁÂ, ÓÒÌÓ‚˚‚‡˛ÚÒfl ̇ ÌÂÔÂ˚‚ÌÓÒÚË ÙÛÌ͈ËÈ Ë Ëı ‡„Û-
ÏÂÌÚÓ‚. ɇÙ˚, Í‡Í ÌÓÒËÚÂÎË ÙÛÌ͈ËÈ, ÒÛ˘ÂÒÚ‚ÂÌÌÓ ‰ËÒÍÂÚ-
Ì˚. Ä̇ÎËÚ˘ÂÒÍË ÏÂÚÓ‰˚ ̇ ÌËı, Í‡Í Ô‡‚ËÎÓ, Ì ‡·ÓÚ‡˛Ú.
á‡ÚÓ Î˛·Û˛ ˜‡ÒÚ¸ ÍÓ̘ÌÓ„Ó „‡Ù‡ (ËÎË Í·ÒÒ ÍÓ̘Ì˚ı „‡-
ÙÓ‚) ÏÓÊÌÓ ÓÔ‰ÂÎËÚ¸ ÔÛÚÂÏ ÔflÏÓ„Ó ÍÓÌÒÚÛÍÚË‚ÌÓ„Ó ÔÓÒÚ-
ÓÂÌËfl Ë ‚˚˜ËÒÎÂÌËfl Á̇˜ÂÌËÈ Ú·ÛÂÏ˚ı ÙÛÌ͈ËÈ. àÏÂfl „Â-
̇ÚÓ „‡ÙÓ‚, ÏÓÊÌÓ Ó„‡ÌËÁÓ‚‡Ú¸ Ëı ‚ÓÒÔÓËÁ‚Ó‰ÒÚ‚Ó Ë
ÔÓ¯ÚÛ˜Ì˚È ‡Ì‡ÎËÁ ̇ ùÇå.
è Ë Ï Â 4. åÂÊ‰Û ÌÂÒÍÓθÍËÏË „ÓÓ‰‡ÏË, Ò‚flÁ‡ÌÌ˚ÏË ÒÂ-
Ú¸˛ ¯ÓÒÒÂÈÌ˚ı Ë ÔÓÒÂÎÓ˜Ì˚ı ‰ÓÓ„, ̇‰Ó Ó„‡ÌËÁÓ‚‡Ú¸ „Û-
ÎflÌÓ ‡‚ÚÓ·ÛÒÌÓ ‰‚ËÊÂÌËÂ. Ü·ÚÂθÌÓ ‚˚· ‡Ú¸ χ¯ÛÚ˚
‰‚ËÊÂÌËfl Ú‡Í, ˜ÚÓ·˚ ‡ÒıÓ‰˚ ‡‚ÚÓԇ͇ ̇ ·ÂÌÁËÌ ·˚ÎË ÏËÌË-
χθÌ˚ÏË.
98
ê  ¯ Â Ì Ë Â. è‰ÒÚ‡‚Ë‚ ‰Ó ÓÊÌÛ˛ ÒÂÚ¸ ‚Á‚¯ÂÌÌ˚Ï „‡ÙÓÏ,
Á‡‰‡˜Û ‚˚·Ó‡ ÓÔÚËχθÌÓ„Ó Ï‡¯ÛÚ‡ Ò‚Ó‰ËÏ Í Ì‡ıÓʉÂÌ˲
Ú‡ÍÓ„Ó ÓÒÚÓ‚‡ „‡Ù‡, ËÁ ÍÓÚÓÓ„Ó ÒÛÏχ ‚ÂÒÓ‚ ‚ÂÚ‚ÂÈ ÏËÌË-
χθ̇. ùÚÛ Á‡‰‡˜Û ÏÓÊÌÓ Â¯ËÚ¸ Ô·ÓÓÏ Ë ‚Á‚¯˂‡ÌËÂÏ
ÓÒÚÓ‚Ì˚ı ‰Â‚¸Â‚ „‡Ù‡. ➤
åÌÓ„Ë ÓÔÚËÏËÁ‡ˆËÓÌÌ˚ Á‡‰‡˜Ë ̇ „‡Ù‡ı ¯‡˛ÚÒfl Ò
ÔËÏÂÌÂÌËÂÏ Ó·ıÓ‰Ó‚ ‚¯ËÌ Ë Â·Â „‡ÙÓ‚.
凯ËÌÌ˚ Ô‰ÒÚ‡‚ÎÂÌËfl „‡ÙÓ‚. ó‡ÒÚÓ ÛÔÓÚ·ÎflÂÏÓÈ
ÙÓÏÓÈ Ô‰ÒÚ‡‚ÎÂÌËfl Ó„‡ÙÓ‚ ‚ ùÇå fl‚ÎflÂÚÒfl χÚˈ‡
ÒÏÂÊÌÓÒÚË Ä, ÒÓÒÚÓfl˘‡fl ËÁ n×n ‰‚Ó˘Ì˚ı ˝ÎÂÏÂÌÚÓ‚ a
ij
, ÓÚÏÂ-
˜‡˛˘Ëı ‰Û„Ë ÏÂÊ‰Û ‚¯Ë̇ÏË v
i
Ë v
j
.
ÖÒÎË fl˜ÂÈ͇ ÒÓ‰ÂÊËÚ ‰‚Ó˘ÌÓ ÒÎÓ‚Ó ‰ÎËÌ˚ l, ÚÓ ‰Îfl Ô‰-
ÒÚ‡‚ÎÂÌËfl Ó‰ÌÓÈ ÒÚÓÍË Ú·ÛÂÚÒfl
n
l
+ 1 fl˜ÂÂÍ. å‡Úˈ‡
ÒÏÂÊÌÓÒÚË ‡ÁÏ¢‡ÂÚÒfl ‚
n
n
l
+
1 Y n
2
fl˜ÂÈ͇ı, ıÓÚfl ‚
ÌÂÈ ÓÚϘÂÌÓ Â‰ËÌˈ‡ÏË m = m
(
r
G) ‰Û„ Ó„‡Ù‡.
ÑÎfl ÌÂÓËÂÌÚËÓ‚‡ÌÌ˚ı „‡ÙÓ‚ χÚˈ‡ ÒÏÂÊÌÓÒÚË ÒËÏÏÂ-
Ú˘̇: a
ij
= a
ji
, A = A
t
, ‰Îfl  ԉÒÚ‡‚ÎÂÌËfl Ú·ÛÂÚÒfl ‚‰‚ÓÂ
ÏÂ̸¯Â Ô‡ÏflÚË ùÇå. ÇÂÏfl Ó·‡·ÓÚÍË ÌÂÓËÂÌÚËÓ‚‡ÌÌÓ„Ó
„‡Ù‡, Ô‰ÒÚ‡‚ÎÂÌÌÓ„Ó ‚ÂıÌÂÈ ÍÓÒ˚ÌÍÓÈ Ï‡Úˈ˚ A(a
ij
, j ≥
≥ i), ÌÂÒÍÓθÍÓ ·Óθ¯ÂÂ, ˜ÂÏ ÔË ÔÓÎÌÓÈ Á‡ÔËÒË ‚ÒÂı ˝ÎÂÏÂÌ-
ÚÓ‚ χÚˈ˚ ÒÏÂÊÌÓÒÚË Ä ËÁ-Á‡ ÌÂÓ·ıÓ‰ËÏÓÒÚË ‚ÓÒÒÚ‡ÌÓ‚ÎÂÌËfl
a
ij
, j < i ÔÓ ÒËÏÏÂÚËË.
èË ‡Ì‡ÎËÁ „‡Ù‡ Ú‡Í ËÎË Ë̇˜Â ̇‰Ó ÔÓıÓ‰ËÚ¸ ‚Ò „Ó
·‡ ·ÂÁ ÔÓÔÛÒÍÓ‚. èÓ˝ÚÓÏÛ ‚ÂÏfl Ó·‡·ÓÚÍË „ ‡Ù‡ ÔË Ú‡-
ÍÓÏ Ï‡Ú˘ÌÓÏ Ô‰ÒÚ‡‚ÎÂÌËË ÔÓÔÓˆËÓ̇θÌÓ Í‚‡‰‡ÚÛ Â„Ó
ÔÓfl‰Í‡ (n
2
= V
2
).
ÖÒÎË „‡Ù
r
G ‡ÁÂÊÂÌÌ˚È: m = E << V
2
= n
2
, ÚÓ
Ô‰ÒÚ‡‚ÎÂÌËÂ Â„Ó Ï‡Úˈ˚ ÒÏÂÊÌÓÒÚË ÒÚ‡ÌÓ‚ËÚÒfl Ì‚˚„Ó‰Ì˚Ï
ËÁ-Á‡ ·Óθ¯Ó„Ó ˜ËÒ· ÌÛÎÂÈ. íÓ„‰‡ ÏÓÊÌÓ ‚ÁflÚ¸ χÚËˆÛ Ë̈Ë-
‰Â̈ËÈ B =
b
ij
, ‚ ÍÓÚÓÓÈ m ÒÚÓηˆÓ‚, n ÒÚÓÍ, ÌÓ ‚ ͇ʉÓÏ
ÒÚÓηˆÂ ÚÓθÍÓ ‰‚‡ ÌÛ΂˚ı ˝ÎÂÏÂÌÚ‡: Ó‰ËÌ ‚ ÒÚÓÍÂ, Óڂ˜‡-
˛˘ÂÈ
̇˜‡Î¸ÌÓÈ
‚¯ËÌÂ
‰Û„, Ë Ó‰ËÌ ‚ ÒÚÓÍÂ, Óڂ˜‡˛˘ÂÈ ÍÓ-
̘ÌÓÈ
‚¯ËÌÂ
‰Û„Ë.
ÑÎfl
Ô‰ÒÚ‡‚ÎÂÌËfl Ú‡ÍÓÈ Ï‡Úˈ˚ ÔÓÚÂ-
·ÛÂÚÒfl
n
×
m
‰‚Ó˘Ì˚ı ‡Áfl‰Ó‚. é̇ ‚˚„Ӊ̇ Î˯¸ ÔË m < n.
àÌÓ„‰‡
ËÒÔÓθÁÛ˛Ú
‰Îfl
χ¯ËÌÌÓ„Ó
Ô‰ÒÚ‡‚ÎÂÌËfl
„‡Ù‡
‰‚Ûı-
ÒÚÓÓÌÌËÈ Ï‡ÒÒË‚ ÌÓÏÂÓ‚ ̇˜‡Î¸Ì˚ı Ë ÍÓ̘Ì˚ı ‚¯ËÌ ‰Û„.
ɇÙÛ Ì‡ ËÒ. 2.39 Óڂ˜‡ÂÚ Ô‰ÒÚ‡‚ÎÂÌËÂ
1 2 1133556
243624465
.
99
í‡Í Í‡Í ‰Îfl Á‡ÔËÒË Î˛·Ó„Ó ˜ËÒ· ÓÚ 1 ‰Ó n Ú·ÛÂÚÒfl
[lgn] + 1 ‰‚Ó˘Ì˚ı ‡Áfl‰Ó‚, ÚÓ ÔÓÚ·Ì˚È Ó·˙ÂÏ Á‡ÔËÒË ·Û‰ÂÚ
‡‚ÂÌ 2m([lgn + 1)·ËÚ, ˜ÚÓ Ú Â·ÛÂÚ Y (2mlgn)/l fl˜ÂÂÍ Ï‡-
¯ËÌÌÓÈ Ô‡ÏflÚË.
ÖÒÎË m = cn
2
, ˜ÚÓ ·˚‚‡ÂÚ Û ÔÎÓÚÌ˚ı „‡ÙÓ‚, ÚÓ ÒÔËÒÓÍ Â-
·Â ı‡ÌËÚ¸ ÏÂÌ ‚˚„Ó‰ÌÓ, ˜ÂÏ Ï‡ÚËˆÛ ÒÏÂÊÌÓÒÚË.
é·ÓÁ̇˜ËÏ ˜ÂÂÁ
r
G(v) ÏÌÓÊÂÒÚ‚Ó ‚¯ËÌ Ó„‡Ù‡, ‚ ÍÓÚÓ-
˚ ÏÓÊÌÓ ÔÓÔ‡ÒÚ¸ ËÁ v. Ç Ó„‡ÙÂ
r
G ÒÚÂÔÂ̸ β·ÓÈ ‚¯Ë-
Ì˚ S(v) ‡‚̇ ÒÛÏÏ ÔÓÎÛÒÚÂÔÂÌÂÈ Á‡ıÓ‰‡ s
+
(v) Ë ËÒıÓ‰‡
s
–
(v). á̇˜ËÚ,
r
G(v) = s
–
(v) – ÍÓ΢ÂÒÚ‚Û ‰Û„, ËÒıÓ‰fl˘Ëı
ËÁ v.
r
G(v) ̇Á˚‚‡˛Ú ÓÍÂÒÚÌÓÒÚ¸˛ ‚¯ËÌ˚ v ‚ „‡ÙÂ
r
G . éÍ-
ÂÒÚÌÓÒÚ¸˛ Á‡ıÓ‰‡ ·Û‰ÂÚ ÏÌÓÊÂÒÚ‚Ó ‚¯ËÌ
r
G
−1
(),v ËÁ ÍÓÚÓ-
˚ı ‚˚ıÓ‰flÚ ‰Û„Ë, Ó͇̘˂‡˛˘ËÂÒfl ‚ v.
r
G
−
=
1
()v s
+
(v).
ëÚÛÍÚÛ ÓÈ (ËÎË ÒÔËÒÍÓÏ) ÒÏÂÊÌÓÒÚË Ó„‡Ù‡ ̇Á˚‚‡ÂÚ-
Òfl Ú‡·Îˈ‡, ‚ ÍÓÚÓÓÈ n ÒÚÓÍ ‚ˉ‡
vv:().
r
G
()
ÑÎfl „‡Ù‡ ̇ ËÒ. 2.39 ËÏÂÂÏ ÒÎÂ‰Û˛˘Û˛ ÒÚÛÍÚÛÛ ÒÏÂÊ-
ÌÓÒÚË:
v
1
: {v
2
, v
3
, v
6
}
v
2
: {v
4
}
v
3
: {v
2
, v
4
}
êàë. 2.39. 鄇٠(‡) Ë Â„Ó Ï‡Ú Ëˆ˚ (·, ‚)
100
v
4
: ∅
v
5
: {v
4
, v
6
}
v
6
: {v
5
}
ÖÒÎË ÏÂÚ͇ ‚¯ËÌ˚ ‡ÒÔÓ·„‡ÂÚÒfl ‚ Ó‰ÌÓÈ fl˜ÂÈÍÂ, ÚÓ ‰Îfl
ı ‡ÌÂÌËfl ÒÔËÒ͇ ÒÏÂÊÌÓÒÚË Ú·ÛÂÚÒfl n + m = V + E
fl˜ÂÂÍ. ÑÎfl ÌÂÓËÂÌÚËÓ‚‡ÌÌÓ„Ó „‡Ù‡ ÚÓÈ Ê ÍÓÌÙË„Û‡ˆËË
ÔÓÚ·ÛÂÚÒfl n + 2m fl˜ÂÂÍ, Ë·Ó Í‡Ê‰ÓÂ Â·Ó ‚ÒÚ˜‡ÂÚÒfl ‰‚‡Ê-
‰˚ ‚ ÒÔËÒÍÂ ÒÏÂÊÌÓÒÚË.
ëÚÛÍÚÛ˚ ÒÏÂÊÌÓÒÚË ÓÚÌÓÒflÚ Í Ú‡Í Ì‡Á˚‚‡ÂÏ˚Ï ÒÔËÒÍÓ‚˚Ï
ÒÚÛÍÚÛ‡Ï ‰‡ÌÌ˚ı. éÌË ¯ËÓÍÓ ÔËÏÂÌfl˛ÚÒfl ‚ ÒÓ‚ ÂÏÂÌÌ˚ı
flÁ˚͇ı ÔÓ„‡ÏÏËÓ‚‡ÌËfl, Ëϲ˘Ëı ‡Á‚ËÚ˚ Ò‰ÒÚ‚‡ Ô‰-
ÒÚ‡‚ÎÂÌËfl Ë Ó·‡·ÓÚÍË ‰‡ÌÌ˚ı.
ëÔËÒÍË ÒÏÂÊÌÓÒÚË Û‰Ó·Ì˚ ‰Îfl Ô ËÏÂÌÂÌËfl Ú‡ÍËı ÏÂÚÓ‰Ó‚
Ó·‡·ÓÚÍË „‡ÙÓ‚, ‚ ÍÓÚÓ˚ı ÔÂÂÏÂÌÌÓ ˜ËÒÎÓ ÔÓ‰ÎÂʇ˘Ëı
ÔÓÒÏÓÚÛ ‚¯ËÌ.
ÇÒ ˜ÂÚ˚ ‚ˉ‡ χ¯ËÌÌ˚ı Ô‰ÒÚ‡‚ÎÂÌËÈ „‡ÙÓ‚ ÔÓÎÛ˜‡-
˛ÚÒfl ÌÂÒÎÓÊÌ˚ÏË ÔÂÓ·‡ÁÓ‚‡ÌËflÏË ‰Û„ ËÁ ‰Û„‡. èËÏÂÌflÚ¸
ÚÓ ËÎË ËÌÓ ËÁ ÌËı ̇‰Ó Ò Û˜ÂÚÓÏ Â‡Î¸Ì˚ı Ô‡‡ÏÂÚÓ‚ Ô‰-
ÒÚÓfl˘ÂÈ Ï‡¯ËÌÌÓÈ Ó·‡·ÓÚÍË, ‡ Ú‡ÍÊ Ë̉˂ˉۇθÌ˚ı ÓÒÓ-
·ÂÌÌÓÒÚÂÈ Ï‡¯ËÌ. ëÔËÒÍË Â·Â Ë ÓÍÂÒÚÌÓÒÚÂÈ ‚¯ËÌ Í‡Í
ÌÓ‚˚ ÒÚÛÍÚÛ˚ ‰‡ÌÌ˚ı ͇ÊÛÚÒfl ÒÓ‚ÂÏÂÌÌÂÂ, ÌÓ ˝ÙÙÂÍÚË‚-
ÌÓÒÚ¸ Ó·‡·ÓÚÍË Á‡‚ËÒËÚ ÚÓθÍÓ ÓÚ ÍÓÌÍÂÚÌ˚ı Á‡‰‡˜ Ë ÛÒÎÓ-
‚ËÈ Ó·‡·ÓÚÍË.
è Ó Ë Ò Í ‚ „ Î Û · Ë Ì Û. ùÚÓ ÏÂÚÓ‰ ÒËÒÚÂχÚ˘ÂÒÍÓ„Ó Ô·Ӈ
‚¯ËÌ „‡Ù‡, ÔË ÍÓÚÓÓÏ ÒÚÂÏflÚÒfl Í‡Í ÏÓÊÌÓ ‰‡Î¸¯Â ÛÈÚË
ÔÓ Â·‡Ï „‡Ù‡ ÓÚ ÒÚ‡ÚÓ‚ÓÈ ‚¯ËÌ˚. 燘Ë̇˛Ú ÔÓËÒÍ Ò
ÔÓËÁ‚ÓθÌÓÈ, ÌÓ ÙËÍÒËÓ‚‡ÌÌÓÈ ‚¯ËÌ˚ v
0
. Ç˚·Ë‡˛Ú ‚Â-
¯ËÌÛ w, ÒÏÂÊÌÛ˛ Ò v
0
, Ë ÔÓ‚ÚÓfl˛Ú ÔÓˆÂÒÒ ÓÚ w.
èÛÒÚ¸ ‚ ͇ÍÓÈ-ÚÓ ÏÓÏÂÌÚ Ï˚ ̇ıÓ‰ËÏÒfl ‚ ‚¯ËÌ v. ëÛ˘Â-
ÒÚ‚ÛÂÚ ‰‚ ‚ÓÁÏÓÊÌÓÒÚË ‰‡Î¸ÌÂÈ¯Â„Ó ‰‚ËÊÂÌËfl: ÎË·Ó ‚Ô‰ Í
ÌÓ‚ÓÈ ‚¯ËÌÂ, ÒÏÂÊÌÓÈ Ò v, ÎË·Ó Ì‡Á‡‰, ÂÒÎË Ì ÒÛ˘ÂÒÚ‚ÛÂÚ
ÌË Ó‰ÌÓÈ ÒÏÂÊÌÓÈ Ò v ‚¯ËÌ˚, ÍÓÚÓ‡fl Ì ·˚· ÔÓȉÂ̇
‡Ì¸¯Â.
ǯË̇, ËÁ ÍÓÚÓÓÈ ÌÂÚ ‚ÓÁÏÓÊÌÓÒÚË Ë‰ÚË ‚Ô‰, ̇Á˚-
‚‡ÂÚÒfl ËÒÔÓθÁÓ‚‡ÌÌÓÈ. àÁ Ì ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ‚ÓÁ‚‡Ú Í ÔÓ-
ÒΉÌÂÈ ÔÓȉÂÌÌÓÈ ‚¯ËÌÂ.
èÓÒΉÌÂÈ ËÒÔÓθÁÓ‚‡ÌÌÓÈ ‚¯ËÌÓÈ ·Û‰ÂÚ ÒÚ‡ÚÓ‚‡fl v
0
, ‚
ÍÓÚÓÛ˛ Ï˚ ‚ÓÁ‚‡ÚËÏÒfl, Ó·Óȉfl ‚Ò ‰Û„Ë ‚¯ËÌ˚ ÚÓÈ ÍÓÏ-
ÔÓÌÂÌÚ˚ „‡Ù‡, Í ÍÓÚÓÓÈ ÓÚÌÓÒËÚÒfl v
0
.
ç‡ ËÒ. 2.40 ‰‡Ì ÔËÏ ÔÓËÒ͇ ‚ „ÎÛ·ËÌÛ ‚ „‡Ù ÚËÔ‡ [10,
14]. í‡ÂÍÚÓËfl Ó·ıÓ‰‡ ‚¯ËÌ ÓÚϘÂ̇ ÔÛÌÍÚËÌÓÈ ÎËÌËÂÈ.
Ç ıӉ ÔÓËÒ͇ ‚ „ÎÛ·ËÌÛ ÏÓÊÌÓ ÓËÂÌÚËÓ‚‡Ú¸ ·‡ „‡Ù‡,
101
ÍÓÚÓ˚ ÔÓıÓ‰flÚ ‚ ÔflÏÓÏ Ì‡Ô‡‚ÎÂÌËË. éÌË ‚ ÒÓ‚ÓÍÛÔÌÓÒÚË
Ó·‡ÁÛ˛Ú ÓËÂÌÚËÓ‚‡ÌÌÓ ÓÒÚÓ‚ÌÓ ‰ÂÂ‚Ó Ò‚flÁ‡ÌÌÓ„Ó „‡Ù‡.
ê·‡, ÔÓ ÍÓÚÓ˚Ï Ì ÔÓıÓ‰ËÚ Ú‡ÂÍÚÓËfl ÔÓËÒ͇ ‚ „ÎÛ·ËÌÛ,
Ó·‡ÁÛ˛Ú ıÓ‰˚ ˝ÚÓ„Ó ÓÒÚÓ‚‡.
ÑÎfl ÏÌÓ„ÓÍÓÏÔÓÌÂÌÚÌÓ„Ó „‡Ù‡ ÔÓËÒÍ ‚ „ÎÛ·ËÌÛ ÓÒÛ˘ÂÒÚ‚-
Îfl˛Ú ÔÓ Í‡Ê‰ÓÈ ÍÓÏÔÓÌÂÌÚ ÓÚ‰ÂθÌÓ. ç‡ ËÒ. 2.40 Ô˂‰ÂÌ˚
ÓÒÚÓ‚ Ë ıÓ‰˚ „‡Ù‡.
åÂÚÓ‰ ÔÓËÒ͇ ‚ „ÎÛ·ËÌÛ ‰ÓÔÛÒ͇ÂÚ Ï‡¯ËÌÌÛ˛ ‡ÎËÁ‡ˆË˛.
ÑÎfl ˝ÚÓ„Ó „‡Ù Á‡‰‡˛Ú Â„Ó ÒÚÛÍÚÛÓÈ ÒÏÂÊÌÓÒÚË – Ô‡‡ÏË
vv:().
r
G
()
ç‡ Í‡Ê‰ÓÏ ¯‡„ ÓÔËÒ͇ ̇‰Ó Á̇ڸ ÏÌÓÊÂÒÚ‚Ó Â˘Â
Ì ÔÓȉÂÌÌ˚ı (ÌÓ‚˚ı) ‚¯ËÌ Ë ÔÓÒÎÂ‰Ì˛˛ ÔÓȉÂÌÌÛ˛
‚¯ËÌÛ.
óÚÓ·˚ ӷ΄˜ËÚ¸ ÔÓËÒÍ ÔÓȉÂÌÌ˚ı ‚¯ËÌ, ÔÓ ıÓ‰Û ÔÓËÒ͇
Ëı ÔÓÏ¢‡˛Ú ‚ χ„‡ÁËÌ – Ә‰¸ Ò Ó·‡ÚÌ˚Ï ÔÓfl‰ÍÓÏ ‰Ó-
ÒÚÛÔ‡. ä‡Ê‰‡fl ÔÓȉÂÌ̇fl ‚¯Ë̇ Í‡Í ·˚ Í·‰ÂÚÒfl Ò‚ÂıÛ ‚
ÒÚÓÔÍÛ ‡Ì ÔÓȉÂÌÌ˚ı, ·Î‡„Ó‰‡fl ˜ÂÏÛ Â ‚Ò„‰‡ ÏÓÊÌÓ ËÁ-
‚Θ¸ Ô‚ÓÈ. Ç Î˛·ÓÈ Ú‡ÍÚ ÔÓËÒ͇ χ„‡ÁËÌ ÒÓ‰ÂÊËÚ ‚ÂÒ¸
ÔÛÚ¸ ÓÚ ÒÚ‡ÚÓ‚ÓÈ ‰Ó ÚÂÍÛ˘ÂÈ ‚¯ËÌ˚, ÌÓ ‡ÒÔÓÎÓÊÂÌÌ˚È ‚
Ó·‡ÚÌÓÏ ÔÓfl‰ÍÂ: Ò̇˜‡Î‡ ÍÓ̈ ÔÛÚË, ÔÓÚÓÏ Ô‰˚‰Û˘‡fl
‚¯Ë̇ Ë, ̇ÍÓ̈, ÔÓÒΉÌflfl – ÒÚ‡ÚÓ‚‡fl ‚¯Ë̇. á̇˜ËÚ,
ÔË Ì‡Î˘ËË Ï‡„‡ÁË̇ ÔÓËÒÍ ‚ „ÎÛ·ËÌÛ ÔÓÁ‚ÓÎflÂÚ ÔÓÎÛ˜‡Ú¸
ÔÛÚË Ì‡ „‡ÙÂ Ò Ëı ÍÓ̈‡.
êàë. 2.40.
1 – ·‡ ÓÒÚÓ‚‡, 2 – ıÓ‰˚; Ó·ıÓ‰ ‚ „ÎÛ·ËÌÛ v
7
– v
6
– v
2
– v
1
– v
4
– v
3
– v
5
–
v
3
– v
8
– v
9
– v
10
– v
9
– v
8
– v
3
– v
4
– v
1
– v
2
– v
6
– v
7
102
íÓÔÓÎӄ˘ÂÒ͇fl ÌÛχˆËfl. ÉÓ‚ÓflÚ, ˜ÚÓ Á‡‰‡Ì‡ ÚÓÔÓÎÓ„Ë-
˜ÂÒ͇fl ÌÛχˆËfl ‚¯ËÌ Ó„ ‡Ù‡ ˜ËÒ·ÏË 1, 2, 3,..., n = V,
ÂÒÎË ‚ β·ÓÈ ‰Û„ (v
i
, v
j
), Ë‰Û˘ÂÈ ËÁ ‚ ¯ËÌ˚ v
i
‚ ‚¯ËÌÛ
v
j
, ÌÓÏ i ÏÂ̸¯Â ÌÓχ j.
ç‡ ËÒ. 2.41 Ô˂‰ÂÌ˚ ‰‚‡ Ó„‡Ù‡, Ó‰ËÌ ËÁ ÍÓÚÓ˚ı ÚÓ-
ÔÓÎӄ˘ÂÒÍË Á‡ÌÛÏÂÓ‚‡Ì, ‡ ‰Û„ÓÈ ÌÂÚ. ã˛·ÓÈ Ó„‡Ù Á‡‰‡ÂÚ
ÌÂÍÓÚÓ˚È ˜‡ÒÚ˘Ì˚È ÔÓfl‰ÓÍ Ì‡ V. íÓÔÓÎӄ˘ÂÒ͇fl ÌÛχˆËfl
Ô‚‡˘‡ÂÚ Â„Ó ‚ ÎËÌÂÈÌ˚È ÔÓfl‰ÓÍ. çÂÓ·ıÓ‰ËÏ˚Ï Ë ‰ÓÒÚ‡ÚÓ˜-
Ì˚Ï ÛÒÎÓ‚ËÂÏ ÒÛ˘ÂÒÚ‚Ó‚‡ÌËfl ÚÓÔÓÎӄ˘ÂÒÍÓÈ ÌÛχˆËË fl‚Îfl-
ÂÚÒfl ÓÚÒÛÚÒÚ‚Ë ÍÓÌÚÛÓ‚ (ˆËÍÎÓ‚) ‚ „‡ÙÂ.
ä‡Í ÛÊ ÓÚϘ‡ÎÓÒ¸, ‚ ·ÂÒÍÓÌÚÛÌÓÏ (‡ˆËÍ΢ÂÒÍÓÏ) Ó„‡-
ÙÂ
r
G ËÏÂÂÚÒfl ÔÛÚ¸ χÍÒËχθÌÓÈ ‰ÎËÌ˚, ÍÓÚÓ˚È ÌÂθÁfl Û‰-
ÎËÌËÚ¸ ÌË Ò Ì‡˜‡Î‡, ÌË Ò ÍÓ̈‡. ì ÍÓ̘ÌÓÈ ‚¯ËÌ˚ ÌÂÚ ‚˚-
ıÓ‰fl˘Ëı ‰Û„, Ó̇ fl‚ÎflÂÚÒfl ÚÛÔËÍÓ‚ÓÈ (ËÎË ÒÚÓÍÓÏ). 쉇ÎË‚ ËÁ
„‡Ù‡ ˝ÚÛ ‚¯ËÌÛ ‚ÏÂÒÚÂ Ò Ë̈ˉÂÌÚÌ˚ÏË ÂÈ ‰Û„‡ÏË, ÔÓÎÛ˜‡-
ÂÏ ÛÏÂ̸¯ÂÌÌ˚È ·ÂÒÍÓÌÚÛÌ˚ È Ó„‡Ù
r
G
1
ÔÓfl‰Í‡ n – 1. èË-
Ò‚ÓËÏ Û‰‡ÎÂÌÌÓÈ ‚¯ËÌ ÌÓÏ n. èÓ‚ÚÓËÏ Û‰‡ÎÂÌË ÚÛÔË-
ÍÓ‚ÓÈ ‚¯ËÌ˚ ‰Îfl
r
G
1
, ÔÓÎÛ˜ËÏ ÌÓ‚˚È ‡ˆËÍ΢ÂÒÍËÈ Ó„‡Ù
r
G
2
ÔÓfl‰Í‡ n – 2 Ë ‚¯ËÌÛ Ò ÌÓÏÂÓÏ n – 1. í‡ÍËÏ Ó·‡ÁÓÏ
ÔËıÓ‰ËÏ Í Ì‡˜‡Î¸ÌÓÈ ‚¯ËÌ ËÒıÓ‰ÌÓ„Ó Ó„‡Ù‡ – Â„Ó ËÒ-
ÚÓ˜ÌËÍÛ. èÓÎÛ˜ÂÌ̇fl ‚ ÔÓˆÂÒÒ ۉ‡ÎÂÌËfl ÚÛÔËÍÓ‚ ÌÛχˆËfl
‚¯ËÌ ·Û‰ÂÚ ÚÓÔÓÎӄ˘ÂÒÍÓÈ ÔÓ ÔÓÒÚÓÂÌ˲. Ç Ó‰ÌÓÏ Ë ÚÓÏ
Ê „‡Ù ÏÓÊÂÚ ·˚Ú¸ ÌÂÒÍÓθÍÓ ËÒÚÓ˜ÌËÍÓ‚ Ë ÒÚÓÍÓ‚, ÔÓ˝ÚÓÏÛ
ÓÌ ÏÓÊÂÚ ·˚Ú¸ ÚÓÔÓÎӄ˘ÂÒÍË ÛÔÓfl‰Ó˜ÂÌ ÌÂÒÍÓθÍËÏË ‡Á΢-
Ì˚ÏË ÒÔÓÒÓ·‡ÏË.
ê‡ÒÔÓÎÓÊË‚ ‚¯ËÌ˚ Ò ÌÓχÏË 1, 2,..., n ‚ ˆÂÎ˚ı ÚӘ͇ı
êàë. 2.41. ɇÙ˚:
‡ – ÌÂÛÔÓfl‰Ó˜ÂÌ, · – ÛÔÓfl‰Ó˜ÂÌ
103
˜ËÒÎÓ‚ÓÈ ÓÒË, ÔÓÎÛ˜ËÏ ÎËÌÂÈÌÛ˛ ÛÍ·‰ÍÛ „‡Ù‡. (èËÏ ÒÏ.
̇ ËÒ. 2.42, ·.)
ÑÎfl ÛÒÍÓÂÌËfl ÚÓÔÓÎӄ˘ÂÒÍÓÈ ÒÓÚËÓ‚ÍË ‚¯ËÌ Ó„‡Ù‡
̇‰Ó ÓÒÛ˘ÂÒÚ‚ËÚ¸ Ô‰‚‡ËÚÂθÌÛ˛ ‡ÁÏÂÚÍÛ ‚¯ËÌ ËÒıÓ‰ÌÓ-
„Ó „‡Ù‡, Ôӂ‰fl ̇ ÌÂÏ ÔÓËÒÍ ‚ „ÎÛ·ËÌÛ Ë ÓÔ‰ÂÎË‚ ÔÓÎÛ-
˜‡˛˘ËÈÒfl ÔË ˝ÚÓÏ ÓÒÚÓ‚ í.
ëӄ·ÒÌÓ ÏÂÚÓ‰Û ÔÓËÒ͇ ‚ „ÎÛ·ËÌÛ ‚Ò ‚¯ËÌ˚ „‡Ù‡, ̇-
˜Ë̇fl ÓÚ ÒÚ‡ÚÓ‚ÓÈ, ÏÓÊÌÓ Ò̇·‰ËÚ¸ ‚ÓÁ‡ÒÚ‡˛˘ËÏË ÏÂÚ͇ÏË
ÔÓ ÔÓfl‰ÍÛ Ó·ıÓ‰‡ ÓÒÚÓ‚ÌÓ„Ó ‰Â‚‡.
íÓÔÓÎӄ˘ÂÒ͇fl ÌÛχˆËfl „‡Ù‡ ÔÓ„‡ÏÏ˚ ÔÓÁ‚ÓÎflÂÚ ÏË-
ÌËÏËÁËÓ‚‡Ú¸ Ô‡ÏflÚ¸, ÔÓÚ·ÌÛ˛ ‰Îfl  ‡ÎËÁ‡ˆËË.
êàë. 2.42. ɇ٠G
B
(‡) Ë ÎËÌÂÈ̇fl ÛÍ·‰Í‡ „‡Ù‡ G
B
(·)
104
è Ë Ï Â 5. Ç˚˜ËÒÎÂÌË ‚˚‡ÊÂÌËfl
((x
1
+ x
2
) – x
3
x
4
)/x
5
(x
6
– x
7
)
ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ‚ ÒÓÓÚ‚ÂÚÒÚ‚ËË Ò ‰Â‚ÂÒÌ˚Ï „‡ÙÓÏ G
‚
(ËÒ.
2.42). àÁ 13 ‚¯ËÌ ¯ÂÒÚ¸ ÒÓÓÚ‚ÂÚÒÚ‚Û˛Ú ÓÔ‡ˆËflÏ, ‡ ÒÂϸ –
ÓÔ‡̉‡Ï. Ç ˝ÚÓÏ ‰Â‚ ‰ËÌÒÚ‚ÂÌÌ˚È ÚÛÔËÍ, Óڂ˜‡˛˘ËÈ
ÔÓÒΉÌÂÈ ÓÔ‡ˆËË – ‰ÂÎÂÌ˲. èËÒ‚ÓË‚ ÂÏÛ ÌÓÏ 13, Ó·˚-
‚‡ÂÏ Â„Ó Ò‚flÁË, ˜ÚÓ ÔË‚Ó‰ËÚ Í ÔÓfl‚ÎÂÌ˲ ‰‚Ûı ÌÓ‚˚ı ÚÛÔËÍÓ‚,
ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘Ëı ÓÔ‡ˆËflÏ ÛÏÌÓÊÂÌËfl Ë ‚˚˜ËÚ‡ÌËfl. ч‚ ËÏ
ÌÓχ 11 Ë 12 Ë Û‰‡ÎË‚ Ëı, ÔÓÎÛ˜ËÏ ÚË ÓÔ‡ÚÓÌ˚ı ‚Â-
¯ËÌ˚ +, ⋅ , – Ë Ó‰ÌÛ ÚÂÏË̇θÌÛ˛ ‚¯ËÌÛ. ч‚ ËÏ ÌÓχ 7,
8, 9, 10 Ë Û‰‡ÎË‚ Ëı, ÔÓÎÛ˜ËÏ Â˘Â ¯ÂÒÚ¸ ÚÂÏË̇θÌ˚ı ‚Â-
¯ËÌ, ÔÓϘÂÌÌ˚ı ÔÂÂÏÂÌÌ˚ÏË x
1
, x
2
, x
3
, x
4
, x
6
, x
7
.
ãËÌÂÈ̇fl ÛÍ·‰Í‡ Ú‡ÍËÏ Ó·‡ÁÓÏ ÛÔÓfl‰Ó˜ÂÌÌÓ„Ó ‰Â‚‡ ‚˚-
˜ËÒÎÂÌËfl ‡ËÙÏÂÚ˘ÂÒÍÓ„Ó ‚˚ ‡ÊÂÌËfl ‰‡Ì‡ ̇ ËÒ. 2.42, ·.
Ç˚˜ËÒÎflfl ‡ËÙÏÂÚ˘ÂÒÍÓ ‚˚‡ÊÂÌË ‚ ÒÓÓÚ‚ÂÚÒÚ‚ËË Ò ÔÓ-
ÎÛ˜ÂÌÌ˚Ï ÎËÌÂÈÌ˚Ï ÔÓfl‰ÍÓÏ, Ó·ÂÒÔ˜˂‡ÂÏ Ò‚Ó‚ÂÏÂÌÌÛ˛
„ÓÚÓ‚ÌÓÒÚ¸ ÌÛÊÌ˚ı ÓÔ‡̉ӂ ‰Îfl ‚ÒÂı ÓÔ‡ÚÓÓ‚. ➤
èÓËÒÍ ‚ ¯ËËÌÛ. éÒÌӂ̇fl ˉÂfl ÔÓËÒ͇ ‚ ¯ËËÌÛ Ì‡ „‡-
Ù – ÒÍÓÂȯËÈ ÔÓÒÏÓÚ ‚ÒÂı ‚¯ËÌ, ÒÏÂÊÌ˚ı Ò ‰‡ÌÌÓÈ.
èÓËÒÍ Ì‡˜Ë̇˛Ú ‚ Ô ÓËÁ‚ÓθÌÓÈ ‚¯ËÌ v
0
∈ V. ë̇˜‡Î‡
ÔÓıÓ‰flÚ ‚Ò ·‡, ÒÏÂÊÌ˚Â Ò v
0
. èÛÒÚ¸ G(v
0
) – ÓÍÂÒÚÌÓÒÚ¸
v
0
‚ „‡Ù – ÒÓÒÚÓËÚ ËÁ ‚¯ËÌ v
1
, v
2
,..., v
k
. ç‡ ‚ÚÓÓÏ ˝Ú‡ÔÂ
ÔÓËÒ͇ ÔÓıÓ‰fl Ú ÔÓӘ‰ÌÓ ‚Ò ·‡, ÒÏÂÊÌ˚Â Ò v
1
, v
2
,..., v
k
.
ÖÒÎË G(v
i
) = {v
j1
, v
j2
,...,
v
ik
i
}, ÚÓ Ì‡ ÒÎÂ‰Û˛˘ÂÏ ˝Ú‡Ô ÔÓÒχÚ-
Ë‚‡˛Ú ·‡, Ë̈ˉÂÌÚÌ˚ v
ij
, Ë Ú‡Í ‰‡ÎÂÂ.
òËÓÍËÈ ÔÓËÒÍ ËÏÂÂÚ Í‡Ò͇‰Ì˚È ı‡‡ÍÚ : Ò̇˜‡Î‡ ÔÓÒχ-
ÚË‚‡˛ÚÒfl ‚¯ËÌ˚, Û‰‡ÎÂÌÌ˚ ÓÚ Ì‡˜‡Î¸ÌÓÈ Ì‡ ‡ÒÒÚÓflÌË 1.
á‡ÚÂÏ ÔÓÒχÚË‚‡˛ÚÒfl ‚ ¯ËÌ˚, ÒÓ‰ËÌÂÌÌ˚Â Ò Ì‡˜‡Î¸ÌÓÈ
ÔÛÚflÏË ‰ÎËÌ˚ 2. ç‡ ÚÂÚ¸ÂÏ ˝Ú‡Ô Ô·ˇ˛Ú ‚¯ËÌ˚, ÒÓ-
‰ËÌÂÌÌ˚Â Ò Ì‡˜‡Î¸ÌÓÈ ÔÛÚflÏË ‰ÎËÌ˚ 3, Ë Ú.‰. èË ˝ÚÓÏ ‚Â-
¯ËÌ˚, ÔÓÒÏÓÚÂÌÌ˚ ̇ β·ÓÏ ˝Ú‡ÔÂ, ËÒÍβ˜‡˛ÚÒfl ËÁ ‡Ò-
ÒÏÓÚÂÌËfl ̇ ÔÓÒÎÂ‰Û˛˘Ëı ˝Ú‡Ô‡ı. èÓ˝ÚÓÏÛ ˜ÂÂÁ ÍÓ̘ÌÓÂ
˜ËÒÎÓ ˝Ú‡ÔÓ‚ ‚Ò ‚¯ËÌ˚ „‡Ù‡ ·Û‰ÛÚ ÔÓȉÂÌ˚, ÂÒÎË „‡Ù
Ò‚flÁÌ˚È. ÖÒÎË Û „‡Ù‡ ÌÂÒÍÓθÍÓ ÍÓÏÔÓÌÂÌÚ, ÚÓ ÔÓËÒÍ ‚ ¯Ë-
ËÌÛ Ó„‡ÌËÁÛ˛Ú ‰Îfl ͇ʉÓÈ ÍÓÏÔÓÌÂÌÚ˚.
è Ë Ï Â 6. ç‡ ËÒ. 2.43 ËÁÓ·‡ÊÂÌ „‡Ù ÚËÔ‡ [12, 17] Ë
ÔÓ͇Á‡Ì‡ Ú‡ÂÍÚÓËfl ÔÓËÒ͇, ̇˜Ë̇˛˘Â„ÓÒfl ‚ ‚¯ËÌ v
5
. êÂ-
·‡, ‚Â‰Û˘Ë ËÁ ÚÂÍÛ˘ÂÈ ‚¯ËÌ˚ ‚ ÒÏÂÊÌ˚ ‚¯ËÌ˚, ‡ÌÂÂ
Ì ‚ÒÚ˜‡‚¯ËÂÒfl, ÓÚϘÂÌ˚ ÊËÌ˚ÏË ÎËÌËflÏË. éÌË Ó·‡ÁÛ˛Ú
ÓÒÚÓ‚ÌÓ ‰ÂÂ‚Ó Ò ÍÓÌÂÏ v
5
. ê·‡, Ì ‚ӯ‰¯Ë ‚ ‰Â‚Ó,
fl‚Îfl˛ÚÒfl ıÓ‰‡ÏË. ➤
èÛÒÚ¸
Á‡‰‡Ì‡
ÒÚÛÍÚÛ‡
ÒÏÂÊÌÓÒÚË
„‡Ù‡
–
Ú‡·Îˈ‡
105
(v
:
G(v)). èÓËÒÍ ‚ ¯ËËÌÛ ÏÓÊÌÓ ÔÓËÁ‚Ó‰ËÚ¸ ÔÓ ˝ÚÓÈ Ú‡·ÎË-
ˆÂ, Ì „Îfl‰fl ̇ ËÁÓ·‡ÊÂÌË „‡Ù‡.
ÑÎfl Ôӂ‰ÂÌËfl ¯ËÓÍÓ„Ó ÔÓËÒ͇ ̇ „‡ÙÂ, Á‡‰‡ÌÌÓÏ Ú‡·-
ÎˈÂÈ ÒÏÂÊÌÓÒÚË ‚¯ËÌ, ̇‰Ó Ó„‡ÌËÁÓ‚‡Ú¸ ‰‚‡ χÒÒË‚‡: ÛÔÓ-
fl‰Ó˜ÂÌÌ˚È Ï‡ÒÒË‚ – “Ә‰¸” Ë ÌÂÛÔÓfl‰Ó˜ÂÌÌ˚È Ï‡ÒÒË‚
“ÌÓ‚˚”. è‰ ̇˜‡ÎÓÏ ÔÓËÒ͇ “Ә‰¸” ÔÛÒÚ‡, ‡ ‚ χÒÒË‚Â
“ÌÓ‚˚” ÒÓ‰ÂʇÚÒfl ‚Ò ‚¯ËÌ˚ „‡Ù‡.
èӈ‰ۇ ÔÓËÒ͇ Ú‡ÍÓ‚‡. ÖÒÎË ÔÓËÒÍ Ì‡˜‡Ú¸ ËÁ ‚¯ËÌ˚ v,
ÚÓ Ì‡‰Ó ÔӉ·ڸ ÒÎÂ‰Û˛˘ÂÂ:
1) ‚¯ËÌÛ v ËÁ˙flÚ¸ ËÁ χÒÒË‚‡ “ÌÓ‚˚” Ë ÔÓÏÂÒÚËÚ¸ ‚
“Ә‰¸”;
2) Ó·‡ÚËÚ¸Òfl Í Ô‚ÓÈ ‚¯ËÌ “Ә‰˔ ê Ë ÔÓÒÂÚËÚ¸
ê;
3) ÔÓÒ¢ÂÌË ê ÒÓ‰ÂÊËÚ ˆËÍÎ ÔÓ ‚¯ËÌ‡Ï v′ ∈ G(P):
ÂÒÎË v′ ÌÓ‚‡fl, ÚÓ ËÒÍβ˜ËÚ¸ v′ ËÁ ÌÓ‚˚ı Ë ÔÓÏÂÒÚËÚ¸ ‚
Ә‰¸. ò‡„Ë Ôӈ‰Û˚ 2 Ë 3 Ó·ÂÒÔ˜˂‡˛Ú ·ÂÒÔÓ‚ÚÓÌÓÂ
ÔÓÒ¢ÂÌË ‚ÒÂı ‚¯ËÌ ÚÓÈ ÍÓÏÔÓÌÂÌÚ˚ „‡Ù‡, ‚ ÍÓÚÓÓÈ ÒÓ-
‰ÂÊËÚÒfl ÒÚ‡ÚÓ‚‡fl ‚¯Ë̇ v.
èÓËÒÍ ‚ ¯ËËÌÛ, Í‡Í Ë ÔÓËÒÍ ‚ „ÎÛ·ËÌÛ, ÔÓÁ‚ÓÎflÂÚ Ì‡ıÓ‰ËÚ¸
ÔÛÚË ÏÂÊ‰Û Î˛·˚ÏË ‰‚ÛÏfl ‚¯Ë̇ÏË v Ë w. ç‡‰Ó Ì‡˜‡Ú¸ ÔÓ-
ËÒÍ ‚ v Ë ‚ÂÒÚË Â„Ó ‰Ó ÔÓfl‚ÎÂÌËfl w. ÖÒÎË ÔÛÚ¸ ÓÚ v Í w ÂÒÚ¸,
Ú‡ÍËÏ Ó·‡ÁÓÏ ÚÓ ÓÌ ·Û‰ÂÚ Ó·Ì‡ÛÊÂÌ.
ä‡Í ÓÚϘ‡ÎÓÒ¸ ‡ÌÂÂ, ÔË ÔÓËÒÍ ‚ „ÎÛ·ËÌÛ ‚ χ„‡ÁËÌ Ó-
„‡ÌËÁÛÂÚÒfl Á‡ÔÓÏË̇ÌË ‚ÒÂı ‚¯ËÌ, ÔÓȉÂÌÌ˚ı ÓÚ ÒÚ‡ÚÓ-
êàë. 2.43. òËÓÍËÈ ÔÓËÒÍ ËÁ v
5
(Í ÔËÏÂÛ 6):
1) r
1
, r
2
, r
3
; 2) r
4
, r
5
; 3) r
6
, r
7
, r
8
; 4) r
9
, r
10
; 5) r
11
; 1 – ·‡ ÓÒÚÓ‚‡, 2 – ı Ó‰˚
106
‚ÓÈ ‰Ó ÚÂÍÛ˘ÂÈ. ùÚÓÚ ÔÛÚ¸ ÏÓÊÂÚ Ó͇Á‡Ú¸Òfl Ì ҇Ï˚Ï ÍÓÓÚÍËÏ,
ÂÒÎË Ï˚ ̇ ͇ÍÓÏ-ÚÓ ¯‡„ ÌÂÛ‰‡˜ÌÓ Û„ÎÛ·ËÎËÒ¸. ë ÔÓÏÓ˘¸˛
¯ËÓÍÓ„Ó ÔÓËÒ͇ ÔÓÒÚÓ ÔÓÒÚÓËÚ¸ ͇ژ‡È¯ËÈ ÔÛÚ¸ ‰Îfl β-
·ÓÈ Ô‡˚ ‚¯ËÌ. ÖÒÎË ‚ ÓÔËÒ‡ÌÌÓÈ ‚˚¯Â Ôӈ‰Û ‚Ó ‚ÂÏfl
ˆËÍ΢ÂÒÍÓ„Ó Ô·Ӈ 3 ÓÚÏÂÚËÚ¸ ‰Îfl ͇ʉÓÈ ‚¯ËÌ˚ v′
‚¯ËÌÛ ê Í‡Í Ô‰¯ÂÒÚ‚Û˛˘Û˛ v′, ÚÓ ÔÓ ÓÍÓ̘‡ÌËË ÔÓËÒ͇
ÏÓÊÌÓ ÔÓÎÛ˜ËÚ¸ Ú‡·Î˘ÍÛ v : ê, ÔÓ ÍÓÚÓÓÈ ÓÔ‰ÂÎflÂÚÒfl ͇Ú-
˜‡È¯ËÈ ÔÛÚ¸ ËÁ v ‚ w. é·‡ÁÛÂÏ ÔÓÒΉӂ‡ÚÂθÌÓÒÚ¸ v
0
, v
1
,
v
2
,..., ‚ ÍÓÚÓÓÈ v
0
= w, ‡ v
5
= p(v
s–1
), s = 1, 2, 3,.... ÖÒÎË ÔË
s = k ‚Ô‚˚ v
s
= v, ÚÓ ‚¯ËÌ˚ v
0
, v
1
, v
2
,..., v
k–1
, v
k
Ó·‡ÁÛ˛Ú
ÔÛÚ¸ ‰ÎËÌ˚ k ÓÚ w ‰Ó v, ‡ ÔÓ˝ÚÓÏÛ ËÌ‚ÂÒ̇fl ÔÓÒΉӂ‡ÚÂθ-
ÌÓÒÚ¸ v
k
= v, v
k–1
,..., v
1
, v
0
= w ‰‡ÂÚ ËÒÍÓÏ˚È ÔÛÚ¸ ËÁ v ‚ w,
ÍÓÚÓ˚È fl‚ÎflÂÚÒfl ͇ژ‡È¯ËÏ ÔÓ ÔÓÒÚÓÂÌ˲.
ç‡ ÔËχı, Ô˂‰ÂÌÌ˚ı ‚ ˝ÚÓÏ Ë Ô‰˚‰Û˘ÂÏ ÔÛÌÍÚ‡ı,
ÏÓÊÌÓ Û·Â‰ËÚ¸Òfl, ˜ÚÓ Í‡Í ÔÓËÒÍ ‚ ¯ËËÌÛ, Ú‡Í Ë ÔÓËÒÍ ‚ „ÎÛ-
·ËÌÛ ÔÓÁ‚ÓÎfl˛Ú ÔÓÎÛ˜‡Ú¸ ÓÒÚÓ‚Ì˚ ‰Â‚¸fl, ıÓ‰˚, ‡ Ò ÌËÏË Ë
·‡ÁËÒÌ˚ ˆËÍÎ˚ „‡Ù‡. èË ˝ÚÓÏ ÔÓˆÂÒÒ ÔÓËÒ͇ Ú Â·ÛÂÚ
ÚÓθÍÓ Á̇ÌËfl ÒÔËÒ͇ ÒÏÂÊÌÓÒÚË „‡Ù‡, ‡ ÌÂ Â„Ó Ì‡„Îfl‰ÌÓ„Ó
ËÁÓ·‡ÊÂÌËfl. èÓÒχÚË‚‡fl ¢ ‡Á ÔÓÒÚÓÂÌËfl ÓÒÚÓ‚ÌÓ„Ó ‰Â-
‚‡ ÔÓËÒÍÓÏ ‚ ¯ËËÌÛ ‚ ÔÓÒΉÌÂÏ ÔËÏ (ÒÏ. ËÒ. 2.43),
ÏÓÊÌÓ Û·Â‰ËÚ¸Òfl, ˜ÚÓ ÒÛ˘ÂÒÚ‚ÛÂÚ ÚÓθÍÓ Ó‰Ì‡ ‚ÓÁÏÓÊÌÓÒÚ¸
Ô ÓÈÚË ËÁ ̇˜‡Î¸ÌÓÈ ‚¯ËÌ˚ v
5
‚ β·Û˛ ‰Û„Û˛ ‚¯ËÌÛ
„‡Ù‡ w ≠ v
5
. ë˜ËÚ‡fl v
5
– Ó‰Ó̇˜‡Î¸ÌËÍÓÏ, ‡ w – Â„Ó ÔÓÚÓÏ-
͇ÏË, Ï˚ ‚ˉËÏ, ˜ÚÓ ÔÓÚÓÏÍË ÛÔÓfl‰Ó˜Ë‚‡˛ÚÒfl ÔÓ ÔÓÍÓÎÂÌËflÏ
¯‡„‡ÏË Ôӈ‰Û˚ ÔÓËÒ͇ ‚ ¯ËËÌÛ.
ì Ô ‡ Ê Ì Â Ì Ë Â . ÑÓ͇ÊËÚÂ, ˜ÚÓ „‡Ù fl‚ÎflÂÚÒfl ‰‚Û‰ÓθÌ˚Ï
ÚÓ„‰‡ Ë ÚÓθÍÓ ÚÓ„‰‡, ÍÓ„‰‡ ÓÌ Ì ÒÓ‰ÂÊËÚ ÔÓÒÚ˚ı ˆËÍÎÓ‚
̘ÂÚÌÓÈ ‰ÎËÌ˚. èÓÒÚÓÈÚ ‰‚ Ôӈ‰Û˚ ÔÓ‚ÂÍË „‡Ù‡ ̇
‰‚Û‰ÓθÌÓÒÚ¸, ÓÒÌÓ‚‡ÌÌ˚ ̇ ÔÓËÒÍ ‚ „ÎÛ·ËÌÛ Ë Ì‡ ÔÓËÒÍ ‚
¯ËËÌÛ.
ëèàëéä ãàíÖêÄíìêõ
éÒÌӂ̇fl
1. ÅÂÎÓ‚ Ç.Ç., ÇÓÓ·¸Â‚ Ö.å., ò‡Ú‡ÎÓ‚ Ç.Ö. íÂÓËfl „‡ÙÓ‚.–å.: Ç˚ Ò¯‡fl
¯ÍÓ·, 1976.
2. Ň҇Í ê., 뇇ÚË í. äÓ̘Ì˚ „‡Ù˚ Ë ÒÂÚË. – å.: ç‡Û͇, 1974.
3. á˚ÍÓ‚ Ä.Ä. éÒÌÓ‚˚ ÚÂÓËË „‡ÙÓ‚. – å.: ç‡Û͇, 1987.
4. äËÒÚÓÙˉÂÒ ç. íÂÓËfl „‡ÙÓ‚. Ä Î„ÓËÚÏ˘ÂÒÍËÈ ÔÓ‰ıÓ‰. – å.: åË,
1978.
5. é é. íÂÓËfl „‡ÙÓ‚. – å.: ç‡Û͇, 1968.
6. ï‡‡Ë î. íÂÓËfl „‡ÙÓ‚. – å.: åË, 1973.
7. ìËÎÒÓÌ ê. ǂ‰ÂÌË ‚ ÚÂÓ˲ „‡ÙÓ‚. – å.: åË, 1977.
8. 낇ÏË å., íıÛ·ÒË‡Ï‡Ì ä. ɇÙ˚, ÒÂÚË Ë ‡Î„ÓËÚÏ˚. – å.: åË, 1984.