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

UptoLike

ВУЗ: 

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

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

Рубрика: 

16
Äëÿ âåðøèíû v
i
îáîçíà÷èì ÷åðåç Ñ(v
i
) ñîâîêóïíîñòü âåðøèí ãðà-
ôà, êîòîðûå ìîæíî ñîåäèíèòü öåïüþ ñ v
i
. Êîìïîíåíòîé ñâÿçíîñòè
G(v
i
) íàçûâàåòñÿ ïîäãðàô ãðàôà G, ïîðîæäåííûé Ñ(v
i
). Íàïðèìåð,
ãðàô G=(V,
U
) íà ðèñ. 1.7 èìååò äâå êîìïîíåíòû ñâÿçíîñòè ñ ïîäìíî-
æåñòâàìè âåðøèí V
1
={v
1
, v
2
, v
3
, v
4
}, V
2
={v
5
, v
6
, v
7
}.
Ïóñòü G
1
, G
2
,... êîìïîíåíòû ñâÿçíîñòè, ïîðîæäåííûå ïîäìíîæå-
ñòâàìè âåðøèí V
1
, V
2
,... . Òîãäà
1. (∀i ∀j) V
i
≠V
j
, ò. å. íåò îäèíàêîâûõ ïîäìíîæåñòâ âåðøèí.
2. (∀i ∀j) V
i
≠V
j
⇒ V
i
∩V
j
=∅, ò. å. ïîäìíîæåñòâà âåðøèí íå ñîäåðæàò
îáùèõ âåðøèí.
3.
VV
i
i
∪=
, ò. å. îáúåäèíåíèå ïîäìíîæåñòâ âåðøèí ñîñòàâëÿåò ìíî-
æåñòâî âåðøèí ãðàôà, à òàêæå ∪ Ñ(v
i
)=V.
v
i
∈V .
Íà îñíîâå ïîíÿòèÿ êîìïîíåíò ñâÿçíîñòè ìîæíî äàòü äðóãîå îïðåäå-
ëåíèå ñâÿçíîñòè ãðàôà:
Ãðàô G=(V,
U
) ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà ìíîæåñòâî åãî
âåðøèí íåëüçÿ ðàçáèòü íà äâà íåïóñòûõ ïîäìíîæåñòâà V
1
è V
2
òàê,
÷òî îáå ãðàíè÷íûå òî÷êè êàæäîãî ðåáðà íàõîäÿòñÿ â îäíîì è òîì æå
ïîäìíîæåñòâå.
Ïóñòü G=(V,
U
) ïðîèçâîëüíûé ãðàô. Çàäàäèì áèíàðíîå îòíî-
øåíèå ρ ìåæäó ïàðàìè âåðøèí ñëåäóþùèì îáðàçîì: v
1
ρ v
2
òîãäà è
òîëüêî òîãäà, êîãäà v
1
= v
2
èëè êîãäà ñóùåñòâóåò öåïü, ñîåäèíÿþùàÿ
v
1
ñ v
2
.
Îòíîøåíèå ρ ðåôëåêñèâíî (v ρ v äëÿ ëþáîãî v), ñèììåòðè÷íî
(èç v
1
ρ v
2
ñëåäóåò v
2
ρ v
1
) è òðàíçèòèâíî (èç v
1
ρ v
2
è v
2
ρ v
3
ñëåäóåò v
1
ρ v
3
). Òàêèì îáðàçîì, ρ åñòü îòíîøåíèå ýêâèâàëåíòíîñòè. Îíî ðàç-
áèâàåò ìíîæåñòâî V åäèíñòâåííûì îáðàçîì íà êëàññû ýêâèâàëåíò-
íîñòè âçàèìíî ñâÿçíûõ âåðøèí. Äëÿ ãðàôà íà ðèñ. 1.7 òàêèìè êëàñ-
v
v
v
!
v
"
1
u
2
u
3
u
4
u
5
u
v
#
6
u
8
u
7
u
v
$
v
%
Ðèñ. 1.7. Ïðèìåð íåñâÿçíîãî ãðàôà

Страницы