Составители:
Рубрика:
33
Òðàíçèòèâíûì çàìûêàíèåì íàçûâàåòñÿ ìíîãîçíà÷íîå îòîáðàæåíèå,
îïðåäåëÿåìîå ôîðìóëîé
2
ˆ
{} ...,
ii i i
vv v v
Γ= ∪Γ∪Γ ∪
ò. å. òðàíçèòèâíîå çàìûêàíèå åñòü ìíîæåñòâî âåðøèí, â êîòîðûå ìîæ-
íî ïðèéòè èç âåðøèíû v
i
ïî íåêîòîðîìó ïóòè áåç ïîâòîðåíèÿ äóã.
Àíàëîãè÷íî îïðåäåëÿåòñÿ îáðàòíîå òðàíçèòèâíîå çàìûêàíèå:
12
ˆ
{ } ... ,
ii i i
vv v v
−−−
Γ = ∪Γ ∪Γ ∪
ò. å. îáðàòíîå òðàíçèòèâíîå çàìûêàíèå åñòü ìíîæåñòâî âåðøèí, èç êî-
òîðûõ ïîïàäàþò â âåðøèíó v
i
ïî íåêîòîðîìó ïóòè áåç ïîâòîðåíèÿ äóã.
Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.20,à
ˆ
Ã
v
1
= V,
ˆ
Ã
v
2
= V,
ˆ
Ã
v
3
= V,
ˆ
Ã
v
4
= V,
ˆ
Ã
v
5
= V,
àíàëîãè÷íî
ˆ
Ã
v
1
=V,
ˆ
Ã
v
2
=V,
ˆ
Ã
v
3
=V,
ˆ
Ã
v
4
=V,
ˆ
Ã
v
5
=V,
ò. å. èç êàæäîé âåðøèíû ìîæíî ïðèéòè â ëþáóþ äðóãóþ âåðøèíó.
Äëÿ ãðàôà íà ðèñ. 1.20,á Ãv
6
= {v
6
}, ò. å. èç âåðøèíû v
6
íåëüçÿ ïî-
ïàñòü íè â îäíó èç äðóãèõ âåðøèí, òîãäà êàê Ã
v
6
= V, ò. å. â âåðøèíó v
6
ìîæíî ïðèéòè èç ëþáûõ äðóãèõ âåðøèí ãðàôà.
1.4.8. Ñèëüíî ñâÿçíûé îðãðàô
Ñèëüíî ñâÿçíûì ãðàôîì G = (V, Ã) íàçûâàåòñÿ ãðàô, åñëè
ˆ
(V)
ÃV
ii
vv
∀∈ =
,
ò. å. äëÿ ëþáûõ äâóõ âåðøèí v
i
, v
j
ñóùåñòâóåò ïóòü, èäóùèé èç v
i
â v
j
.
Íàïðèìåð, ãðàô íà ðèñ 1.20,à ÿâëÿåòñÿ ñèëüíî ñâÿçàííûì, à åãî íàäãðàô
íà ðèñ.1.20,á íå ÿâëÿåòñÿ òàêîâûì. Ñèëüíî ñâÿçíûé ãðàô ìîæíî îïðå-
äåëèòü òàêæå ñ ïîìîùüþ óñëîâèÿ
ˆ
(V)
ÃV
ii
vv
−
∀∈ =
.
Áèíàðíîå îòíîøåíèå ñóùåñòâóåò ïóòü èç v
i
â v
j
ÿâëÿåòñÿ îòíîøå-
íèåì ÷àñòè÷íîãî ïîðÿäêà íà ìíîæåñòâå âåðøèí V, òàê êàê îíî òðàíçè-
òèâíî è ðåôëåêñèâíî. Áèíàðíîå îòíîøåíèå ñóùåñòâóåò ïóòü èç v
i
â v
j
è ïóòü èç v
j
â v
i
çàäàåò îòíîøåíèå ýêâèâàëåíòíîñòè (R), òàê êàê îíî,
êðîìå òîãî, ñèììåòðè÷íî. Ýòî áèíàðíîå îòíîøåíèå ïîðîæäàåò êîíòóðû â
ãðàôå. Çíà÷èò, ñèëüíî ñâÿçíûé ãðàô ýòî ãðàô, ñîäåðæàùèé êîíòóðû.
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
