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

UptoLike

ВУЗ: 

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

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

Рубрика: 

27
Ïî òðàíñïîíèðîâàííîé ìàòðèöå ñìåæíîñòè S
ò
ìîæíî âûäåëèòü Ã
1
v
i
ïî i-é ñòðîêå, ãäå íåíóëåâûå ýëåìåíòû s
ò
ij
óêàçûâàþò íà âåðøèíû
v
j
∈ Ã
1
v
i
:
S
5×5
=
L
1
L
2
L
3
L
4
L
5
L
1
01010
L
2
10000
L
3
02100
L
4
00101
L
5
00001
.
1.4.2. Ðàçäåëåíèå îðãðàôà íà ñîñòàâëÿþùèå
Ñóãðàôîì G'=(V, Ã') ãðàôà G=(V, Ã) íàçûâàåòñÿ ãðàô, åñëè (∀v
i
∈V)
(Ã'v
i
⊆ Ãv
i
), ò. å. èç èñõîäíîãî ãðàôà óäàëÿåòñÿ íåêîòîðîå êîëè÷åñòâî
äóã (ñ ñîõðàíåíèåì âåðøèí) (ðèñ.1.16, à,á).
Ïîäãðàôîì G'=(V', Ã') ãðàôà G=(V, Ã) íàçûâàåòñÿ ãðàô, åñëè V'⊂V è
(∀v
i
∈V) (Ã'v
i
=V'∩Ãv
i
), ò. å. èç èñõîäíîãî ãðàôà óäàëÿþòñÿ íåêîòîðûå âåð-
øèíû âìåñòå ñî âñåìè äóãàìè, èíöèäåíòíûìè óäàëåííîé âåðøèíå
(ðèñ.1.16, à,â).
×àñòè÷íûì ïîäãðàôîì G'=(V', Ã') ãðàôà G=(V, Ã) íàçûâàåòñÿ ãðàô,
åñëè V'⊂V, Ã ' ⊂Ã, ò. å. ê èñõîäíîìó ãðàôó ïðèìåíåíû îáå îïèñàííûå
âûøå îïåðàöèè (ðèñ.1.16, à, ã).
1.4.3. Íåêîòîðûå ñïåöèàëüíûå êëàññû îðãðàôîâ
Ñèììåòðè÷åñêèì íàçûâàåòñÿ ãðàô G=(V, U), â êîòîðîì (∀v
i
∈V, ∀v
j
∈V)
(v
i
, v
j
)∈U ⇒ (v
j
, v
i
) ∈U ( ò. å. ëþáûå äâå ñìåæíûå âåðøèíû v
i
è v
j
ñî-
v
v
v
"
v
!
ã
à
)
á
v
v
v
!
v
"
v
"
v
"
v
v
v
v
â)
Ðèñ. 1.16. Ðàçäåëåíèå îðãðàôà íà ïîä÷àñòè:
à îðãðàô ; á ñóãðàô; â ïîäãðàô; ã ÷àñòè÷íûé ãðàô
Ò

Страницы