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:
“Though Justice against Fate complain,
And plead the antient Rights in vain:
But those do hold or break
As Men are strong or weak.”
—Andrew Marvell (1621–1678)
“Institutions of higher education in the United States are products of Western society in which masculine values like an orientation toward achievement and objectivity are valued over cooperation, connectedness and subjectivity.”
—Yolanda Moses (b. 1946)