비교가능성

Comparability graph

그래프 이론에서 비교가능성 그래프는 서로 비교 가능한 요소 쌍을 부분 순서로 연결하는 비방향 그래프다.비교가능성 그래프는 전이성 방향 그래프, 부분적으로 순서가 가능한 그래프, 격납 그래프, [1]구분 그래프라고도 불린다.[2]비교불가능성 그래프는 서로 비교가 안 되는 요소 쌍을 부분 순서로 연결하는 비방향 그래프다.

정의 및 특성화

포셋(왼쪽)과 비교가능성 그래프(오른쪽)의 Hasse 다이어그램
비교가능성 그래프의 금지 유도 하위 그래프 중 하나.이 그래프의 일반화 주기 a-b–d–f–c–c–b–a는 홀수 길이(9)를 가지지만 삼각형 화음은 없다.

엄격한 부분 순서 집합(S,<)에 대해 (S, <)의 비교가능성 그래프는 (S, )의 그래프(S, ⊥)이며, 정점들은 S의 요소들이며, 가장자리는 u < v>와 같은 요소들의 쌍 {u, v}이다. 즉 부분 순서 집합에 대해서는 지시된 아세클릭 그래프를 취하고, 전이성 폐쇄를 적용하며, 방향을 제거한다.

동등하게 비교가능성 그래프는 결과 지시된 그래프의 인접 관계가 전이되도록 그래프의 가장자리에 대한 방향([3]즉, 그래프의 방향)을 할당하는 전이적 방향을 갖는 그래프로서, 지시된 가장자리(x,y)와 (y,z)가 존재할 때마다 에지(x,z)가 존재해야 한다.

x에 해당하는 집합이 y에 해당하는 집합의 하위 집합일 때마다 부분 순서로 x < y와 같이 집합의 집합으로 유한 부분 순서를 나타낼 수 있다.이러한 방식으로 비교가능성 그래프는 집합 집합 집합의 격납 그래프 즉, 집합의 각 집합에 대한 꼭지점과 다른 집합의 부분 집합일 때마다 두 집합 사이의 가장자리가 있는 그래프와 동일하다는 것을 보여줄 수 있다.[4]또는 x에 해당하는 정수가 y에 해당하는 정수의 구분자일 때마다 x < y와 같이 정수 계열에 의한 부분 순서를 나타낼 수 있다.이러한 구조 때문에 비교가능성 그래프는 분할 그래프라고도 불린다.[2]

비교가능성 그래프는 홀수 길이의 모든 일반화된 주기에 대해 주기에서 거리 2에 있는 두 정점을 연결하는 에지(x,y)를 찾을 수 있는 그래프로 특징지어질 수 있다.그런 가장자리를 삼각형 화음이라고 한다.이러한 맥락에서 일반화된 사이클은 각 방향에서 그래프의 각 가장자리를 최대 한 번에 사용하는 폐쇄된 보행으로 정의된다.[5]비교가능성 그래프는 금지된 유도 하위 그래프의 목록으로도 특징지어질 수 있다.[6]

다른 그래프 패밀리와의 관계

모든 전체 그래프는 비교가능성 그래프, 총 순서의 비교가능성 그래프다.전체 그래프의 모든 반복 방향은 전이적이다.모든 초당적 그래프도 비교가능성 그래프다.양분 그래프의 한쪽에서 다른 쪽까지 양분 그래프의 가장자리를 맞추면 높이 2의 부분 순서에 해당하는 전이적 방향이 된다.시모어(2006)가 관찰한 바와 같이, 완전하지도 않고 초당적이지도 않은 모든 비교가능성 그래프에는 스큐 파티션이 있다.

모든 구간 그래프의 보완은 비교가능성 그래프다.비교가능성 관계를 구간 순서라고 한다.구간 그래프는 정확히 화음이고 비교가능성 그래프를 보완하는 그래프다.[7]

순열 그래프는 일련의 간격에 대한 격납 그래프다.[8]따라서 순열 그래프는 비교가능성 그래프의 또 다른 하위 등급이다.

아주 완벽하지 않은 그래프는 뿌리가 있는 나무의 비교가능성 그래프다.[9]Cographs는 직렬-병렬 부분 순서의 비교가능성 그래프로 특징지어질 수 있다. 따라서 Cographs는 비교가능성 그래프이기도 하다.[10]

분계점 그래프는 또 다른 특별한 종류의 비교가능성 그래프다.

모든 비교가능성 그래프는 완벽하다.비교가능성 그래프의 완성도는 미르스키의 정리이고, 그 보완성의 완성도는 딜워스의 정리다;[11] 이러한 사실들은 완벽한 그래프 정리들과 함께 미르스키의 정리로부터 딜워스의 정리를 증명하는 데 사용될 수 있다.좀 더 구체적으로, 비교가능성 그래프는 완벽하게 순서가 가능한 그래프로서, 완벽한 그래프의 하위 클래스인, 즉 그래프의 전이적 방향의 위상학적 순서를 위한 탐욕스러운 색소 알고리즘은 그것들을 최적으로 색칠할 것이다.[12]

