Элементы теории графов. Домнин Л.Н. - 42 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
j1
v
j2
v
1
.
deg
−
v
∗
=0,
G
{v
5
, v
6
, v
7
, v
8
},
{v
5
}, {v
6
}, {v
7
} {v
8
}.
ñòåïåíüþ çàõîäà, ðàâíîé 0, è ëåãêî îòûñêèâàåòñÿ. Íàïðèìåð,
â ãðàôå íà ðèñ. 2.6 áàçà ñîñòîèò èç äâóõ âåðøèí vj1 è vj2 , à
â ãðàôå íà ðèñ. 2.7  èç îäíîé âåðøèíû v1 .
   Èç âûøåïðèâåäåííûõ óñëîâèé ñëåäóåò òàêæå, ÷òî â áàçå
íå ìîæåò áûòü äâóõ âåðøèí, ïðèíàäëåæàùèõ îäíîé è òîé
æå ñèëüíîé êîìïîíåíòå. Ïîýòîìó, åñëè ãðàô ñîäåðæèò öèê-
ëû, è, ñëåäîâàòåëüíî, õîòÿ áû îäíó ñèëüíóþ êîìïîíåíòó, ïðè-
÷åì ýòà êîìïîíåíòà îáðàçóåò âåðøèíó êîíäåíñàöèè, ó êîòîðîé
deg− v ∗ =0, òî â ãðàôå åñòü íåñêîëüêî áàç. Ýòî ñëåäñòâèå òîãî,
÷òî â áàçó ìîæíî âêëþ÷èòü ëþáóþ (íî òîëüêî îäíó!) âåðøèíó
òàêîé êîìïîíåíòû. Íàïðèìåð, â ãðàôå G íà ðèñ. 2.2 áàçó êîí-
äåíñàöèè îáðàçóåò ñèëüíàÿ êîìïîíåíòà {v5 , v6 , v7 , v8 }, çíà÷èò
èìååòñÿ ÷åòûðå îäíîâåðøèííûõ áàçû: {v5 }, {v6 }, {v7 } è {v8 }.
 îáùåì æå ñëó÷àå ÷èñëî áàç ðàâíî ïðîèçâåäåíèþ ÷èñåë âåð-
øèí â ñèëüíûõ êîìïîíåíòàõ, îáðàçóþùèõ áàçó êîíäåíñàöèè.
   Ñ ó÷åòîì èçëîæåííîãî ïîèñê áàç â îðãðàôå ìîæíî ïðîâî-
äèòü â ñëåäóþùåì ïîðÿäêå:
   1. Íàéòè âñå ñèëüíûå êîìïîíåíòû ãðàôà.
   2. Ïîñòðîèòü åãî êîíäåíñàöèþ.
   3. Íàéòè áàçó êîíäåíñàöèè.
   4. Èç êàæäîé ñèëüíîé êîìïîíåíòû, îáðàçóþùåé âåðøèíó
áàçû êîíäåíñàöèè, âçÿòü ïî îäíîé âåðøèíå.




                               42

Страницы