“Comparability graph”的意思、由来-开放百科全书

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, and containment graphs.^[1]

An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

Definitions and characterization

For any strict partially ordered set (S,<), the comparability graph of (S, <) is the graph (S, ⊥) of which the vertices are the elements of S and the edges are those pairs {u, v} of elements such that u < v. That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation.

Equivalently, a comparability graph is a graph that has a transitive orientation,^[2] an assignment of directions to the edges of the graph (i.e. an orientation of the graph) such that the adjacency relation of the resulting directed graph is transitive: whenever there exist directed edges (x,y) and (y,z), there must exist an edge (x,z).

One can represent any partial order as a family of sets, such that x < y in the partial order whenever the set corresponding to x is a subset of the set corresponding to y. In this way, comparability graphs can be shown to be equivalent to containment graphs of set families; that is, a graph with a vertex for each set in the family and an edge between two sets whenever one is a subset of the other.^[3]

Alternatively,^[4] a comparability graph is a graph such that, for every generalized cycle of odd length, one can find an edge (x,y) connecting two vertices that are at distance two in the cycle. Such an edge is called a triangular chord. In this context, a generalized cycle is defined to be a closed walk that uses each edge of the graph at most once in each direction.

Comparability graphs can also be characterized by a list of forbidden induced subgraphs.^[5]

Relation to other graph families

Every complete graph is a comparability graph, the comparability graph of a total order. All acyclic orientations of a complete graph are transitive. Every bipartite graph is also a comparability graph. Orienting the edges of a bipartite graph from one side of the bipartition to the other results in a transitive orientation, corresponding to a partial order of height two. As {{harvtxt|Seymour|2006}} observes, every comparability graph that is neither complete nor bipartite has a skew partition.

The complement of any interval graph is a comparability graph. The comparability relation is called an interval order. Interval graphs are exactly the graphs that are chordal and that have comparability graph complements.^[6]

A permutation graph is a containment graph on a set of intervals.^[7] Therefore, permutation graphs are another subclass of comparability graphs.

Every comparability graph is perfect. The perfection of comparability graphs is Mirsky's theorem, and the perfection of their complements is Dilworth's theorem; these facts, together with the perfect graph theorem can be used to prove Dilworth's theorem from Mirsky's theorem or vice versa.^[10] More specifically, comparability graphs are perfectly orderable graphs, a subclass of perfect graphs: a greedy coloring algorithm for a topological ordering of a transitive orientation of the graph will optimally color them.^[11]

Algorithms

A transitive orientation of a graph, if it exists, can be found in linear time.^[13] However, the algorithm for doing so will assign orientations to the edges of any graph, so to complete the task of testing whether a graph is a comparability graph, one must test whether the resulting orientation is transitive, a problem provably equivalent in complexity to matrix multiplication.

Because comparability graphs are perfect, many problems that are hard on more general classes of graphs, including graph coloring and the independent set problem, can be computed in polynomial time for comparability graphs.

Notes

1. ^{{harvtxt|Golumbic|1980}}, p. 105; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 94.
2. ^{{harvtxt|Ghouila-Houri|1962}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 1.4.1, p. 12. Although the orientations coming from partial orders are acyclic, it is not necessary to include acyclicity as a condition of this characterization.
3. ^{{harvtxt|Urrutia|1989}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, section 6.3, pp. 94–96.
4. ^{{harvtxt|Ghouila-Houri|1962}} and {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.1.1, p. 91.
5. ^{{harvtxt|Gallai|1967}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91 and p. 112.
6. ^Transitive orientability of interval graph complements was proven by {{harvtxt|Ghouila-Houri|1962}}; the characterization of interval graphs is due to {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Golumbic|1980}}, prop. 1.3, pp. 15–16.
7. ^{{harvtxt|Dushnik|Miller|1941}}. {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.3.1, p. 95.
8. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.6.1, p. 99.
9. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, corollary 6.4.1, p. 96; {{harvtxt|Jung|1978}}.
10. ^{{harvtxt|Golumbic|1980}}, theorems 5.34 and 5.35, p. 133.
11. ^{{harvtxt|Maffray|2003}}.
12. ^{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2012}}.
13. ^{{harvtxt|McConnell|Spinrad|1997}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91.

Definitions and characterization

Relation to other graph families

Algorithms

Notes

References