Составители:
Рубрика:
17
ñàìè ýêâèâàëåíòíîñòè ÿâëÿþòñÿ V
1
={v
1
, v
2
, v
3
, v
4
} è V
2
={v
5
, v
6
, v
7
}.
Êàæäûé êëàññ ýêâèâàëåíòíîñòè âåðøèí âìåñòå ñ ðåáðàìè èç
U
, èí-
öèäåíòíûìè ýòèì âåðøèíàì, îáðàçóåò ñâÿçíûé ïîäãðàô, íàçûâàå-
ìûé ïðîñòî êîìïîíåíòîé ñâÿçíîñòè ãðàôà G. Êîìïîíåíòà G
i
ãðàôà G
ÿâëÿåòñÿ ìàêñèìàëüíî ñâÿçíûì ïîäãðàôîì â òîì ñìûñëå, ÷òî ãðàô G
i
íå èìååò ñâÿçíîãî ñîáñòâåííîãî íàäãðàôà. Îòñþäà ñëåäóåò åùå îäíî
îïðåäåëåíèå êîìïîíåíòû ñâÿçíîñòè:
Ïîäãðàô G' ãðàôà G íàçûâàåòñÿ êîìïîíåíòîé ñâÿçíîñòè ãðàôà G, åñëè
1) G' ñâÿçåí, 2) G' îáëàäàåò ñâîéñòâîì ìàêñèìàëüíîñòè, ò. å. åñëè G''
íåêîòîðûé äðóãîé ñâÿçíûé ïîäãðàô G è G'⊂ G'', òî ãðàôû G' è G''
ñîâïàäàþò.
1.3.7. Äåðåâüÿ è ëåñà â ãðàôå
Äåðåâîì íàçûâàåòñÿ ñâÿçíûé ãðàô áåç öèêëîâ. Ãðàô ÿâëÿåòñÿ äåðå-
âîì òîãäà è òîëüêî òîãäà, êîãäà êàæäàÿ ïàðà ðàçëè÷íûõ âåðøèí ñîåäè-
íÿåòñÿ îäíîé è òîëüêî îäíîé öåïüþ. Ñâÿçíîñòü äåðåâà îçíà÷àåò ñóùå-
ñòâîâàíèå, ïî êðàéíåé ìåðå, îäíîé òàêîé öåïè, à èç îòñóòñòâèÿ öèêëîâ
ñëåäóåò ñóùåñòâîâàíèå åäèíñòâåííîé òàêîé öåïè.
Ëåñîì èç K äåðåâüåâ íàçûâàåòñÿ ãðàô áåç öèêëîâ, ñîñòîÿùèé èç K
êîìïîíåíò.
Èç ãðàôà íà ðèñ.1.7 ïóòåì óäàëåíèÿ ðåáåð, çàìûêàþùèõ öèêëû,
ìîæíî ïîëó÷èòü ðàçëè÷íûå âàðèàíòû äåðåâüåâ, íàïðèìåð òàêèå, êàê
íà ðèñ.1.8.
Óäàëåíèå ëþáîãî ðåáðà èç äåðåâà äåëàåò åãî íåñâÿçíûì, òàê êàê óäà-
ëÿåìîå ðåáðî ñîñòàâëÿåò åäèíñòâåííóþ öåïü, ñîåäèíÿþùóþ åãî ãðàíè÷-
íûå òî÷êè. Ñëåäîâàòåëüíî, äåðåâî ìîæíî òàêæå îïðåäåëèòü êàê ìèíè-
ìàëüíî ñâÿçíûé ãðàô, ãäå ìèíèìàëüíîñòü ïîíèìàåòñÿ â òîì ñìûñëå, ÷òî
v
v
v
!
v
"
1
u
2
u
3
u
4
u
v
#
6
u
8
u
7
u
v
$
v
%
1
u
3
u
6
u
v
v
v
"
v
!
v
$
v
#
v
%
a á
Ðèñ. 1.8. Ïðèìåðû íåñâÿçíîãî ãðàôà â âèäå ëåñà èç äâóõ äåðåâüåâ
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
