Составители:
Рубрика:
72
4.7. Âûäåëåíèå ÿäåð ãðàôà
 òåîðèè ãðàôîâ âîçìîæíî èñïîëüçîâàòü ìåòîäû îòûñêàíèÿ ÿäåð ãðà-
ôà G, ñîñòîÿùèõ èç ïîäìíîæåñòâà íåñðàâíèìûõ ìåæäó ñîáîé îáúåêòîâ,
êàê îñíîâó äëÿ âûäåëåíèÿ íàèáîëåå ïðåäïî÷òèòåëüíûõ îáúåêòîâ. Ðàñ-
ñìîòðèì ïîíÿòèÿ è ïîäõîäû, íåîáõîäèìûå äëÿ ðåøåíèÿ ýòîé çàäà÷è.
4.7.1. Âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî
Ïóñòü çàäàí ãðàô G=(V,Ã) ; ïîäìíîæåñòâî S⊂V íàçûâàåòñÿ âíóòðåí-
íå óñòîé÷èâûì, åñëè 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
:
äëÿ j≠i, åñëè v
j
∈Ãv
i
(ò. å. âåðøèíû ñìåæíûå, v
j
êîíåö äóãè), òî
α
ij
=1,
Ðèñ. 4.8. Îðãðàô
áåç ïåòåëü
E
AD
CB
Страницы
- « первая
- ‹ предыдущая
- …
- 70
- 71
- 72
- 73
- 74
- …
- следующая ›
- последняя »