모든 비교가능성 그래프의 보완은 문자열 그래프다.[13]

알고리즘

그래프의 전이 방향은, 존재하는 경우, 선형 시간에서 찾을 수 있다.[14]그러나 알고리즘은 그래프의 가장자리에 방향을 할당하므로 그래프가 비교 가능한 그래프인지 여부를 테스트하는 과제를 완료하려면 결과 방향이 전이적인지, 즉 행렬 곱셈과 복잡성이 동일한 문제인지 여부를 테스트해야 한다.

비교가능성 그래프가 완벽하기 때문에 그래프 컬러링, 독립적 세트 문제 등 더 일반적인 등급의 그래프에 어려운 많은 문제들은 비교가능성 그래프의 다항 시간 내에 해결할 수 있다.

메모들

  1. ^ 골룸빅(1980), 페이지 105; 브란슈타트, 르앤 스핀래드(1999), 페이지 94.
  2. ^ a b 샤르트랑 외 (2001).
  3. ^ Ghuila-Huri(1962); Brandstédt, Le & Spinrad(1999), 정리 1.4.1, 페이지 12를 참조한다.부분 순서에서 오는 방향은 반복적이지만, 이러한 특성화의 조건으로 반복성을 포함할 필요는 없다.
  4. ^ Urrutia (1989); Trotter (1992); Brandstédt, Le & Spinrad (1999), 섹션 6.3, 페이지 94–96.
  5. ^ 구윌라후리(1962년), 길모어&호프만(1964년).Brandstédt, Le & Spinrad(1999), 정리 6.1.1, 페이지 91을 참조하십시오.
  6. ^ 갈라이(1967);트로터(1992); 브란슈타트, 르앤 스핀래드(1999), 91페이지, 112페이지.
  7. ^ 구간 그래프 보완의 전이적 방향성은 Ghuila-Huri(1962)에 의해 입증되었다. 구간 그래프의 특성화는 Gilmore & Hoffman(1964)에 기인한다.또한 골룸빅(1980), 받침 1.3, 페이지 15-16을 참조한다.
  8. ^ 뒤스닉&밀러(1941)Brandstédt, Le & Spinrad(1999), 정리 6.3.1, 페이지 95.
  9. ^ Brandstédt, Le & Spinrad(1999), 정리 6.6.1, 페이지 99.
  10. ^ Brandstédt, Le & Spinrad(1999), 6.4.1, 페이지 96; Jung(1978).
  11. ^ 골룸빅(1980)은 5.34와 5.35 페이지 133을 정리한다.
  12. ^ 매프레이(2003년).
  13. ^ 골룸빅, 로템앤우루티아(1983)와 로바스츠(1983)이다.Fox & Pach(2012)도 참조하십시오.
  14. ^ McConnell & Spinrad(1997); Brandstédt, Le & Spinrad(1999), 페이지 91을 참조한다.

참조

  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Chartrand, Gary; Muntean, Raluca; Saenpholphat, Varaporn; Zhang, Ping (2001), "Which graphs are divisor graphs?", Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001), Congressus Numerantium, 151: 189–200, MR 1887439
  • Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", American Journal of Mathematics, The Johns Hopkins University Press, 63 (3): 600–610, doi:10.2307/2371374, hdl:10338.dmlcz/100377, JSTOR 2371374, MR 0004862.
  • Fox, Jacob; Pach, Jànos (2012), "String graphs and incomparability graphs" (PDF), Advances in Mathematics, 230 (3): 1381–1401, doi:10.1016/j.aim.2012.03.011.
  • Gallai, Tibor (1967), "Transitiv orientierbare Graphen", Acta Math. Acad. Sci. Hung., 18 (1–2): 25–66, doi:10.1007/BF02020961, MR 0221974, S2CID 119485995.
  • Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre", Les Comptes rendus de l'Académie des sciences, 254: 1370–1371, MR 0172275.
  • Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics, 16: 539–548, doi:10.4153/CJM-1964-055-5, MR 0175811.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
  • Golumbic, M.; Rotem, D.; Urrutia, J. (1983), "Comparability graphs and intersection graphs", Discrete Mathematics, 43 (1): 37–46, doi:10.1016/0012-365X(83)90019-5.
  • Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR 0491356.
  • Lovász, L. (1983), "Perfect graphs", Selected Topics in Graph Theory, vol. 2, London: Academic Press, pp. 55–87.
  • Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3.
  • McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
  • Seymour, Paul (2006), "How the proof of the strong perfect graph conjecture was found" (PDF), Gazette des Mathématiciens (109): 69–83, MR 2245898.
  • Trotter, William T. (1992), Combinatorics and Partially Ordered Sets — Dimension Theory, Johns Hopkins University Press.
  • Urrutia, Jorge (1989), "Partial orders and Euclidean geometry", in Rival, I. (ed.), Algorithms and Order, Kluwer Academic Publishers, pp. 327–436, doi:10.1007/978-94-009-2639-4.