Bipolar orientation

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph. Let G = (V,E) be an undirected graph with n = |V| vertices. An orientation of G is an assignment of a direction to each edge of G, making it into a directed graph. It is an acyclic orientation if the resulting directed graph has no directed cycles. Every acyclically oriented graph has at least one source (a vertex with no incoming edges) and at least one sink (a vertex with no outgoing edges); it is a bipolar orientation if it has exactly one source and exactly one sink. In some situations, G may be given together with two designated vertices s and t; in this case, a bipolar orientation for s and t must have s as its unique source and t as its unique sink. An st-numbering of G (again, with two designated vertices s and t) is an assignment of the integers from 1 to n to the vertices of G, such that each vertex is assigned a distinct number, s is assigned the number 1, t is assigned the number n, and if a vertex v is assigned the number i with 1 < i < n, then at least one neighbor of v is assigned a smaller number than i and at least one neighbor of v is assigned a larger number than i. A graph has a bipolar orientation if and only if it has an st-numbering. For, if it has a bipolar orientation, then an st-numbering may be constructed by finding a topological ordering of the directed acyclic graph given by the orientation, and numbering each vertex by its position in the ordering. In the other direction, every st-numbering gives rise to a topological ordering, in which each edge of G is oriented from its lower-numbered endpoint to its higher-numbered endpoint. In a graph containing edge st, an orientation is bipolar if and only if it is acyclic and the orientation formed by reversing edge st is totally cyclic.