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

UptoLike

ВУЗ: 

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

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

Рубрика: 

14
Ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô G'=(V',
U
'), ãäå V'⊂V,
U
'=
U
∩(V'&V'), ò. å. ïîäãðàô ïîëó÷àåòñÿ èç èñõîäíîãî ãðàôà óäàëåíè-
åì íåêîòîðîãî ÷èñëà âåðøèí âìåñòå ñî âñåìè ðåáðàìè, èíöèäåíòíûìè
óäàëåííîé âåðøèíå. Íàïðèìåð, íà ðèñ. 1.5,á ïîêàçàí ïîäãðàô ãðàôà
(ðèñ. 1.4) ïîñëå óäàëåíèÿ âåðøèíû v
3
è èíöèäåíòíûõ åé ðåáåð è ïåòåëü
(
u
3
,
u
4
,
u
5
).
×àñòüþ (÷àñòè÷íûì ãðàôîì) ãðàôà G íàçûâàåòñÿ ãðàô G'=(V',
U
'),
ãäå V'⊂V,
U
'⊂
U
, ò. å. ÷àñòü ãðàôà ïîëó÷àåòñÿ èç èñõîäíîãî ãðàôà ïðè-
ìåíåíèåì îáåèõ îïèñàííûõ îïåðàöèé. Íàïðèìåð, íà ðèñ. 1.5,â ïîêàçàíà
÷àñòü ãðàôà (ðèñ. 1.4) áåç êðàòíûõ ðåáåð è ïåòåëü (
u
2
,
u
4
,
u
5
), áåç èçî-
ëèðîâàííîé âåðøèíû v
4
.
Èñõîäíûé ãðàô G íàçûâàåòñÿ íàäãðàôîì äëÿ âñåõ åãî ÷àñòåé.
1.3.5. Äèíàìè÷åñêèå ñâîéñòâà íåîðèåíòèðîâàííîãî ãðàôà
Äî ñèõ ïîð ìû ðàññìàòðèâàëè ñòàòè÷åñêèå ñòðóêòóðíûå ñâîéñòâà
ãðàôà è îòðàæàþùèå èõ ïîíÿòèÿ. Îäíàêî ãðàô îáëàäàåò è äèíàìè÷åñ-
êèìè ñâîéñòâàìè, êîòîðûå ïîçâîëÿþò ïåðåìåùàòüñÿ ïî ñìåæíûì ðåá-
ðàì îò îäíîé âåðøèíû ê äðóãîé. Äëÿ èçó÷åíèÿ ýòèõ ñâîéñòâ, êîòîðûå
èãðàþò ôóíäàìåíòàëüíóþ ðîëü â òåîðèè ãðàôîâ, ââåäåì â ðàññìîòðå-
íèå ñîîòâåòñòâóþùèå ïîíÿòèÿ.
Ìàðøðóòîì íàçûâàåòñÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü n ðåáåð ãðàôà
u
1
,
u
2
, ... ,
u
n
(íå îáÿçàòåëüíî ðàçëè÷íûõ), åñëè ñóùåñòâóåò ïîñëåäîâàòåëü-
íîñòü v
0
, v
1
, ... , v
n
èç n+1 (íå îáÿçàòåëüíî ðàçëè÷íûõ) âåðøèí òàêèõ, ÷òî
u
i
~[v
i1
, v
i
], äëÿ i=1, 2, ... , n.
v
v
v
"
v
!
1
u
2
u
3
u
4
u
à
á
â
1
u
1
u
3
u
v
!
v
v
v
"
v
v
Ðèñ. 1. 5. Ïðèìåðû äåëåíèÿ ãðàôà:
à ñóãðàô; á ïîäãðàô; â ÷àñòè÷íûé ãðàô

Страницы