In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph.
Strong orientations have been applied to the design of one-way road networks. According to Robbins' theorem, the graphs with strong orientations are exactly the bridgeless graphs. Eulerian orientations and well-balanced orientations provide important special cases of strong orientations; in turn, strong orientations may be generalized to totally cyclic orientations of disconnected graphs. The set of strong orientations of a graph forms a partial cube, with adjacent orientations in this structure differing in the orientation of a single edge. It is possible to find a single orientation in linear time, but it is #P-complete to count the number of strong orientations of a given graph.
Read more about Strong Orientation: Application To Traffic Control, Related Types of Orientation, Flip Graphs, Algorithms and Complexity
Famous quotes containing the words strong and/or orientation:
“Good strong thick stupefying incense-smoke!”
—Robert Browning (1812–1889)
“Every orientation presupposes a disorientation.”
—Hans Magnus Enzensberger (b. 1929)