A transitive orientation of a graph
G is an orientation on the edges of
G such that if
a < b and
b < c, then
a < c. Not all graphs have transitive orientations, but those that do are
comparabilityGraphs of posets.
i1 : G = graph {{1,2}, {2,3}, {3,4}, {1,4}};
|
i2 : transitiveOrientation G
o2 = Relation Matrix: | 1 1 1 0 |
| 0 1 0 0 |
| 0 0 1 0 |
| 0 1 1 1 |
o2 : Poset
|
A transitive orientation of a graph G need not be unique. To see other random orientations, set the option Random to true.
i3 : setRandomSeed 0;
|
i4 : G = graph {{1,2},{2,3},{3,4},{1,3},{1,3}};
|
i5 : removeIsomorphicPosets apply(4, i -> transitiveOrientation(G, Random => true))
o5 = {Relation Matrix: | 1 1 1 1 |, Relation Matrix: | 1 1 1 0 |}
| 0 1 0 0 | | 0 1 0 0 |
| 0 1 1 0 | | 0 1 1 0 |
| 0 0 0 1 | | 0 1 0 1 |
o5 : List
|
If the give graph is not a comparability graph, e.g. an odd cycle of length at least 5, then the method returns an error.
The method implemented is Algorithm 5.3 (pages 129-130) from Martin Charles Golumbic, "Algorithmic graph theory and perfect graphs." Second edition. Annals of Discrete Mathematics, 57. Elsevier Science B.V., Amsterdam, 2004. xxvi+314pp.