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

UptoLike

ВУЗ: 

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

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

Рубрика: 

30
1) ïóòü (u
1
, u
3
, u
6
) ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí (v
3
,v
2
, v
1
, v
4
);
2) ïóòü (u
6
, u
7
, u
1
) ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí (v
1
, v
4
, v
3
,v
2
).
Àíàëîãè÷íî ãàìèëüòîíîâ êîíòóð ýòî êîíòóð, ïðîõîäÿùèé ÷åðåç
âñå âåðøèíû â òî÷íîñòè ïî îäíîìó ðàçó (èñêëþ÷àÿ ïðîèçâîëüíî âûá-
ðàííîå íà÷àëî). Íàïðèìåð, íà ðèñ.1.18 åñòü îäèí ãàìèëüòîíîâ êîíòóð
(u
1
, u
3
, u
6
, u
7
) ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí (v
3
, v
2
, v
1
, v
4
, v
3
); ïðè÷åì
ëþáàÿ âåðøèíà ìîæåò áûòü âûáðàíà â êà÷åñòâå íà÷àëüíîé öèêëè÷åñ-
êèì ñäâèãîì.
1.4.5. Îðèåíòèðîâàííûå äåðåâüÿ
Îðèåíòèðîâàííûì äåðåâîì (åãî íàçûâàþò òàêæå ïðàäåðåâîì), ðàñ-
òóùèì èç êîðíÿ v
0
, íàçûâàåòñÿ ãðàô G=(V,U),åñëè:
1) (∃!v
0
∈V) Ã
1
{v
0
}=∅ (ãäå ñèìâîëüíîå îáîçíà÷åíèå ∃! îçíà÷àåò
ñóùåñòâóåò îäíà è òîëüêî îäíà), ò. å. ñóùåñòâóåò åäèíñòâåííàÿ âåð-
øèíà v
0
(íàçûâàåìàÿ êîðíåì äåðåâà), â êîòîðóþ íå çàõîäèò íè îäíà
äóãà (íåò ïðåäøåñòâóþùèõ âåðøèí);
2) (∀v
i
∈V)|Ã
1
{v
i
}| =1 (v
i
≠v
0
), ò. å. â êàæäóþ äðóãóþ âåðøèíó çàõî-
äèò òîëüêî îäíà äóãà (òîëüêî îäíà âåðøèíà ïðåäøåñòâóåò âåðøèíå v
i
);
3) ãðàô íå ñîäåðæèò êîíòóðîâ.
Âåðøèíà v
i
íàçûâàåòñÿ âèñÿ÷åé, åñëè Ãv
i
=∅, ò. å. èç v
i
íå èñõîäèò
äóãà (íåò ñëåäóþùåé âåðøèíû), åå òàêæå íàçûâàþò ëèñòîì.
Íà ðèñ.1.19,à ïîêàçàíî ïðàäåðåâî ñ êîðíåì v
0
è âèñÿ÷èìè âåðøèíà-
ìè v
3
, v
4
, v
5
, v
6
.
Òàêèì îáðàçîì, ìîæíî ñêàçàòü, ÷òî ïðàäåðåâîì ÿâëÿåòñÿ ãðàô áåç
êîíòóðîâ è ïåòåëü, â êîòîðîì èç êîðíÿ äåðåâà â ëþáóþ äðóãóþ âåðøèíó
ìîæíî ïðèéòè òîëüêî ïî îäíîìó ýëåìåíòàðíîìó ïóòè.
v
v
"
v
!
à á â
v
!
v
v
"
v
v
#
v
$
v
#
v
v
v
v
%
v
&
v
'
v

v
$
A
B
E
C
D
F
GH I
L
J
K
Ðèñ. 1.19. Îðèåíòèðîâàííûå äåðåâüÿ :
à ïðàäåðåâî; á äâîè÷íîå äåðåâî; â âåòâÿùèéñÿ ãðàô

Страницы