Flip Graphs
If G is a 3-edge-connected graph, and X and Y are any two different strong orientations of G, then it is possible to transform X into Y by changing the orientation of a single edge at a time, at each step preserving the property that the orientation is strong. Therefore, the flip graph whose vertices correspond to the strong orientations of G, and whose edges correspond to pairs of strong orientations that differ in the direction of a single edge, forms a partial cube.
Read more about this topic: Strong Orientation
Famous quotes containing the word flip:
“By act of Congress, male officers are gentlemen, but by act of God, we are ladies. We don’t have to be little mini-men and try to be masculine and use obscene language to come across. I can take you and flip you on the floor and put your arms behind your back and you’ll never move again, without your ever knowing that I can do it.”
—Sherian Grace Cadoria (b. 1940)