Составители:
Рубрика:
79
Ïîäìíîæåñòâî âåðøèí, óäîâëåòâîðÿþùèõ îáîèì ñâîéñòâàì, ñîñòàâ-
ëÿþò ÿäðà ãðàôà ñ ó÷åòîì îòíîøåíèÿ ïðåäïî÷òåíèÿ Ð
f
.
Ïóñòü å∈K (ãäå K êîíòóð) åñòü ýëåìåíò (îáúåêò), ðàññìàòðèâàåìûé
êàê ýêâèâàëåíòíûé äðóãèì îáúåêòàì èç êîíòóðà K â ãðàôå G. Ïîëîæèì,
÷òî v∈VK ïðåâîñõîäèò å, åñëè ñóùåñòâóåò e'∈K òàêîé, ÷òî v ïðåâîñõî-
äèò e', ò. å. v ïðåâîñõîäèò K â öåëîì, òàêîå ïðåîáðàçîâàíèå â òåîðèè
ãðàôîâ íàçûâàåòñÿ ñòÿãèâàíèåì êîíòóðà K.
Íà îñíîâå ââåäåííîãî îòíîøåíèÿ ïðåâîñõîäñòâà ðàçðàáîòàí àëãîðèòì,
êîòîðûé ïîçâîëÿåò âåñòè ïîèñê ÿäåð ãðàôà ñîâìåñòíî ñî ñòÿãèâàíèåì
âñòðå÷àþùèõñÿ êîíòóðîâ. Îñíîâíûå ýòàïû àëãîðèòìà :
1. Ðåøåíèå çàäà÷è ïîèñêà êîíòóðîâ â ãðàôå è ïîëó÷åíèå âåêòîðà V ñ
íîìåðàìè êîíòóðîâ.
2. Â öèêëàõ ïðîñìîòðà êîíòóðîâ è âåðøèí âíå êîíòóðà îïðåäåëåíèå
âåðøèí âíå êîíòóðà, ïðåâîñõîäÿùèõ õîòÿ áû îäíó âåðøèíó êîíòóðà, è
èñêëþ÷åíèå òàêîãî êîíòóðà èç âåêòîðà V.
Îñòàâøèåñÿ â âåêòîðå V âåðøèíû è êîíòóðû ñîñòàâëÿþò ÿäðà ãðàôà.
Åñëè ÿäåð ãðàôà áîëüøå îäíîãî, òî îíè íåñðàâíèìû ïî èíôîðìàöèè,
ñîäåðæàùåéñÿ â ãðàôå, ïîýòîìó íåîáõîäèì äîïîëíèòåëüíûé àíàëèç
îáúåêòîâ ñðàâíåíèÿ.
4.7.8. Îïèñàíèå ìàøèííîãî àëãîðèòìà ïîèñêà ÿäåð ãðàôà
Âîçìîæíûé âàðèàíò àëãîðèòìà âêëþ÷àåò ñëåäóþùèå øàãè.
1. Ââîä áóëåâîé ìàòðèöû ñìåæíîñòè ãðàôà (S) è åå ðàçìåðà (n).
2. Âûçîâ ïîäïðîãðàììû ïîèñêà êîíòóðîâ CONTUR (S, n, V, nk),
ãäå S, n âõîäíûå äàííûå, à ðåçóëüòàòû: V âåêòîð íîìåðîâ êîíòóðîâ â
ãðàôå, nk êîëè÷åñòâî êîíòóðîâ.
3. Öèêë k=1(1)nk (ïî íîìåðàì êîíòóðîâ)
4. { öèêë i=1(1)n (âûäåëåíèå âåðøèí êîíòóðà)
5. { åñëè (V
i
=k) (âåðøèíà V
i
âõîäèò â êîíòóð k )
6. { öèêë j=1(1)n (âûäåëåíèå âåðøèí âíå êîíòóðà)
7. { åñëè (V
i
≠V
j
∧ S
ij
=1) ( âåðøèíà âíå êîíòóðà V
j
ïðåâîñõîäèò âåðøèíó èç êîíòóðà V
i
)
8. { öèêë m=1(1)n (èñêëþ÷åíèå âåðøèí êîíòóðà)
9. { åñëè (V
m
=k) (ýòî âåðøèíà êîíòóðà )
V
m
=0 ; (èñêëþ÷åíèå íîìåðà êîíòóðà
èç âåêòîðà V )
10. } (êîíåö öèêëà ïî m)
