Овчаров Л.А. и др. Математические модели информационых процессов и управления
Подождите немного. Документ загружается.
58
àÁ Ú‡·Îˈ˚ ÒÓÓÚ‚ÂÚÒÚ‚Ëfl, ÓÔËÒ˚‚‡˛˘ÂÈ ‡ÁϘÂÌÌ˚È ÏÛθ-
ÚË„‡Ù Ù‡Á˚ ‚ ÔËÏ 14, ΄ÍÓ Û‚Ë‰ÂÚ¸, ˜ÚÓ Â ÏÓÊÌÓ
Ú‡ÍÚÓ‚‡Ú¸ Í‡Í Ô‰ÒÚ‡‚ÎÂÌË ÏÓ‰ÂÎË M
Ù
= 〈W; R
1
, R
2
, R
3
, R
4
〉,
‚ ÍÓÚÓÓÈ ÓÒÌÓ‚‡ÌËÂÏ ÒÎÛÊËÚ ÏÌÓÊÂÒÚ‚Ó ÌÓÏÂÓ‚ ÒÎÓ‚ W = {1,
2, 3, 4, 5, 6, 7}, ‡ Ò˄̇ÚÛÓÈ – ÒÂÏÂÈÒÚ‚‡ ÌÓÏÂÓ‚ ÒÎÓ‚:
R
1
= {{3}, {7}, {7}, {7}} Óڂ˜‡ÂÚ ·ÛÍ‚‡Ï ä, Ç, É, î, ‚ÒÚ˜‡-
˛˘ËÏÒfl ‚ ÓÚ‰ÂθÌ˚ı ÒÎÓ‚‡ı Ù‡Á˚;
R
2
= {{1, 3}, {1, 3}, {1, 3}, {4, 5}, {6, 7}} Óڂ˜‡˛Ú Ô‡‡Ï ÒÎÓ‚,
ÒÓ‰Âʇ˘Ëı ·ÛÍ‚˚ Ñ, Ö, ë, á, é;
R
3
= {{1 , 3, 6}, {4, 5, 7}, {1, 3, 4}} ÒÓ‰ÂÊËÚ ÚÓÈÍË ÒÎÓ‚
Ù‡Á˚, Ëϲ˘Ëı ·ÛÍ‚˚ Ö, Ä, ì;
R
4
= {{2, 3, 4, 6}, {1, 3, 4, 6}} Óڂ˜‡ÂÚ „ÛÔÔ‡ ËÁ ˜ÂÚ˚Âı
ÒÎÓ‚ Ù‡Á˚, ÒÓ‰Âʇ˘Ëı ·ÛÍ‚˚ à, í.
Ç ÌÂÍÓÚÓ˚ı ËÒÚÓ˜ÌË͇ı ÏÓ‰ÂÎË Ì‡Á˚‚‡˛Ú Ì „ËÔ„‡Ù‡-
ÏË, ‡ ÏÓ„‡Ù‡ÏË (ÒÓ͇˘ÂÌË ÓÚ ÏÓ‰ÂθÌÓ„Ó „‡Ù‡).
å˚ ‚ˉËÏ, ˜ÚÓ Ó·˚ÍÌÓ‚ÂÌÌ˚È „‡Ù, ÒÓÒÚÓfl˘ËÈ ËÁ ‚¯ËÌ Ë
Ô‡ ‚¯ËÌ (· 1-„Ó Ë 2-„Ó ÔÓfl‰Í‡), fl‚ÎflÂÚÒfl ÏÓ‰Âθ˛ Ò
Ò˄̇ÚÛÓÈ ÚËÔ‡ 1, 2 ̇‰ ÏÌÓÊÂÒÚ‚ÓÏ Â„Ó ‚¯ËÌ.
ê‡ÒÒÏÓÚÂÌÌ˚ È ‚ ÔËÏ 14 ÏÛθÚË„‡Ù Ò ‡ÁϘÂÌÌ˚ÏË
·‡ÏË ˝Í‚Ë‚‡ÎÂÌÚÂÌ ÏÓ„‡ÙÛ å
Ù
, Ò˄̇ÚÛ‡ ÍÓÚÓÓ„Ó ËÏÂÂÚ
ÚËÔ 1, 2, 3, 4.
à Á Ó Ï Ó Ù Ë Á Ï „ ‡ Ù Ó ‚. ä‡ÍË „‡Ù˚ ÏÓÊÌÓ Ò˜ËÚ‡Ú¸ ÒÓ‚-
Ô‡‰‡˛˘ËÏË ËÎË ÌÂÒÛ˘ÂÒÚ‚ÂÌÌÓ ‡Á΢‡˛˘ËÏËÒfl ÚÓθÍÓ ÒÔÓ-
ÒÓ·ÓÏ Ëı Ô‰ÒÚ‡‚ÎÂÌËfl?
ç‡ ËÒ. 2.26 ÔË‚Ó‰fl ÚÒfl ‡ÁÌ˚ „ÂÓÏÂÚ˘ÂÒÍË ӷ˙ÂÍÚ˚:
Í‚‡‰‡Ú Ò ‰Ë‡„Ó̇ÎflÏË G
Í
Ë ÚÂÚ‡˝‰ ‚ Ô·Ì G
Ú
(ËÎË ÚÂ-
Û„Óθ̇fl ÔËÁχ). é·ÓÁ̇˜‡fl ‚¯ËÌ˚ Í‚‡‰‡Ú‡ ˆËÙ‡ÏË, ‡
êàë. 2.26
59
ÚÂÚ‡˝‰‡ – ·ÛÍ‚‡ÏË, ÓÔ‰ÂÎËÏ ˝ÚË „‡Ù˚ Ëı ÌÓÒËÚÂÎflÏË Ë
Ò˄̇ÚÛ‡ÏË:
G
Í
= (V
1
, E
1
), G
Ú
= (V
2
, E
2
),
V
1
= {v
1
, v
2
, v
3
, v
4
}, E
1
= {{v
1
, v
2
}, {v
1
, v
3
}, {v
1
, v
4
}, {v
2
, v
3
},
{v
2
, v
4
}, {v
3
, v
4
}},
V
2
= {v
a
, v
b
, v
c
, v
d
}, E
2
= {{v
a
, v
b
}, {v
a
, v
c
}, {v
a
, v
d
}, {v
b
, v
c
},
{v
b
, v
d
}, {v
c
, v
d
},
V
1
= V
2
= 4, E
1
= E
2
= 6.
ÖÒÎË Ó‰ÌÓÁ̇˜ÌÓ ÓÚÓ·‡ÁËÚ¸ V
1
Ë V
2
, ̇ÔËÏ ÔÓÎÓÊË‚ f:
v
1
→ v
a
, v
2
→ v
b
, v
3
→ v
c
, v
4
→ v
d
, ÚÓ Â·‡Ï Í‚‡‰‡Ú‡ ·Û‰ÛÚ
Ó‰ÌÓÁ̇˜ÌÓ ÒÓÓÚ‚ÂÚÒÚ‚Ó‚‡Ú¸ ·‡ ÚÂÚ‡˝‰‡, Í‡Í ˝ÚÓ ‚ˉÌÓ ËÁ
‡Á‚ÂÌÛÚ˚ı Á‡ÔËÒÂÈ ÏÌÓÊÂÒÚ‚ E
1
Ë Ö
2
. è˂‰ÂÌÌ˚ „‡Ù˚
G
Í
Ë G
Ú
Ò ‡·ÒÚ‡ÍÚÌÓÈ ÚÓ˜ÍË ÁÂÌËfl Ó‰Ë̇ÍÓ‚˚, ͇ʉ˚È ËÁ
ÌËı – ÚÓθÍÓ ‡Á̇fl „ÂÓÏÂÚ˘ÂÒÍË ÙÓχ Ô‰ÒÚ‡‚ÎÂÌËfl
4-ÍÎËÍË K
4
. ➤
Ñ‚‡ „‡Ù‡ G Ë G
∗
̇Á˚‚‡˛Ú ËÁÓÏÓÙÌ˚ÏË (Ë Ò˜ËÚ‡˛Ú ‡·-
ÒÚ‡ÍÚÌÓ Ì‡Á΢ËÏ˚ÏË), ÂÒÎË ÏÂÊ‰Û Ëı ÌÓÒËÚÂÎflÏË ÏÓÊÌÓ
ÛÒÚ‡ÌÓ‚ËÚ¸ Ú‡ÍÓ ‚Á‡ËÏÓÓ‰ÌÓÁ̇˜ÌÓ ÓÚÓ·‡ÊÂÌË f: V ↔ V
∗
,
ÍÓÚÓÓ Ô‚ӉËÚ ÒÏÂÊÌ˚ ‚¯ËÌ˚ Ô ‚Ó„Ó „‡Ù‡ ‚ ÒÏÂÊ-
Ì˚ ‚¯ËÌ˚ ‚ÚÓÓ„Ó „‡Ù‡. àÁÓÏÓÙËÁÏ Ó·ÓÁ̇˜‡˛Ú Ú‡Í:
G Y G
∗
. èË ËÁÓÏÓ ÙËÁÏ „‡ÙÓ‚ ÒÓ ı ‡ÌflÂÚÒfl Í‡Í ÒÏÂÊÌÓÒÚ¸
‚¯ËÌ, Ú‡Í Ë ÒÏÂÊÌÓÒÚ¸ ·Â. ꇂÂÌÒÚ‚‡ V = n = V
∗
,
R= m = R
∗
– ÌÂÓ·ıÓ‰ËÏ˚ ÔËÁ̇ÍË ËÁÓÏÓÙËÁχ, ÌÓ ÌÂ
‰ÓÒÚ‡ÚÓ˜Ì˚Â.
ç‡ ËÒ. 2.27 Ô˂‰ÂÌ˚ ÌÂËÁÓÏÓÙÌ˚ „‡Ù˚ G
6
Ë G
7
Ó‰ÌÓ„Ó Ë ÚÓ„Ó Ê ÚËÔ‡ (5, 5). ì·Â‰ËÚ¸Òfl ‚ ˝ÚÓÏ ÔӢ ‚Ò„Ó
Ú‡Í. ǯË̇ „‡Ù‡ G
7
Ë̈ˉÂÌÚ̇ ˜ÂÚ˚ÂÏ Â·‡Ï, ‡ ‚ G
6
χÍÒËχθÌÓ ˜ËÒÎÓ Â·Â, ‚˚ıÓ‰fl˘Ëı ËÁ ‚¯ËÌ˚ v
1
, ‡‚ÌÓ
ÚÂÏ.
ÇÂÌÂÏÒfl Í ÒÓÔÓÒÚ‡‚ÎÂÌ˲ Í‚‡‰‡Ú‡ Ò ‰Ë‡„Ó̇ÎflÏË Ë ÚÂÚ‡-
˝‰‡.
䂇‰‡Ú ËÏÂÂÚ ÚÓ˜ÍÛ ÔÂÂÒ˜ÂÌËfl ‰Ë‡„Ó̇ÎÂÈ, Ì fl‚Îfl˛˘Û-
˛Òfl ‚¯ËÌÓÈ „‡Ù‡, ‡ Û ÚÂÚ‡˝‰‡ ·‡, ÍÓÏ ‚¯ËÌ, Ó·-
˘Ëı ÚÓ˜ÂÍ Ì ËϲÚ. ÉÂÓÏÂÚ˘ÂÒÍË G
Í
Ë G
Ú
ÒÛ˘ÂÒÚ‚ÂÌÌÓ ‡Á-
΢Ì˚.
íÂÚ‡˝‰ – ÔÎÓÒÍËÈ „‡Ù, ‡ Í‚‡‰‡Ú Ò ‰Ë‡„Ó̇ÎflÏË ÌÂÔÎÓÒ-
60
ÍËÈ, ıÓÚfl ÓÌË ËÁÓÏÓÙÌ˚. á̇˜ËÚ, Ò‚ÓÈÒÚ‚Ó „‡Ù‡ ·˚Ú¸ ÔÎÓÒ-
ÍËÏ (Ì Ëϲ˘ËÏ Ì‡ ÔÎÓÒÍÓÒÚË ÚÓ˜ÂÍ ÔÂÂÒ˜ÂÌËfl ·Â, ÓÚ-
΢Ì˚ı ÓÚ ‚¯ËÌ) Ì ÒÓı‡ÌflÂÚÒfl ÔË ËÁÓÏÓÙËÁÏÂ. ÉÂÓÏÂÚ-
˘ÂÒÍË „‡Ù˚ ËÏÂ˛Ú ·ÓΠÚÓÌÍÛ˛ ÒÚÛÍÚÛÛ, ˜ÂÏ ‡·ÒÚ‡ÍÚ-
Ì˚Â. ɇÙ˚, ‰Îfl ÍÓÚÓ˚ı ÒÛ˘ÂÒÚ‚Û˛Ú ËÁÓÏÓÙÌ˚ ÔÎÓÒÍËÂ
„‡Ù˚ (ËÎË ÔÎÓÒÍË ‡ÎËÁ‡ˆËË), ̇Á˚‚‡˛ÚÒfl Ô·̇Ì˚ÏË.
ÖÒÎË „‡Ù G Ô·̇ ÂÌ Ë ÓÔËÒ˚‚‡ÂÚ ÒıÂÏÛ ÒÓ‰ËÌÂÌËfl ˝ÎÂ-
ÏÂÌÚÓ‚ ˝ÎÂÍÚÓÌÌÓ„Ó ÛÒÚÓÈÒÚ‚‡, ÚÓ ‰Îfl ˝ÚÓÈ ÒıÂÏ˚ ÒÛ˘ÂÒÚ-
‚ÛÂÚ ‚ÓÁÏÓÊÌÓÒÚ¸ ‡ÎËÁ‡ˆËË Ì‡ Ó‰ÌÓÒÎÓÈÌÓÈ ÏÓÌÚ‡ÊÌÓÈ
Ô·ÚÂ.
èËÏÂÓÏ ÌÂÔ·̇ÌÓ„Ó „‡Ù‡ fl‚ÎflÂÚÒfl ËÁÓ·‡ÊÂÌÌ˚È Ì‡
ËÒ. 2.28, ‡ ÔÓÎÌ˚È ‰‚Û‰ÓθÌ˚È „‡Ù
K
3, 3
.
ùÚÓ
„‡Ù ÚËÔ‡ (6, 9).
í Ë ‚‡Ê‰Û˛˘Ëı ‰Óχ Ì ÏÓ„ÛÚ ÔÓÎÓÊËÚ¸ ͇ʉ˚È ÔÓ ÚË
‰ÓÓÊÍË Í ÚÂÏ ÍÓÎÓ‰ˆ‡Ï Ú‡Í, ˜ÚÓ·˚ ÓÌË Ì ÔÂÂÒÂ͇ÎËÒ¸.
çÂÔ·̇ÌÓÈ fl‚ÎflÂÚÒfl Ë 5-ÍÎË͇ K
5
, ËÁÓ·‡ÊÂÌ̇fl ̇ ËÒ.
2.28,
·.
Ç ÚÂıÏÂÌÓÏ ÔÓÒÚ‡ÌÒÚ‚Â Ö
3
β·ÓÈ ÍÓ̘Ì˚È „‡Ù ÚËÔ‡
(n, m) ‰ÓÔÛÒ͇ÂÚ ÛÍ·‰ÍÛ ·ÂÁ ÔÂÂÒ˜ÂÌËfl ·Â.
í Â Ó Â Ï ‡ 1. ã˛·ÓÈ ÍÓ̘Ì˚È „‡Ù (ÏÛθÚË„‡Ù) Ô‰ÒÚ‡-
‚ËÏ ‚ Ö
3
„ÂÓÏÂÚ˘ÂÒÍËÏ „‡ÙÓÏ, Û ÍÓÚÓÓ„Ó Â·‡ Ì ËϲÚ
Ó·˘Ëı ÚÓ˜ÂÍ, ÓÚ΢Ì˚ı ÓÚ ‚¯ËÌ „‡Ù‡.
ÑÓ͇ÊÂÏ ˝ÚÓ ÍÓÌÒÚÛÍÚË‚ÌÓ. ê‡ÒÔÓÎÓÊËÏ ‚¯ËÌ˚ v
1
, v
2
,
v
3
,..., v
n
̇ ÓÒË ‡·ÒˆËÒÒ X Ë Ôӂ‰ÂÏ ˜ÂÂÁ Ì m ‡Á΢Ì˚ı
ÔÓÎÛÔÎÓÒÍÓÒÚÂÈ π
1
, π
2
,..., π
m
, ‡ÒÔÓÎÓÊÂÌÌ˚ı ÔÓ‰ ‡Á΢Ì˚ÏË
ۄ·ÏË Ì‡ÍÎÓ̇ Í ÍÓÓ‰Ë̇ÚÌÓÈ ÔÎÓÒÍÓÒÚË X, Y. ÖÒÎË „‡Ù
·ÂÁ ÔÂÚÂθ, ÚÓ Í‡Ê‰ÓÏÛ Â· Û r
j
‚ ÔÎÓÒÍÓÒÚË π
j
ÔÓÒÚ‡‚ËÏ ‚ ÒÓ-
ÓÚ‚ÂÚÒÚ‚Ë ÔÓÎÛÓÍÛÊÌÓÒÚ¸, ÍÓ̈˚ ÍÓÚÓÓÈ ÒÓ‚Ô‡‰‡˛Ú Ò ÍÓÌ-
êàë. 2.27. çÂËÁÓÏÓÙÌ˚ „‡Ù˚
61
êàë. 2.28. çÂÔ·̇Ì˚ „‡Ù˚
ˆ‡ÏË r
j
. ÖÒÎË ‚ „‡Ù ÂÒÚ¸ ÔÂÚÎË: r
i
= (v
i
, v
i
), ÚÓ Ëı Ô‰ÒÚ‡-
‚ËÏ ÓÍÛÊÌÓÒÚflÏË, ÔÓıÓ‰fl˘ËÏË ˜ÂÂÁ v
i
‚ ÔÎÓÒÍÓÒÚË π
i
. ê·-
‡ ÔÓÎÛ˜ÂÌÌÓ„Ó „ÂÓÏÂÚ˘ÂÒÍÓ„Ó „‡Ù‡ Ì ËÏÂ˛Ú ÔÂÂÒ˜ÂÌËÈ
ÔÓ ÔÓÒÚÓÂÌ˲. ➤
ç‡ ËÒ.
2.29
ËÁÓ·‡ÊÂÌ „‡Ù
G
8
“˜ÂÎӂ˜ÂÍ ·ÂÁ ¯ÂË”
(a)
Ë Â„Ó
ÔÓÒÚ‡ÌÒÚ‚ÂÌÌÓ ‡ÁÌÂÒÂÌË ÔÓ ÔÛ˜ÍÛ ¯ÂÒÚË ÔÓÎÛÔÎÓÒÍÓÒ-
ÚÂÈ (·).
óËÒÎÓ‚˚ ı‡‡ÍÚÂËÒÚËÍË „‡ÙÓ‚. óËÒÎÓ‚˚  ı‡‡ÍÚÂËÒÚË-
ÍË „‡Ù‡, ÒÓı‡Ìfl˛˘ËÂÒfl ÔË ËÁÓÏÓ ÙÌ˚ı ÓÚÓ·‡ÊÂÌËflı, Ú.Â.
Ó·˘Ë ‰Îfl ‚ÒÂı „‡ÙÓ‚, ËÁÓÏÓÙÌ˚ı ‰‡ÌÌÓÏÛ, ̇Á˚‚‡˛Ú ˜ËÒ-
·ÏË „‡Ù‡. èÓÒÚÂȯËÏË ˜ËÒ·ÏË „‡Ù‡ G fl‚Îfl˛ÚÒfl ˜ËÒÎÓ
‚¯ËÌ n = n(G) = V(G) Ë ˜ËÒÎÓ Â·Â m = m (G) =
=R(G).
êàë. 2.29.
62
ëÚÂÔÂ̸˛ ‚¯ËÌ˚ v S(v) ̇Á˚‚‡˛Ú ˜ËÒÎÓ Â·Â, ÒÏÂÊ-
Ì˚ı Ò v ‚ „‡Ù G. ëÚÂÔÂÌË ı‡‡ÍÚÂËÁÛ˛Ú ÓÍÂÒÚÌÓÒÚË ‚Â-
¯ËÌ. ÖÒÎË ÔË ËÁÓÏÓÙËÁÏ G Y G
∗
‚¯ËÌ v ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ
v
∗
, ÚÓ Ëı ÒÚÂÔÂÌË ÒÓ‚Ô‡‰‡˛Ú, Ú.Â. s(v) = s(v
∗
), Ë·Ó ËÁÓÏÓÙËÁÏ
ÒÓı ‡ÌflÂÚ Ë̈ˉÂÌÚÌÓÒÚ¸ · ‚¯Ë̇Ï. ëÚÂÔÂ̸ ‚ ¯ËÌ˚
s(v) – ÎÓ͇θ̇fl ˜ËÒÎÓ‚‡fl ı‡‡ÍÚÂËÒÚË͇ „‡Ù‡. ÖÒÎË s(v) =
= 1, ÚÓ ‚¯Ë̇ ̇Á˚‚‡ÂÚÒfl ‚ËÒfl˜ÂÈ, ÂÒÎË s(v) = 0, ÚÓ ËÁÓÎË-
Ó‚‡ÌÌÓÈ.
ç‡ÁÓ‚ÂÏ ÒÂÏÂÈÒÚ‚ÓÏ Ì‡·Ó ÒÚÂÔÂÌÂÈ
S = {s(v
1
), s(v
2
),..., s(v
n
)}.
Ç ÌÂÏ ÌÂÍÓÚÓ˚ ˜ËÒ· ÔÓ‚ÚÓfl˛ÚÒfl; s(v) ≥ 0 Ë s(v) ≤ n.
çÂÍÓÚÓ˚ ˆÂÎ˚ ˜ËÒ· ÓÚ ÂÁ͇ [0, n] ÓÚÒÛÚÒÚ‚Û˛Ú.
ÖÒÎË S
∗
– ÒÂÏÂÈÒÚ‚Ó ÒÚÂÔÂÌÂÈ „‡Ù‡ G
∗
Y G, ÚÓ, Ә‚ˉÌÓ,
S
∗
= S Í‡Í Ì‡·Ó ˚ Ó‰ÌËı Ë Ú ı Ê ˜ËÒÂÎ. èÓ˝ÚÓÏÛ S – ÍÓÎÎÂÍ-
ÚË‚Ì˚È ËÌ‚‡Ë‡ÌÚ „‡Ù‡.
óËÒ· „‡Ù‡ n Ë m Ì ÌÂÁ‡‚ËÒËÏ˚ ‰Û„ ÓÚ ‰Û„‡. í‡Í ͇Í
͇ʉ˚È Ô ÓÒÚÓÈ „‡Ù G ÔÓfl‰Í‡ n “·Óθ¯Â” N
n
Ë “ÏÂ̸¯Â”
K
n
, ‡ Û K
n
˜ËÒÎÓ m = n(n – 1)/2, ÚÓ ˜ËÒÎÓ Â·Â Î˛·Ó„Ó Ô Ó-
ÒÚÓ„Ó „ ‡Ù‡ (·ÂÁ ÔÂÚÂθ Ë Í‡ÚÌ˚ı ·Â) Û‰Ó‚ÎÂÚ‚Ó flÂÚ ÌÂ-
‡‚ÂÌÒÚ‚‡Ï
0 ≤ m(G) ≤ n(n – 1)/2.
ì Ô ‡ Ê Ì Â Ì Ë Â. èÛÒÚ¸ G Ô Â‰ÒÚ‡‚ÎflÂÚ ÒÓ·ÓÈ Ó·˙‰ËÌÂÌË k
ÌÂÔÂÂÒÂ͇˛˘Ë ıÒ fl ˜‡ÒÚÂÈ G = G
1
+ G
2
+ ... + G
k
. ÑÓ͇ÊËÚÂ.
˜ÚÓ m(G) = (n – k)(n – k + 1)/2. ➤
ǂ‰ÂÏ Â˘Â ÚË ˜ËÒ· „‡Ù‡:
ϕ(G) – ÔÎÓÚÌÓÒÚ¸ „ ‡Ù‡ – ˜ËÒÎÓ ‚ ¯ËÌ Ï‡ÍÒËχθÌÓÈ
ÍÎËÍË, ‚ıÓ‰fl˘ÂÈ ‚ G;
ε(G) – ÌÂÔÎÓÚÌÓÒÚ¸ „ ‡Ù‡, ÒÓ‚Ô‡‰‡˛˘‡ fl Ò ÔÎÓÚÌÓÒÚ¸˛ ‰Ó-
ÔÓÎÌËÚÂθÌÓ„Ó „‡Ù‡ G;
γ(G) – ı ÓχÚ˘ÂÒÍÓ ˜ËÒÎÓ – ̇ËÏÂ̸¯Â ÍÓ΢ÂÒÚ‚Ó
ˆ‚ÂÚÓ‚, ‚ ÍÓÚÓ ˚ ÏÓÊÌÓ Ó͇ÒËÚ¸ ‚¯ËÌ˚ G Ú‡Í, ˜ÚÓ·˚ ͇Ê-
‰ÓÂ Â·Ó ËÁ R(G) ËÏÂÎÓ ‡ÁÌÓˆ‚ÂÚÌ˚ ÍÓ̈˚.
àÌ‚‡Ë‡ÌÚÌÓÒÚ¸ ÔÎÓÚÌÓÒÚË ϕ(G) = ϕ(G
∗
), „‰Â G
∗
Y G, –
ÒΉÒÚ‚Ë ÒÓı‡ÌÂÌËfl ÍÎËÍ ÔË ËÁÓÏÓÙËÁÏÂ. í‡Í Í‡Í ε(G) =
=
ϕ(G), „‰Â
G = K
n
– G, ‰ÓÔÓÎÌÂÌË „‡Ù‡ G, ‡ ‰ÓÔÓÎÌÂÌËÂ
ÒÓı‡ÌflÂÚÒfl ÔË ËÁÓÏÓÙËÁÏÂ, ÚÓ ÌÂÔÎÓÚÌÓÒÚ¸ „‡Ù‡ ÚÓÊÂ
fl‚ÎflÂÚÒfl ˜ËÒÎÓÏ „‡Ù‡.
ëÓ‰ÂʇÚÂθÌÓ ε(G) ÂÒÚ¸ ˜ËÒÎÓ ‚¯ËÌ Ì‡Ë·Óθ¯Â„Ó ·ÂÁ-
·ÂÌÓ„Ó ÔÓ‰„‡Ù‡ „ ‡Ù‡ G, Ú.Â. ÏÓ˘ÌÓÒÚ¸ χÍÒËχθÌÓ„Ó ÌÂ-
Á‡‚ËÒËÏÓ„Ó ÔÓ‰ÏÌÓÊÂÒÚ‚‡ ‚¯ËÌ „‡Ù‡. Ö„Ó Â˘Â Ì‡Á˚‚‡˛Ú
χÍÒËχθÌ˚Ï ˜ËÒÎÓÏ ÌÂÁ‡‚ËÒËÏÓÒÚË „‡Ù‡ G.
63
è Ë Ï Â 15. Ç ÍÓÏËÚÂÚ ËÁ ÒÂÏË ˜ÎÂÌÓ‚ 1, 2, 3, 4, 5, 6, 7
ËϲÚÒfl ‰‚ „ÛÔÔ˚: “΂˚” – 1, 2, 3 Ë “Ô‡‚˚” – 4, 5, 6, 7
(ÔÓÎÌ˚ı ‰ËÌÓÏ˚¯ÎÂÌÌËÍÓ‚), ‡ ˜ÎÂÌ Ô‚ÓÈ „ÛÔÔ˚ 2 ˜‡ÒÚÓ
‡Á‰ÂÎflÂÚ Û·ÂʉÂÌËfl ˜ÎÂ̇ 4 ‰Û„ÓÈ „ÛÔÔ˚. èÓÒÚÓËÏ „‡Ù
G
10
(ËÒ. 2.30), Óڇʇ˛˘ËÈ Ë‰ÂÈÌ˚ ҂flÁË ˜ÎÂÌÓ‚ ÍÓÏËÚÂÚ‡,
Ë Ì‡È‰ÂÏ ‚Ò ‚ıÓ‰fl˘Ë ‚ ÌÂ„Ó ÍÎËÍË. àı Ә‚ˉÌÓ 3: K
3
, ‚Íβ-
˜‡˛˘‡fl ˜ÎÂÌÓ‚ Ô‚ÓÈ „ÛÔÔ˚, K
4
– ˜ÎÂÌÓ‚ ‚ÚÓÓÈ „ÛÔÔ˚, Ë
K
2
– ‰ËÔÓθ Ò ‚¯Ë̇ÏË 2 Ë 4. äÎËÍÓ‚Ó ˜ËÒÎÓ ˝ÚÓ„Ó „‡Ù‡
ϕ(G
10
) = 4 = ϕ(K
4
), Ú‡Í Í‡Í K
4
– χÍÒËχθ̇fl ÔÓ ˜ËÒÎÛ ˜ÎÂÌÓ‚
ÍÎË͇ „‡Ù‡ G
10
. êÂ·Ó {2, 4} ÒÎÛÊËÚ “ÏÓÒÚÓÏ” ËÎË Ô¯ÂÈ-
ÍÓÏ, ‚ ÓÚÒÛÚÒÚ‚ËË ÍÓÚÓÓ„Ó ÍÓÏËÚÂÚ ‡ÒÔ‡ÎÒfl ·˚ ̇ ‰‚ ÌÂÒ‚flÁ-
Ì˚Â ÍÎËÍË: K
3
Ë K
4
. ➤
ïÓχÚ˘ÂÒÍÓ ˜ËÒÎÓ γ(G) ÂÒÚ¸ ÏËÌËχθÌÓ ˜ËÒÎÓ ˜‡ÒÚÂÈ,
̇ ÍÓÚÓ˚ ‡Á·Ë‚‡ÂÚÒfl ÌÓÒËÚÂθ V(G) Ú‡Í, ˜ÚÓ Í‡Ê‰Ó ·Ó
ËÁ R ËÏÂÂÚ ÍÓ̈˚ ‚ ‡ÁÌ˚ı ˜‡ÒÚflı. ÖÒÎË „‡Ù ‰‚Û‰ÓθÌ˚È,
Í‡Í Ì‡ÔËÏ G
5
= K
3, 4
(ÒÏ. ËÒ. 2.10, ·), ÚÓ Â„Ó ıÓχÚ˘ÂÒÍÓÂ
˜ËÒÎÓ ‡‚ÌÓ ‰‚ÛÏ.
àÌ‚‡Ë‡ÌÚÌÓÒÚ¸ ıÓχÚ˘ÂÒÍÓ„Ó ˜ËÒ· Ó·ÛÒÎÓ‚ÎÂ̇ ÚÂÏ, ˜ÚÓ
ÔË ËÁÓÏÓÙËÁÏ ÒÓı‡ÌflÂÚÒfl ÒÏÂÊÌÓÒÚ¸ Ë ˜‡ÒÚ¸ ÔÂÓ·‡ÁÛ-
ÂÚÒfl ‚ ˜‡ÒÚ¸ Ò ÒÓı‡ÌÂÌËÂÏ ‚Á‡ËÏÌ˚ı Ò‚flÁÂÈ.
2.2. åÄíêàóçõÖ èêÖÑëíÄÇãÖçàü
ÉêÄîéÇ
ë ÌÂÓËÂÌÚËÓ‚‡ÌÌ˚Ï „‡ÙÓÏ G ·ÂÁ ÔÂÚÂθ ÏÓÊÌÓ Ò‚flÁ‡Ú¸
χÚËˆÛ ÒÏÂÊÌÓÒÚË ‚¯ËÌ Ä = Ä(G) ÔÓfl‰Í‡ n×n. ÖÒÎË ‚Â-
¯Ë̇ v
i
ÒÓ‰ËÌÂ̇ ·ÓÏ Ò v
j
, ÚÓ ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘ËÈ ˝ÎÂÏÂÌÚ
a
ij
= 1. Ç ËÌÓÏ ÒÎÛ˜‡Â a
ij
= 0. ÑÎfl „‡Ù‡ G
6
̇ ËÒ. 2.27, ‡ ËÏÂ-
ÂÏ Ï‡ÚˈÛ
êàë. 2.30
64
G
0
1
1
0
1
0
0
1
1 000
0 1 0
1
0
1
6
1 2345
1
2
3
4
5
0
1 0 1 0
0
0
AA==() .
üÒÌÓ, ˜ÚÓ ÂÒÎË ÔÂÚÂθ ÌÂÚ, ÚÓ a
ii
= 0 ÔË Î˛·ÓÏ i = 1,..., n,
ÔÓ˝ÚÓÏÛ Ï‡Úˈ‡ ÒÏÂÊÌÓÒÚË ÌÂÓËÂÌÚËÓ‚‡ÌÌÓ„Ó „‡Ù‡ ËÏÂÂÚ
ÌÛÎÂ‚Û˛ „·‚ÌÛ˛ ‰Ë‡„Ó̇θ. ÖÒÎË ‚ ͇ʉÓÈ ‚¯ËÌ „‡Ù‡
ËÏÂÂÚÒfl ÔÂÚÎfl, ÚÓ Ú‡ÍÓÈ „‡Ù ÓÔËÒ˚‚‡˛Ú ÏÓ‰ËÙˈËÓ‚‡ÌÌÓÈ
χÚˈÂÈ ÒÏÂÊÌÓÒÚË:
˜
(A G)= ε
n
+ A(G),
„‰Â ε
n
– ‰ËÌ˘̇fl χÚˈ‡.
ü‚ÎflÂÚÒfl ÎË Ï‡Ú Ëˆ‡ ÒÏÂÊÌÓÒÚË ËÌ‚‡Ë‡ÌÚÓÏ „‡Ù‡?
ä‡Í ÏÂÌflÂÚÒfl Ó̇ ÔË ËÁÓÏÓÙËÁÏÂ? èÂÂËÏÂÌÛÂÏ ‚ „‡ÙÂ
G
6
̇ ËÒ. 2.27, ‡ ÔÂ‚Û˛ Ë ‚ÚÓÛ˛ ‚¯ËÌ˚. èÓÎÛ˜ËÏ „‡Ù
G
6
∗
.
Ö„Ó Ï‡Úˈ‡
G
0
1
1
0
0
1
1
0
0 1 00
1 00
1
1
1
6
1 2345
1
2
3
4
5
0
0 110
0
0
AA
∗∗
==() .
ÔÓÎÛ˜‡ÂÚÒfl ËÁ χÚˈ˚ Ä = Ä(G
6
) ÔÂÂÒÚ‡ÌÓ‚ÍÓÈ 1-È Ë 2-È
ÒÚÓÍ Ë 1-„Ó Ë 2-„Ó ÒÚÓηˆÓ‚. å‡Úˈ‡
A()G
6
∗
≠ A(G
6
).
ÑÂÈÒÚ‚ËÚÂθÌÓ, ÔÂÂÒÚ‡ÌÓ‚ÍÛ 1 Ë 2 ÒÚÓÍË Ä Ó·ÂÒÔ˜˂‡ÂÚ
ÛÏÌÓÊÂÌˠ ̇ ê
σ
Ò΂‡, ‡ ÔÂÂÒÚ‡ÌÓ‚ÍÛ ÒÚÓηˆÓ‚ 1 Ë 2 –
ÛÏÌÓÊÂÌË ̇
P
σ
−1
=
P
σ
−1
ÒÔ‡‚‡.
á‰ÂÒ¸ ˜ÂÂÁ σ Ó·ÓÁ̇˜Â̇ ÔÓ‰ÒÚ‡Ìӂ͇
1 2345
2 1 345
, ÍÓÚÓÓÈ
Óڂ˜‡ÂÚ Ï‡Úˈ‡
65
P
σ
=
0 1 000
1 00 00
001 00
000 1 0
000 01
.
Ä ÔÓ‰ÒÚ‡ÌÓ‚ÍÓÈ σ
–1
, Ó·‡ÚÌÓÈ Í σ, ·Û‰ÂÚ Ò‡Ï‡ σ, Ú‡Í Í‡Í σ⋅σ
‰‡ÂÚ Â‰ËÌ˘ÌÛ˛ ÔÓ‰ÒÚ‡ÌÓ‚ÍÛ.
èÓ˝ÚÓÏÛ
PP P
σ
σ
σ
−
−
==
1
1
. í‡ÍËÏ Ó·‡ÁÓÏ, Ï˚ ۷‰ËÎËÒ¸, ˜ÚÓ
Ä
∗
= P
σ
A
P
σ
−1
.
á̇˜ËÚ, ÔÂÂÌÛχˆËË ‚¯ËÌ 1 Ë 2 ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ Á‡ÏÂ̇
χÚˈ˚ Ä Ì‡ ÔÓ‰Ó·ÌÛ˛ ÂÈ Ä
∗
, ÔÓÎÛ˜‡˛˘Û˛Òfl ËÁ Ä Ô ÂÒÚ‡-
ÌÓ‚ÍÓÈ 1-È Ë 2-È ÒÚÓÍ Ë 1-„Ó Ë 2-„Ó ÒÚÓηˆÓ‚.
èÓ‰ÒÚ‡Ìӂ͇ σ fl‚ÎflÂÚÒfl ˝ÎÂÏÂÌÚ‡ÌÓÈ Ú‡ÌÒÔÓÁˈËÂÈ
(ÔÂÂÒÚ‡ÌÓ‚ÍÓÈ) ‰‚Ûı ‚¯ËÌ, Ó̇ ҇χ Ò· ӷ‡Ú̇: σ
–1
= σ.
èÓËÁ‚Óθ̇fl ÔÂÂÌÛÏÂӂ͇ ‚¯ËÌ τ, ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘‡fl Ó·-
˘ÂÏÛ ËÁÓÏÓÙËÁÏÛ V ↔ V
∗
, ‡ÁÎÓÊËχ ‚ ÔÓÒΉӂ‡ÚÂθÌÓÒÚ¸
Ú‡ÌÒÔÓÁˈËÈ τ = σ
1
σ
2
...γ
k
. é·‡ÚÌÓÈ ‰Îfl Ì ·Û‰ÂÚ ÔÓ‰ÒÚ‡ÌÓ‚-
͇ τ
–1
, ‰Îfl ÍÓÚÓÓÈ ‚ÂÌÓ Ô‰ÒÚ‡‚ÎÂÌË τ
–1
=
σσ σ
kk
−
−
−−
=
1
1
1
1
1
...
= σ
k
σ
k–1
...σ
1
. èÓËÁ‚‰ÂÌË ÔÓ‰ÒÚ‡ÌÓ‚ÓÍ σ
1
Ë σ
2
ÂÒÚ¸ ÔÓÒΉӂ‡-
ÚÂθÌÓ ‚˚ÔÓÎÌÂÌË ˝ÚËı ÔÓ‰ÒÚ‡ÌÓ‚ÓÍ. ã„ÍÓ ÔÓ‚ÂËÚ¸, ˜ÚÓ
(σ
1
...σ
k–1
σ
k
)(σ
k
σ
k–1
...σ
1
) ‰‡ÂÚ Â‰ËÌ˘ÌÛ˛ ÔÓ‰ÒÚ‡ÌÓ‚ÍÛ.
èË Î˛·ÓÏ ËÁÓÏÓÙËÁÏ τ ÔÓÎÛ˜‡ÂÏ
A P AP P P P AP P P
kk k k
τττ σσ σσσσ
∗
−
−−
==
1
111 1
... ... .
éÔ‰ÂÎËÚÂθ β·ÓÈ ÔÓ‰ÒÚ‡ÌÓ‚Ó˜ÌÓÈ Ï‡Úˈ˚ ‡‚ÂÌ Â‰Ë-
ÌˈÂ:
detP
τ
= det
P
τ
−
=
1
1.
í Â Ó Â Ï ‡ 2. èË ‚Á‡ËÏÌÓÓ‰ÌÓÁ̇˜ÌÓÏ ÓÚÓ·‡ÊÂÌËË τ ‚Â-
¯ËÌ „‡Ù‡ G ÔÓÎÛ˜ËÚÒfl „‡Ù
G
τ
∗
Y G, Û ÍÓÚÓÓ„Ó Ï‡Ú Ëˆ‡
ÒÏÂÊÌÓÒÚË
A()G
τ
∗
ÔӉӷ̇ χÚˈ Ä(G), ‡ ËÏÂÌÌÓ:
APAPPAP() () .GG
ττ
τ
ττ
∗
−
−
==
1
1
àÁ ˝ÚÓÈ ÚÂÓÂÏ˚ Á‡Íβ˜‡ÂÏ, ˜ÚÓ Ï‡Úˈ‡ ÒÏÂÊÌÓÒÚË Ì fl‚-
ÎflÂÚÒfl ËÌ‚‡Ë‡ÌÚÓÏ „‡Ù‡. àÁÓÏÓÙÌ˚ „‡Ù˚ ËÏÂ˛Ú Ì ӉË-
̇ÍÓ‚˚Â, ‡ ÚÓθÍÓ ÔÓ‰Ó·Ì˚ ‰Û„ ‰Û„Û Ï‡Úˈ˚, ‡Á΢‡˛˘Ë-
66
ÂÒfl ÔÂÂÒÚ‡ÌÓ‚ÍÓÈ fl‰Ó‚, ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘ÂÈ ÔÂÂÌÛχˆËË
‚¯ËÌ ÔË ËÁÓÏÓÙËÁÏÂ.
í Â Ó Â Ï ‡ 3. ëÔÂÍÚ Ï‡Úˈ˚ ÒÏÂÊÌÓÒÚË Ä Λ
Ä
{λ
1
, λ
2
,..., λ
n
}
Ì ÏÂÌflÂÚÒfl ÔË ËÁÓÏÓÙËÁÏÂ, Ú.Â. fl‚ÎflÂÚÒfl ÍÓÎÎÂÍÚË‚Ì˚Ï
ËÌ‚‡Ë‡ÌÚÓÏ „‡Ù‡.
Ñ Ó Í ‡ Á ‡ Ú Â Î ¸ Ò Ú ‚ Ó . ëÔÂÍÚ Ä ÔÓ ÓÔ‰ÂÎÂÌ˲ ÂÒÚ¸ ÒÓ‚Ó-
ÍÛÔÌÓÒÚ¸ ı‡‡ÍÚÂËÒÚ˘ÂÒÍËı ˜ËÒÂÎ – ÍÓÌÂÈ ı‡‡ÍÚÂËÒÚ˘Â-
ÒÍÓ„Ó ÔÓÎËÌÓχ ψ
Ä
(λ) = det(λε – A). éÌ Ì ÏÂÌflÂÚÒfl ÔË ËÁÓ-
ÏÓÙËÁÏÂ, Ú‡Í Í‡Í
ψ λ λε λε
τ
ττ τ
A
APAP
∗
∗−
= − = − =() ( ) ( )det det
1
= − = − =
−
det det det det(PAP A
Aττ
λε λε ψ λ() )().
1
➤
ëÔÂÍÚ Λ
Ä
– ˝ÚÓ ÒÂÏÂÈÒÚ‚Ó ÍÓÏÔÎÂÍÒÌ˚ı ˜ËÒÂÎ {λ
1
, λ
2
,...,
λ
n
}, ÒÂ‰Ë ÍÓÚÓ˚ı k ≤ n ‡Á΢Ì˚ı. é‰ÌÓ Ë ÚÓ Ê ı ‡‡ÍÚÂË-
ÒÚ˘ÂÒÍÓ ˜ËÒÎÓ λ
i
ÏÓÊÂÚ ·˚Ú¸ ÍÓÌÂÏ ψ
Ä
(λ
i
) = 0 ͇ÚÌÓÒÚË m
i
.
èË ˝ÚÓÏ Ó·flÁ‡ÚÂθÌÓ m
1
+ m
2
+ ... + m
k
= n. èÓ ÒÔÂÍÚÛ „‡Ù‡
ÏÓÊÌÓ ÓÔ‰ÂÎËÚ¸ Â„Ó ÒÚÛÍÚÛÛ, ÍÓ΢ÂÒÚ‚Ó Ë ‚Â΢ËÌÛ ˆËÍ-
ÎÓ‚.
àÁ-Á‡ ˜ÂÁ‚˚˜‡ÈÌÓÈ ÚÛ‰ÓÂÏÍÓÒÚË Ì‡ıÓʉÂÌËfl ÍÓÌÂÈ ı‡-
‡ÍÚÂËÒÚ˘ÂÒÍÓ„Ó ÔÓÎËÌÓχ Ú‡ÍÓÈ ‡Î„·‡Ë˜ÂÒÍËÈ ÔÛÚ¸ ËÁÛ˜Â-
ÌËfl ÒÚÛÍÚÛ˚ „‡Ù‡ Ô ‡ÍÚ˘ÂÒÍË Ì ÔËÏÂÌËÏ.
ê‡Á΢Ì˚Ï ÓÔ‡ˆËflÏ Ì‡‰ „‡Ù‡ÏË ÒÓÓÚ‚ÂÚÒÚ‚Û˛Ú ‡Î„·‡-
˘ÂÒÍË ÓÔ‡ˆËË Ì‡‰ Ëı Ï‡Ú Ëˆ‡ÏË ÒÎÓÊÌÓÒÚË. å‡Úˈ‡
ÒÏÂÊÌÓÒÚË ÔÓÎÌÓ„Ó „‡Ù‡ K
n
·ÂÁ ÔÂÚÂθ
A(K
n
) = I
n
– ε
n
,
„‰Â I
n
– χÚˈ‡ ÔÓfl‰Í‡ n×n, ÒÓÒÚÓfl˘‡fl ËÁ Ó‰ÌËı ‰ËÌˈ, ‡
ε
n
– ‰ËÌ˘̇fl χÚˈ‡ ÚÓ„Ó Ê ÔÓfl‰Í‡.
èË ÔÂÂıӉ ÓÚ „‡Ù‡ G Í Â„Ó ‰ÓÔÓÎÌÂÌ˲
G = K
n
– G
χÚˈ‡ ÒÏÂÊÌÓÒÚË Ä(G) Á‡ÏÂÌflÂÚÒfl ̇
A = A(
G), ‡‚ÌÛ˛
AA A I A
nnn
= −−−() ( .KG)=ε
Ñˇ„Ó̇θÌ˚ ˝ÎÂÏÂÌÚ˚ χÚˈ˚
A ÌÛ΂˚Â, ‡ ̉ˇ„Ó-
̇θÌ˚Â
a
ij
= 1– a
ij
; (i ≠ j).
ǂ‰ÂÏ ÓÔ‡ˆË˛ ÒÎÓÊÂÌËfl ÔÓ ÏÓ‰Ûβ ‰‚‡, ÓÔ‰ÂÎÂÌÌÛ˛
‰Îfl ·Ë̇Ì˚ı ÔÂÂÏÂÌÌ˚ı (˝ÎÂÏÂÌÚÓ‚ ˜ËÒÎÓ‚Ó„Ó ÔÓÎfl Z
2
= {0,
1}) X
1
Ë X
2
.
ëÛÏχ ÔÓ ÏÓ‰Ûβ ‰‚‡ Ó·ÓÁ̇˜‡ÂÚÒfl ÒËÏ‚ÓÎÓÏ ⊕: X
1
⊕ X
2
Ë
ÓÔ‰ÂÎflÂÚÒfl Ú‡·ÎˈÂÈ
67
Ú‡Í Í‡Í 1+1 ÔÓ ÏÓ‰Ûβ ‰‚‡ ‡‚ÌÓ ÌÛβ. ê‡ÁÌÓÒÚ¸ ÔÓ ÏÓ‰Ûβ
‰‚‡ ÒÓ‚Ô‡‰‡ÂÚ Ò ÒÛÏÏÓÈ, Ë·Ó –1 Ò‡‚ÌËχ ÔÓ ÏÓ‰Ûβ ‰‚‡ Ò +1
(–1 + 2 = 1). í‡ÍËÏ Ó·‡ÁÓÏ, X
1
J X
2
= X
2
J X
1
= X
1
⊕ X
2
. Ç
˝ÚËı Ó·ÓÁ̇˜ÂÌËflı ÔÂÂıÓ‰ ÓÚ Ä(G) Í Ä(G) ÏÓÊÌÓ ‚˚‡ÁËÚ¸
˜ÂÂÁ ÔÓ˝ÎÂÏÂÌÚÌÓ ÒÎÓÊÂÌË ÔÓ ÏÓ‰Ûβ ‰‚‡ χÚˈ A(K
n
) Ë
A(G):
AA A A I A
nnn
= ⊕⊕⊕(()( ).G) = K G) = ( ε
óËÒ· ËÁ Z
2
= {0, 1} ÔÂÂÏÌÓʇ˛ÚÒfl ÔÓ Ó·˘ÂÏÛ Ô ‡‚ËÎÛ:
X
1
⋅X
2
, Á‡‰‡‚‡ÂÏÓÏÛ Ú‡·ÎˈÂÈ:
燉 ˝ÎÂÏÂÌÚ‡ÏË Z
2
ÓÔ‰ÂÎfl˛Ú ‰‚‡ Îӄ˘ÂÒÍË ÓÔ‡ˆËË:
Îӄ˘ÂÒÍÛ˛ ÒÛÏÏÛ, ËÎË ‰ËÁ˙˛ÌÍˆË˛, Ó·ÓÁ̇˜‡ÂÏÛ˛ Á̇ÍÓÏ ∨ Ë
Îӄ˘ÂÒÍÓ ÔÓËÁ‚‰ÂÌËÂ, ËÎË ÍÓÌ˙˛ÌÍˆË˛, ÒÓ Á̇ÍÓÏ ∧.
퇷Îˈ˚, Á‡‰‡˛˘Ë Îӄ˘ÂÒÍÓ ÒÎÓÊÂÌËÂ Ë Îӄ˘ÂÒÍÓ ÛÏ-
ÌÓÊÂÌËÂ, Ú‡ÍÓ‚˚:
X
1
∨X
2
‡‚ÌÓ 1, ÂÒÎË ıÓÚfl ·˚ Ӊ̇ ÔÂÂÏÂÌ̇fl ‡‚̇ 1. ãÓ„Ë-
˜ÂÒÍÓ ÒÛÏÏËÓ‚‡ÌË ÒÓ‚Ô‡‰‡ÂÚ Ò Ó·˙‰ËÌÂÌËÂÏ ÏÌÓÊÂÒÚ‚.
X
1
∧X
2
‡‚ÌÓ 1, ÂÒÎË Ó·Â ÔÂÂÏÂÌÌ˚ ‡‚Ì˚ 1. ãӄ˘ÂÒÍÓ ÛÏ-
ÌÓÊÂÌË ‡‚ÌÓÒËθÌÓ ÔÂÂÒ˜ÂÌ˲ ÏÌÓÊÂÒÚ‚.
é·˙‰ËÌÂÌ˲ „‡ÙÓ‚ G
1
∪G
2
ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ Îӄ˘ÂÒÍÓÂ
(ÌÛ΂ÓÂ) ÒÛÏÏËÓ‚‡ÌË Ëı χÚˈ ÒÏÂÊÌÓÒÚË
A(G
1
∪G
2
) = A(G
1
)∧A(G
2
) = A
1
∧A
2
.
Ç ˝ÎÂÏÂÌÚ‡ı ˝ÚÓ Á̇˜ËÚ, ˜ÚÓ
aaa
ij ij ij
() () ()
.
1 2 1 2∨
= ∨
X
2
X
1
0 1
00 1
11 0
X
2
X
1
0 1
0 0 0
1 0 1
∨
∧
X
2
X
1
0 1 X
2
X
1
0 1
00 1 0 0 0
11 110 1