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

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

64
Çíà÷åíèåì 1 îòìå÷åíû âåðøèíû, íå âîøåäøèå â çàìûêàíèÿ. Îñ-
òàëüíûå âåðøèíû âõîäÿò â ïðÿìîå è (èëè) îáðàòíîå òðàíçèòèâíûå çà-
ìûêàíèÿ îò íà÷àëüíîé âåðøèíû v
1
â ñîîòâåòñòâèè ñ àëãîðèòìîì ï. 2.3.2:
1
ˆ
Ã
v
={v
1
, v
4
, v
5
, v
6
, v
7
, v
8
, v
11
} (òðàíçèòèâíîå çàìûêàíèå Z).
1
1
ˆ
Ã
v
−
={v
1
, v
2
, v
3
, v
7
, v
9
, v
10
, v
11
} (îáðàòíîå òðàíçèòèâíîå çàìûêàíèå  ZÎ).
Âåðøèíû, âîøåäøèå â îáà çàìûêàíèÿ, îáðàçóþò êîíòóð K
1
:
K
1
(v
1
)=
1
ˆ
Ã
v
∩
1
1
ˆ
Ã
v
−
= {v
1
, v
7
, v
11
}.
 âåêòîðå V â ïîçèöèÿõ âåðøèí ñ íîìåðàìè 1, 7, 11 çàíîñèòñÿ íîìåð
êîíòóðà Ê
1
, ò. å. 1 :
Íîìåðà âåðøèí ãðàôà:
Âåêòîð íîìåðîâ êîíòóðîâ V :
 ìàòðèöå ñìåæíîñòè S îáíóëÿþòñÿ ñòðîêè è ñòîëáöû ñ íîìåðàìè 1,
7, 11, òåì ñàìûì âåðøèíû ñ ýòèìè íîìåðàìè èñêëþ÷àþòñÿ èç äàëüíåé-
øåãî àíàëèçà. Åñëè â âåêòîðå V åñòü íåîáðàáîòàííûå âåðøèíû (çíà÷å-
íèå íîìåðà êîíòóðà = 0), òî ïðîäîëæàþòñÿ ýòàïû ïîèñêà êîíòóðîâ â
ãðàôå.
Ýòàï 2. Îáðàáîòêà ìàòðèöû S ïîñëå ïîäàâëåíèÿ ñâÿçåé âåðøèí
{v
1
, v
7
, v
11
}. Íà÷àëüíàÿ âåðøèíà v
2
= 0.
123456789 0111
100000010000 0
211000001001 1
300110000110 1
400011000000 4
500010000000 3
600000101000 3
700000000001 1
800000000000 4
900100000000 1
01 10011000100 1
11 10001100001 2
01211121311
||S||:
1
ˆ
Ã
v
1
1
ˆ
Ã
v
−
123456789 0111
10000010001

Страницы