Составители:
Рубрика:
75
Ìèíèìàëüíîå âíåøíå óñòîé÷èâîå ïîäìíîæåñòâî íå ñîäåðæèò ñòðî-
ãî íèêàêîãî äðóãîãî âíåøíå óñòîé÷èâîãî ïîäìíîæåñòâà, íàïðèìåð äëÿ
ãðàôà íà ðèñ. 4.8 ïîäìíîæåñòâî {C,E} âíåøíå óñòîé÷èâîå è ìèíèìàëü-
íîå. Ãðàô ìîæåò îáëàäàòü íåñêîëüêèìè ìèíèìàëüíûìè âíåøíå óñòîé-
÷èâûìè ïîäìíîæåñòâàìè.
4.7.4. Ìåòîä ïîèñêà ñåìåéñòâà ìèíèìàëüíûõ
âíåøíå óñòîé÷èâûõ ïîäìíîæåñòâ (ìåòîä Ìàãó)
Èç óñëîâèÿ (4.2) ñëåäóåò, ÷òî ïîäìíîæåñòâî Ò äîëæíî ñîäåðæàòü âìå-
ñòå ñ v
i
ïî êðàéíåé ìåðå îäíó èç âåðøèí Ãv
i.
Ñëåäîâàòåëüíî, ñïðàâåäëè-
âî óñëîâèå
(∀v
i
∈V) ( v
i
∈T èëè (∃v
j
)( v
j
∈Ò è v
j
∈Ãv
i
)).
Ïóñòü x
i
=1, åñëè v
i
∈Ò è α
ij
=1 (α
ij
îïðåäåëåíî âûøå), òîãäà
1,
iijj
ii
xx
∨α =
∏∑
Òàê êàê (∀v
i
)
iijj ij
j
ij
xx x
∨α =α
∑∑
,
òî
Ô1.
Tijj
ij
x
=α=
∏∑
(4.3)
Ïðè ðàçëîæåíèè Ô
T
ïîñëå îïåðàöèé ïîãëîùåíèÿ (x∨x⋅y=x) è ïðèâå-
äåíèÿ ïîäîáíûõ ÷ëåíîâ êàæäûé ÷ëåí ýòîãî ðàçëîæåíèÿ äàåò ìèíèìàëü-
íîå âíåøíå óñòîé÷èâîå ïîäìíîæåñòâî. Äåéñòâèòåëüíî, òàêîé ÷ëåí íå
ñîäåðæèò ïåðåìåííûõ ñ îòðèöàíèåì, è ïîýòîìó èç ìíîæåñòâà âåðøèí
v
i
, ñîîòâåòñòâóþùèõ ïåðåìåííûì x
i
, âñòðå÷àþùèõñÿ â ýòîì ÷ëåíå,
íåëüçÿ óäàëèòü íè îäíó.
Ïðèìåð
Ðàññìîòðèì ãðàô (ðèñ. 4.8) è åãî áóëåâó ìàòðèöó (ðèñ. 4.9).
Òàê, äëÿ 1-é ñòðîêè ìàòðèöû ìîæíî ïîëó÷èòü âûðàæåíèå
α
AA
a ∨ α
AB
b ∨ α
AE
e = a ∨ b ∨ e.
Àíàëîãè÷íûå âûðàæåíèÿ ìîæíî ïîëó÷èòü äëÿ îñòàëüíûõ ñòðîê. Â
ñèëó (4.3)
Ô
T
= (a ∨ b ∨ e) (b ∨ a ∨ c ∨ d) c (d ∨ e) = 1.
Страницы
- « первая
- ‹ предыдущая
- …
- 73
- 74
- 75
- 76
- 77
- …
- следующая ›
- последняя »
