Bipolar orientation

A bipolar orientation and st-numbering (right) of an undirected graph (left). A single source and sink are established, and all edges are directed from the former to the latter. Vertices are numbered such that the numbers increase along any path.

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.

This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.