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:
“Fathering makes a man, whatever his standing in the eyes of the world, feel strong and good and important, just as he makes his child feel loved and valued.”
—Frank Pittman (20th century)
“Every orientation presupposes a disorientation.”
—Hans Magnus Enzensberger (b. 1929)