Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 76 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

76
Óïðîùàÿ, èìååì
Ô
T
= (a ∨ b ∨ e) c (d ∨ e) = 1,
èëè Ô
T
= acd ∨ bcd ∨ ce = 1.
Òàêèì îáðàçîì, ãðàô îáëàäàåò òðåìÿ ìèíèìàëüíûìè âíåøíå óñòîé-
÷èâûìè ïîäìíîæåñòâàìè :
{A,C,D}, {B,C,D}, {C,E}.
4.7.5. ßäðà ãðàôà
Ïóñòü çàäàí ãðàô G=(V,Ã). Ïîäìíîæåñòâî N⊂V íàçûâàåòñÿ ÿäðîì
ãðàôà G, åñëè N îäíîâðåìåííî âíóòðåííå è âíåøíå óñòîé÷èâîå ïîä-
ìíîæåñòâî, ò. å.
(∀v
i
∈N) N∩Ãv
i
=∅, (ò. å. âåðøèíû N íå ñìåæíû);
(∀v
j
∉N) N∩Ãv
j
≠∅, (ò. å. â N âõîäÿò êîíöû äóã, íà÷àëà êîòîðûõ âíå N).
Îòñþäà ñëåäóåò, ÷òî ÿäðî ñîäåðæèò âñÿêóþ âåðøèíó v
i
ñ Ãv
i
= ∅ (ò. å.
âèñÿ÷óþ âåðøèíó) è íå ñîäåðæèò âåðøèí ñ ïåòëÿìè. Î÷åâèäíî, ÷òî ∅
íå åñòü ÿäðî ãðàôà.
Ãðàô ìîæåò îáëàäàòü íåñêîëüêèìè ÿäðàìè èëè âîîáùå íå èìåòü ÿäðà.
4.7.6. Ïîèñê ÿäåð ãðàôà ( ìåòîä Ìàãó)
Ïîëàãàåì x
i
=1, åñëè v
i
∈N è ðàññìîòðèì óðàâíåíèÿ Ô
S
=1 è Ô
Ò
=1.
Òàê êàê ýòè ðàâåíñòâà äîëæíû âûïîëíÿòüñÿ, òî
Ô
N
= Ô
S
·Ô
Ò
= 1,
ò. å.
()
1,
iijj ijj
iji ij
x
õx
≠




∨α∨ α =




∏∏ ∏∑
èëè
()
1.
iijji ijj
ij ji
xxx
õ
≠


α∨ α∨ =


∏∑ ∏
(3.4)
 ðåçóëüòàòå ðåøåíèÿ óðàâíåíèÿ Ô
N
ïîëó÷èì ÿäðà ãðàôà.
Ïðèìåð
Äëÿ ãðàôà íà ðèñ. 4.8. ñîãëàñíî (3.4) ïî áóëåâîé ìàòðèöå íà ðèñ.4.9
íàõîäèì ÷ëåíû óðàâíåíèÿ Ô
N
(çàìå÷àÿ, ÷òî
xx
=0, õõ=õ, õ∨õy=x) :
(a ∨ b ∨ e) ∨ a (
b
) =
(b ∨ e) ∨ a (
b
),
b
( a ∨ b ∨ c ∨ d) ∨ b (
ñ
d
) =
b
( a ∨ c ∨ d) ∨ b (
ñ
d
),

Страницы