可比性圖
在圖理論中，可比性圖是一個無方向的圖，它連接了以部分順序相互典型的元素對。可比性圖也稱為可提供的可提供定向圖，部分有序的圖，圍欄圖和除數圖。無與倫比的圖形是一個無方向的圖，它連接了一對在部分順序中彼此不可媲美的元素。
定義和表徵
對於任何嚴格的部分有序集（ s ，<） ， （ s ，<）的可比性圖是該圖（ s ，⊥） ，其頂點是s的元素，邊緣是那些對的{ u ， v }元素使u < v 。也就是說，對於部分有序的集合，請拿到有向的無環圖，應用及時的閉合並刪除方向。
同等地，可比性圖是具有傳遞方向的圖形，將方向分配到圖表邊緣（即圖的方向），以使所得有向圖的鄰接關係是傳遞的： （ x ， y ）和（ y ， z ） ，必須存在邊緣（ x ， z ） 。
一個人可以表示任何有限的部分順序作為集合家族，因此，每當與x相對應的集合是對應於y的集合的子集時， x < y 。通過這種方式，可以證明可比性圖等效於集合族的容器圖。也就是說，每當一個集合是另一個集合的一個子集時，都有一個頂點的圖形，而兩個集合之間的邊緣。另外，一個人可以代表整數家族的部分秩序，以便x < y每當與x相對應的整數是與y相對應的整數的除數。由於這種結構，可比性圖也稱為除數圖。
可比性圖可以表徵為圖形，以便在每個通用周期（見下文）中，可以找到一個邊緣（ x ， y ）連接兩個在循環中距離二的頂點的邊緣（x，y）。這樣的邊緣稱為三角形和弦。在這種情況下，將廣義週期定義為封閉的步行，該步行最多一次在每個方向上使用圖形的每個邊緣。可比性圖也可以通過禁止誘發的子圖表列表來表徵。
與其他圖表家庭的關係
每個完整的圖是一個可比性圖，是總順序的可比性圖。完整圖的所有無環方向均為及傳遞。每個兩分圖也是一個可比性圖。將兩分圖的邊緣從兩部分的一側定向到另一側，從而導致瞬態取向，對應於兩個高度二的部分。正如Seymour（2006）所觀察到的那樣，每個既不完整也不是兩分的可比性圖具有偏斜的分區。
任何間隔圖的補充都是可比性圖。可比性關係稱為間隔順序。間隔圖正是弦的圖形，並且具有可比性圖形。
置換圖是一組間隔上的圍欄圖。因此，置換圖是可比性圖的另一個子類。
瑣碎的完美圖是根樹的可比性圖。 Cographs可以被描述為串聯局部順序的可比性圖。因此，Cographs也是可比性圖。
閾值圖是另一種特殊的可比性圖。
每個可比性圖都是完美的。可比性圖的完美是Mirsky的定理，其補充的完美是Dilworth的定理。這些事實以及完美的圖定理可用於證明米爾斯基定理的dilworth定理，反之亦然。更具體地說，可比性圖是完美的有序圖，是完美圖的子類：用於圖表的及時定向的拓撲排序的貪婪著色算法將最佳地著色。
演算法
圖形的及時取向（如果存在）可以在線性時間中找到。但是，這樣做的算法將把方向分配給任何圖的邊緣，因此要完成測試圖形是否是可比性圖的任務，必須測試結果方向是否是傳遞的，這是一個相當於矩陣的問題，這是一個相當於的問題乘法。