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

UptoLike

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

72
4.7. Âûäåëåíèå ÿäåð ãðàôà
 òåîðèè ãðàôîâ âîçìîæíî èñïîëüçîâàòü ìåòîäû îòûñêàíèÿ ÿäåð ãðà-
ôà G, ñîñòîÿùèõ èç ïîäìíîæåñòâà íåñðàâíèìûõ ìåæäó ñîáîé îáúåêòîâ,
êàê îñíîâó äëÿ âûäåëåíèÿ íàèáîëåå ïðåäïî÷òèòåëüíûõ îáúåêòîâ. Ðàñ-
ñìîòðèì ïîíÿòèÿ è ïîäõîäû, íåîáõîäèìûå äëÿ ðåøåíèÿ ýòîé çàäà÷è.
4.7.1. Âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî
Ïóñòü çàäàí ãðàô G=(V,Ã) ; ïîäìíîæåñòâî SV íàçûâàåòñÿ âíóòðåí-
íå óñòîé÷èâûì, åñëè SÃS=, ò. å. íèêàêèå äâå âåðøèíû S íå ñìåæíû
(íå ñâÿçàíû äóãîé ).
Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî âåðøèíà, èìåþùàÿ ïåòëþ (v,v), íå ìî-
æåò ïðèíàäëåæàòü âíóòðåííå óñòîé÷èâîìó ïîäìíîæåñòâó, ïîýòîìó äà-
ëåå áóäóò ðàññìàòðèâàòüñÿ òîëüêî ãðàôû áåç ïåòåëü. Äëÿ ãðàôà ñ ïåòëÿ-
ìè ìîæíî ðàññìàòðèâàòü ñîîòâåòñòâóþùèé ãðàô áåç ïåòåëü.
Ïðèìåð
Ðàññìîòðèì ãðàô íà ðèñ. 4.8. Ïîäìíîæåñòâà S
1
={A,D}, S
2
={B,E},
S
3
={A,C,D} âíóòðåííå óñòîé÷èâû. Ïðîâåðèì ýòî, íàïðèìåð, äëÿ S
1
:
ÃA={B,E}, ÃD={E},
ÃS
1
=ÃAÃD={B,E},
S
1
ÃS
1
={A,D}{B,E}=.
Ìàêñèìàëüíîå âíóòðåííå óñòîé÷èâîå ïîä-
ìíîæåñòâî. Ýòî âíóòðåííå óñòîé÷èâîå ïîä-
ìíîæåñòâî, íå ÿâëÿþùååñÿ ñîáñòâåííûì ïîä-
ìíîæåñòâîì íèêàêîãî äðóãîãî âíóòðåííå óñ-
òîé÷èâîãî ïîäìíîæåñòâà. Íàïðèìåð, â ïðå-
äûäóùåì ïðèìåðå S
1
S
3
, ãäå S
3
 ìàêñèìàëü-
íîå âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî. Ãðàô ìîæåò îáëàäàòü íåñêîëü-
êèìè ìàêñèìàëüíûìè âíóòðåííå óñòîé÷èâûìè ïîäìíîæåñòâàìè.
4.7.2. Ìåòîä ïîèñêà ñåìåéñòâà ìàêñèìàëüíûõ âíóòðåííå
óñòîé÷èâûõ ïîäìíîæåñòâ (ìåòîä Ìàãó)
Ýòîò ìåòîä èñïîëüçóåò ñâîéñòâà áóëåâûõ óðàâíåíèé. Ïóñòü S
íåêîòîðîå âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî. Ëþáîé âåðøèíå ãðà-
ôà v
i
V ïîñòàâèì â ñîîòâåòñòâèå áóëåâó ïåðåìåííóþ x
i,
ïîëàãàÿ, ÷òî,
åñëè v
i
S, òî x
i
= 0 èëè
1
i
x
=
. Ââåäåì ïåðåìåííóþ α
ij
:
äëÿ ji, åñëè v
j
Ãv
i
. å. âåðøèíû ñìåæíûå, v
j
êîíåö äóãè), òî
α
ij
=1,
Ðèñ. 4.8. Îðãðàô
áåç ïåòåëü
E
AD
CB