Составители:
Рубрика:
74
Ïðèìåð
Ðàññìîòðèì áóëåâó ìàòðèöó (ðèñ.4.9) îðãðàôà ïðåäñòàâëåííîãî íà ðèñ.
4.8.
Äëÿ ýëåìåíòîâ ìàòðèöû α
i j
= 1 ïîëó÷àåì ÷ëå-
íû óðàâíåíèÿ âèäà
0,
AB
ab abab
α∨∨=∨∨=∨
à äëÿ ýëåìåíòîâ ìàòðèöû α
ij
=0 :
11.
AÑ
a
ñañ
α∨∨=∨∨=
Ïîñêîëüêó ÷ëåíû óðàâíåíèÿ âèäà (
ab
∨
) è
(
ba
∨
) ïîäîáíû, òî óðàâíåíèå Ô
S
ñ ðàçíûìè ÷ëå-
íàìè èìååò âèä
()
()
()()()
Ô1.
S
abaeb
ñbdd e
=∨ ∨ ∨ ∨ ∨=
Óïðîùàÿ, ïîëó÷àåì
()()()
Ô1,
S
abeb
ñd d e
=∨ ∨ ∨=
è, íàêîíåö,
Ô1.
S
abd a
ñd be
=∨∨=
Òàêèì îáðàçîì, ãðàô íà ðèñ. 4.8 îáëàäàåò òðåìÿ ìàêñèìàëüíûìè
âíóòðåííå óñòîé÷èâûìè ïîäìíîæåñòâàìè : {C,E}, {B,E}, {A,C,D}.
4.7.3. Âíåøíå óñòîé÷èâîå ïîäìíîæåñòâî
Ïóñòü çàäàí ãðàô G=(V,Ã) ; ïîäìíîæåñòâî T⊂V íàçûâàåòñÿ âíåøíå
óñòîé÷èâûì, åñëè (∀v∉T) T∩Ãv ≠ ∅, ò. å. âåðøèíà v, íå ïðèíàäëåæàùàÿ
Ò, ñâÿçàíà ïî êðàéíåé ìåðå ñ îäíîé âåðøèíîé èç Ò äóãîé, íà÷àëî êîòî-
ðîé ëåæèò â VÒ. Ýòî ìîæíî çàïèñàòü òàêæå â ñëåäóþùåì âèäå:
(∀v ∈ V) ({v}∪Ãv) ∩T ≠ ∅. (4.2)
Ïðèìåð
Äëÿ ãðàôà íà ðèñ. 4.8 ïîäìíîæåñòâî {C,D,E} âíåøíå óñòîé÷èâîå,
÷òî ëåãêî ïðîâåðÿåòñÿ : T={C,D,E}, ÃA={B,E}, ÃB={A,C,D},
T∩ÃA={C,D,E}∩{B,E}={E}≠∅,
T∩ÃB={C,D,E}∩{A,C,D}={C,D}≠∅.
Î÷åâèäíî, ÷òî åñëè Ò⊂Ò'⊂V, òî Ò' âíåøíå óñòîé÷èâîå ïîäìíîæå-
ñòâî. Ëþáàÿ âèñÿ÷àÿ âåðøèíà v (Ãv=∅, ò. å. èç íåå íå èñõîäèò äóãà)
ïðèíàäëåæèò êàæäîìó âíåøíå óñòîé÷èâîìó ïîäìíîæåñòâó.
Ðèñ. 4.9. Áóëåâà
ìàòðèöà îðãðàôà
ABCDE
A0 1001
B10110
C0 0 000
D0 0 00 1
E00010
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
