St-граф: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «Ациклический ориентированный граф (орграф) G называется '''st-графом''' (''st-graph''), если в нем и…»)
 
Нет описания правки
 
Строка 1: Строка 1:
Ациклический ориентированный граф (орграф) G называется '''st-графом''' (''st-graph''), если в нем имеется только одна начальная вершина, обозначаемая через <math>s</math>, и только одна конечная вершина, обозначаемая через <math>t</math>. Ясно, что любой ациклический орграф (дэг) <math>G</math> может быть преобразован в '''st-граф''' добавлением фиктивных вершин <math>s</math>  и <math>t</math>, а также дуг <math>(s, p)</math> и <math>(q, t)</math> для всех начальных вершин <math>p</math>  и конечных вершин <math>q</math>  графа <math>G</math>.
[[Бесконтурный орграф|Ациклический ориентированный граф (орграф)]] G называется '''st-графом''' (''st-graph''), если в нем имеется только одна [[начальная вершина]], обозначаемая через <math>s</math>, и только одна [[конечная вершина]], обозначаемая через <math>t</math>. Ясно, что любой ациклический орграф (дэг) <math>G</math> может быть преобразован в '''st-граф''' добавлением фиктивных вершин <math>s</math>  и <math>t</math>, а также дуг <math>(s, p)</math> и <math>(q, t)</math> для всех начальных вершин <math>p</math>  и конечных вершин <math>q</math>  графа <math>G</math>.


Другое название –  ''двухполюсный бесконтурный орграф''.
Другое название –  ''[[двухполюсный бесконтурный орграф]]''.

Навигация