St-граф

Материал из WikiGrapp
Версия от 16:56, 4 ноября 2018; KVN (обсуждение | вклад) (Новая страница: «Ациклический ориентированный граф (орграф) G называется '''st-графом''' (''st-graph''), если в нем и…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Ациклический ориентированный граф (орграф) G называется st-графом (st-graph), если в нем имеется только одна начальная вершина, обозначаемая через [math]\displaystyle{ s }[/math], и только одна конечная вершина, обозначаемая через [math]\displaystyle{ t }[/math]. Ясно, что любой ациклический орграф (дэг) [math]\displaystyle{ G }[/math] может быть преобразован в st-граф добавлением фиктивных вершин [math]\displaystyle{ s }[/math] и [math]\displaystyle{ t }[/math], а также дуг [math]\displaystyle{ (s, p) }[/math] и [math]\displaystyle{ (q, t) }[/math] для всех начальных вершин [math]\displaystyle{ p }[/math] и конечных вершин [math]\displaystyle{ q }[/math] графа [math]\displaystyle{ G }[/math].

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