Составители:
Рубрика:
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. Ðàçäåëåíèå îðãðàôà íà ïîä÷àñòè:
à îðãðàô ; á ñóãðàô; â ïîäãðàô; ã ÷àñòè÷íûé ãðàô
Ò
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »