Составители:
Рубрика:
66
4.5.2. Îïèñàíèå ìàøèííîãî àëãîðèòìà ïîèñêà êîíòóðîâ â ãðàôå
Âîçìîæíûé âàðèàíò ìàøèííîãî àëãîðèòìà ìîæåò âêëþ÷àòü ñëåäóþ-
ùèå îñíîâíûå øàãè.
1. Ââîä ìàòðèöû ñìåæíîñòè îðãðàôà (S) è åå ðàçìåðà (n).
2. Îáíóëåíèå V âåêòîðà âåðøèí êàê íåîáðàáîòàííûõ è NK-ñ÷åò÷è-
êà êîíòóðîâ.
3. Öèêë i=1(1)n (ïî âåðøèíàì âåêòîðà V)
{ åñëè (V
i
= 0) (âåðøèíà íå îáðàáîòàíà)
{ ïîëó÷åíèå ïî ïîäïðîãðàììå äëÿ âåðøèíû V
i
âåêòîðà
òðàíçèòèâíîãî çàìûêàíèÿ (Z);
òðàíñïîíèðîâàíèå ìàòðèöû S (ST);
ïîëó÷åíèå âåêòîðà îáðàòíîãî òðàíçèòèâíîãî
çàìûêàíèÿ (ZÎ);
NK=NK + 1; (ïîëó÷åíèå íîìåðà êîíòóðà)
4. öèêë j=i(1)n (äëÿ îïðåäåëåíèÿ âåðøèí êîíòóðà)
{åñëè (Z
j
≥0 è ZÎ
j
≥0 ) (íàéäåíà âåðøèíà êîíòóðà)
{ V
j
=NK; (çàíåñåíèå íîìåðà êîíòóðà â âåêòîð V )
5. öèêë m=1(1)n(ïîäàâëåíèå ñâÿçåé âåðøèí êîíòóðà)
{ S
mj
=0; S
jm
=0; (îáíóëåíèå ñòðîêè è ñòîëáöà j â S )
} (êîíåö öèêëà ïî m)
}
} (êîíåö öèêëà ïî j )
}
} (êîíåö öèêëà ïî i )
6. Âûâîä ðåçóëüòàòîâ: V, NK (âåêòîð êîíòóðîâ è èõ êîëè÷åñòâî).
Íà îñíîâå ïîëó÷åííîãî âåêòîðà êîíòóðîâ V ìîæíî èçîáðàçèòü îðã-
ðàô G ñ âûäåëåííûìè êëàññàìè ýêâèâàëåíòíîñòåé ( êîíòóðàìè).
4.5.3. Ïîñòðîåíèå ãðàôà êîíòóðîâ
Ðèñ. 4.4,à ïîêàçûâàåò, êàê ìîæíî óïîðÿäî÷èòü êëàññû ýêâèâàëåíò-
íûõ îáúåêòîâ, îáðàçóþùèõ êîíòóðû, äëÿ ãðàôà íà ðèñ. 4.3. Íà ðèñ. 4.4,á
ïîêàçàí ãðàô ñàìèõ êîíòóðîâ êàê îòäåëüíûõ îáúåêòîâ, ïîñëå óäàëåíèÿ
êðàòíûõ äóã ìåæäó êîíòóðàìè. Ïîäîáíîå ïðåäñòàâëåíèå êîíòóðà â âèäå
îäíîãî îáúåêòà íàçûâàåòñÿ ñòÿãèâàíèåì êîíòóðà.
Ãðàô êîíòóðîâ, ïîëó÷åííûé íà îñíîâå îòíîøåíèÿ R': ñóùåñòâóåò ïóòü
èç êëàññà K
r
â K
s
, ÿâëÿåòñÿ òðàíçèòèâíûì, ðåôëåêñèâíûì, àñèììåòðè÷-
íûì (íå èìååò âñòðå÷íûõ äóã), çíà÷èò, îí îòðàæàåò ÷àñòè÷íûé ïîðÿäîê, ò.
å. ÿâëÿåòñÿ êâàçèñåðèåé, à ïîñêîëüêó â ñèëó îòíîøåíèÿ íåðàçëè÷èìîñòè
Страницы
- « первая
- ‹ предыдущая
- …
- 64
- 65
- 66
- 67
- 68
- …
- следующая ›
- последняя »
