论文标题
可比性挖掘：可比性图的模拟
Comparability digraphs: An analogue of comparability graphs
论文作者
论文摘要
可比性图是流行的图形类。我们将其作为可比性图形的Digraph类似物介绍了可比性挖掘类别的类别。我们表明，许多概念，例如含义类别和可比性图的打结图，可以自然地扩展到可比性挖掘。我们从它们的打结图中给出了可比性挖掘的特征。半完整的可比性图形是可比性挖掘的原型。分析可比性图的结构的一种仪器技术是图形的三角引理。我们将三角引理概括为半完整的挖掘。使用三角形引理进行半完整的挖掘物，我们证明，如果半完整的挖掘物的含义类别不包含长度2的电路，那么它根本不包含电路。我们还将其用于设备$ \ MATHCAL {O}（n^3）$ $ n $是输入Digraph的顶点的时间识别算法。该算法的正确性意味着半完整的可比性图形的表征，类似于与可比性图有关的表征。
Comparability graphs are a popular class of graphs. We introduce as the digraph analogue of comparability graphs the class of comparability digraphs. We show that many concepts such as implication classes and the knotting graph for a comparability graph can be naturally extended to a comparability digraph. We give a characterization of comparability digraphs in terms of their knotting graphs. Semicomplete comparability digraphs are a prototype of comparability digraphs. One instrumental technique for analyzing the structure of comparability graphs is the Triangle Lemma for graphs. We generalize the Triangle Lemma to semicomplete digraphs. Using the Triangle Lemma for semicomplete digraphs we prove that if an implication class of a semicomplete digraph contains no circuit of length 2 then it contains no circuit at all. We also use it to device an $\mathcal{O}(n^3)$ time recognition algorithm for semicomplete comparability digraphs where $n$ is the number of vertices of the input digraph. The correctness of the algorithm implies a characterization for semicomplete comparability digraphs, akin to that for comparability graphs.
