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:
“There was no need for a feminist philosophy. My mother never stopped to think that she couldn’t do something.... You didn’t have to change the rules. Just be a strong and skilled individual, work hard, do your homework, and you can do it.”
—Katherine Berman Mariano (b. 1957)
“Every orientation presupposes a disorientation.”
—Hans Magnus Enzensberger (b. 1929)