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

UptoLike

ВУЗ: 

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

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

Рубрика: 

65
1
ˆ
Ã
v
={v
2
, v
8
} (òðàíçèòèâíîå çàìûêàíèå Z).
1
1
ˆ
Ã
v
−
={v
2
} (îáðàòíîå òðàíçèòèâíîå çàìûêàíèå ZÎ).
Âåðøèíû, âîøåäøèå â îáà çàìûêàíèÿ, îáðàçóþò êîíòóð K
2
:
K
2
(v
2
)=
2
ˆ
Ã
v
∩
1
2
ˆ
Ã
v
−
= {v
2
}, ò. å. êîíòóð âêëþ÷àåò òîëüêî îäíó âåðøè-
íó.
 âåêòîðå V â ïîçèöèè âåðøèíû ñ íîìåðîì 2 çàíîñèòñÿ íîìåð êîí-
òóðà K
2
, ò. å. 2 :
Íîìåðà âåðøèí ãðàôà:
Âåêòîð íîìåðîâ êîíòóðîâ V :
Àíàëîãè÷íî ïîëó÷àþòñÿ ñëåäóþùèå êëàññû ýêâèâàëåíòíîñòåé (ðå-
êîìåíäóåòñÿ ïðîâåðèòü ñàìîñòîÿòåëüíî):
K
3
(v
3
) = {v
3
, v
9
, v
10
}; K
4
(v
4
) = {v
4
, v
5
}; K
5
(v
6
) = {v
6
}; K
6
(v
8
) = {v
8
}.
 ðåçóëüòàòå ïîëíîé îáðàáîòêè ìàòðèöû ñìåæíîñòè S ìîæíî ïîëó-
÷èòü âåêòîð V, ñîäåðæàùèé íîìåðà êîíòóðîâ â ïîçèöèÿõ âåðøèí, âêëþ-
÷åííûõ â äàííûé êîíòóð:
Íîìåðà âåðøèí ãðàôà:
Âåêòîð íîìåðîâ êîíòóðîâ V:
Ðàññìîòðåííûé âûøå ïðîöåññ îáðàáîòêè ìàòðèöû ñìåæíîñòè S è
ïîëó÷åíèÿ âåêòîðà êîíòóðîâ V ìîæíî ïðåäñòàâèòü â âèäå ìàøèííîãî
àëãîðèòìà.
123456789 0111
100000000000 1
201000001001 0
300110000110 1
400011000000 1
500010000000 1
600000101000 1
700000000000 1
800000000000 1
900100000000 1
01 00011000100 1
11 00000000000 1
10111111111
||S||:
1
ˆ
Ã
v
1
1
ˆ
Ã
v
−
123456789 0111
12000010001
123456789 0111
12344516331

Страницы