St-граф: различия между версиями
KVN (обсуждение | вклад) (Новая страница: «Ациклический ориентированный граф (орграф) G называется '''st-графом''' (''st-graph''), если в нем и…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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>. | ||
Другое название – ''двухполюсный бесконтурный орграф''. | Другое название – ''[[двухполюсный бесконтурный орграф]]''. | ||
Текущая версия от 17:10, 19 октября 2024
Ациклический ориентированный граф (орграф) 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].
Другое название – двухполюсный бесконтурный орграф.