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

UptoLike

ВУЗ: 

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

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

Рубрика: 

32
1.4.7. Òðàíçèòèâíûå çàìûêàíèÿ
Äëÿ òîãî ÷òîáû äàòü ôîðìàëèçîâàííîå îïðåäåëåíèå ñèëüíî ñâÿçíîãî
ãðàôà, èãðàþùåãî âàæíóþ ðîëü ïðè ðåøåíèè ìíîãèõ çàäà÷ ìåòîäàìè
òåîðèè ãðàôîâ, ââåäåì ïîíÿòèå òðàíçèòèâíîãî è îáðàòíîãî òðàíçèòèâ-
íîãî çàìûêàíèÿ.
Âûøå ìû îáîçíà÷èëè ÷åðåç Ãv ïîäìíîæåñòâî ñìåæíûõ âåðøèí-êîí-
öîâ äóã, èìåþùèõ íà÷àëîì âåðøèíó v, à ÷åðåç Ã
v ïîäìíîæåñòâî ñìåæ-
íûõ âåðøèííà÷àëà äóã, èìåþùèõ êîíöîì âåðøèíó v.
Îáîçíà÷èì ÷åðåç Ã
n
v ïîäìíîæåñòâî òåõ âåðøèí, â êîòîðûå ìîæíî
ïðèéòè èç âåðøèíû v, èñïîëüçóÿ ïóòè äëèíû n (èëè, áûòü ìîæåò, ìåíü-
øåé), à ÷åðåç Ã
n
v ïîäìíîæåñòâî òåõ âåðøèí, èç êîòîðûõ ìîæíî ïðèéòè
â âåðøèíó v, èñïîëüçóÿ ïóòè äëèíû n (èëè, âîçìîæíî, ìåíüøåé).
Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.20,à èìååì:
Ãv
1
={v
2
, v
3
}, Ãv
2
={v
1
, v
4
, v
5
}, Ãv
3
={v
4
}, Ãv
4
={v
1
}, Ãv
5
={v
4
};
Ã
2
v
1
=Ã{Ãv
1
}=Ã{v
2
, v
3
}=Ãv
2
∪Ãv
3
={v
1
, v
4
, v
5
}∪{v
4
}={v
1
, v
4
, v
5
};
Ã
3
v
1
=Ã{Ã
2
v
1
}=Ã{v
1
, v
4
, v
5
}=Ãv
1
∪Ãv
4
∪Ãv
5
=
={v
2
, v
3
}∪{v
1
}∪{v
4
}={v
1
, v
2
, v
3
, v
4
};
Ã
1
v
1
={v
2
, v
4
}; Ã
1
v
2=
{v
1
}; Ã
1
v
3=
{v
1
}; Ã
1
v
4=
{v
2
, v
3
, v
5
}; Ã
1
v
5=
{v
2
};
Ã
2
v
4
=Ã
{Ã
v
4
}=Ã
{v
2
, v
3
, v
5
}=Ã
v
2
∪ Ã
v
3
∪ Ã
v
5=
={v
1
}∪{v
1
}∪{v
2
}={v
1
, v
2
};
Ã
3
v
4
=Ã
{Ã
2
v
4
}=Ã
{v
1
, v
2
}=Ã
v
1
∪ Ã
v
2
={v
2
,v
4
}∪{v
1
}={v
1
, v
2
, v
4
}.
Ðèñ. 1.20. Îðãðàôû
v
v
"
v
!
à
á
v
!
v
v
"
v
v
#
v
#
v
v
$

Страницы