완벽하게 주문 가능한 그래프

Perfectly orderable graph

그래프 이론에서, 완벽하게 순서가 가능한 그래프는 주어진 그래프의 모든 유도 서브그래프를 최적으로 색칠하는 탐욕스러운 컬러링 알고리즘으로 정점을 정렬할 수 있는 그래프다.완벽하게 순서가 가능한 그래프는 완벽한 그래프의 특별한 경우를 형성하며, 그것들은 화음 그래프, 비교가능성 그래프, 그리고 거리-계통 그래프를 포함한다.그러나 그래프를 완벽하게 주문할 수 있는지 테스트하는 것은 NP-완전하다.

정의

탐욕스러운 컬러링 알고리즘은, 그래프 G의 정점 순서에 적용되었을 때, 그래프의 정점을 순서대로 고려하고, 각각의 정점들이 그 인접국가들이 사용하는 색상들의 집합에 대한 최소 제외 값인 첫 번째 가용 색상을 할당한다.다른 정점 순서에 따라 이 알고리즘은 다른 수의 색상을 사용할 수 있다.항상 최적의 색상으로 이어지는 순서가 있다. 예를 들어, 정점을 색으로 구분하여 최적의 색상으로 결정하는 순서가 사실이지만 찾기가 어려울 수 있다.완벽하게 순서가 가능한 그래프는 그래프 자체뿐만 아니라 모든 유도 하위 그래프에 대해 탐욕스러운 알고리즘에 최적의 순서가 있는 그래프로 정의된다.

좀 더 형식적으로 G의 정점 순서가 존재하는 경우 G의 모든 유도 서브그래프는 서브그래프의 정점에 의해 유도된 π의 반복성을 이용하여 탐욕스러운 알고리즘에 의해 최적으로 색칠되도록 그래프 G는 완벽하게 순서가 가능하다고 한다.abcd가 유도 경로인 a, b, c, d의 정점 4개가 존재하지 않는 경우, a는 순서에서 b보다 앞에 나타나고 c는 순서에서 d 뒤에 나타나는 경우, 주문 π은 정확히 이 속성을 갖는다.[1]

계산 복잡성

완벽하게 순서가 가능한 그래프는 인식하기에 NP-완전하다.[2]그러나 특정 순서가 그래프의 완벽한 순서가 되는지는 쉽게 테스트할 수 있다.따라서 그래프를 완벽하게 주문할 수 있다고 이미 알려져 있더라도 그래프의 완벽한 순서를 찾는 것은 또한 NP-힘든 일이다.

관련 그래프 클래스

완벽하게 주문 가능한 모든 그래프는 완벽한 그래프다.[1]

코드 그래프는 완벽하게 순서가 가능하며, 코드 그래프의 순서는 그래프에 대한 완벽한 제거 순서를 반대로 적용하면 찾을 수 있다.따라서 탐욕스러운 색상을 완벽한 순서에 적용하면 화음 그래프를 최적으로 색칠할 수 있는 효율적인 알고리즘을 제공한다.비교가능성 그래프는 또한 완벽하게 순서가 가능하며, 완벽한 순서는 그래프의 전이적 방향에 대한 위상학적 순서에 의해 주어진다.[1]공차 그래프의 보완 그래프는 완벽하게 순서가 가능하다.[3]

G에서 5개의 정점의 모든 부분 집합에서 5개의 정점 중 하나 이상이 5개의 정점 중 다른 정점의 닫힌 근방의 부분 집합(또는 같은)인 닫힌 근방을 갖는 그래프 G에 의해 완전히 순서가 가능한 다른 등급이 주어진다.마찬가지로, 이러한 그래프는 집합 포함에 의해 정렬된 폐쇄된 인접 영역의 부분적인 순서가 최대 4개의 너비를 갖는 그래프들이다.5-Vertex 사이클 그래프는 주변 부분 순서가 5이므로 4는 완벽한 주문성을 보장하는 최대 너비다.화음 그래프와 마찬가지로(그리고 더 일반적으로 순서가 완벽하게 가능한 그래프와는 달리) 너비 4의 그래프는 다항식 시간에서 알아볼 수 있다.[4]

코드 그래프의 완벽한 제거 순서와 완벽한 순서 사이의 개념 중간은 반완벽 제거 순서다: 제거 순서에서는 중간 꼭지점이 세 개 중 가장 먼저 제거되는 3Vertex 유도 경로가 없고, 반완벽 제거 순서에서는 4Vertex i가 없다.두 개의 중간 꼭지점 중 하나가 가장 먼저 제거되는 중복된 경로.따라서 이 순서의 역순은 완벽한 순서의 요건을 충족하므로 반완벽한 제거 순서가 있는 그래프는 완벽하게 순서가 가능하다.[5]특히 코드 그래프의 완벽한 제거 순서를 찾는 데 사용되는 사전 편찬 폭 우선 검색 알고리즘을 사용하여 거리 계통 그래프의 반완벽 제거 순서를 찾을 수 있으며, 따라서 이 알고리즘도 완벽하게 정렬할 수 있다.[6]

모든 정점 순서가 완벽한 순서가 되는 그래프는 cographs이다.cograph는 4Vertex 유도 경로가 없는 그래프이기 때문에 완벽한 순서에 따른 경로 순서 지정 요건을 위반할 수 없다.

완벽하게 주문 가능한 그래프의 몇 가지 추가 클래스가 알려져 있다.[7]

메모들

  1. ^ a b c 체바탈(1984년), 마프라(2003년).
  2. ^ Middendorf & Pfeiffer (1990), Maffray (2003).
  3. ^ 골룸빅, 몬마 & 트로터(1984)
  4. ^ 페이안(1983년), 펠스너, 라그하반 & 스핀래드(2003년).
  5. ^ Hoang & Reed (1989); Brandstédt, Le & Spinrad (1999), 페이지 70 및 82.
  6. ^ Brandstédt, Le & Spinrad(1999), Organia 5.2.4, 페이지 71.
  7. ^ 차바탈 외 연구진(1987); 호앙 & 리드(1989); 호앙 외 연구진(1992); 마프레이(2003); 브란슈타트, 르 & 스핀래드(1999), 페이지 81–86.

참조

  • 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
  • Christen, Claude A.; Selkow, Stanley M. (1979), "Some perfect coloring properties of graphs", Journal of Combinatorial Theory, Series B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, MR 0539075
  • Chvátal, Václav (1984), "Perfectly orderable graphs", in Berge, Claude; Chvátal, Václav (eds.), Topics in Perfect Graphs, Annals of Discrete Mathematics, vol. 21, Amsterdam: North-Holland, pp. 63–68. Maffray(2003)가 인용한 바와 같다.
  • Chvátal, Václav; Hoàng, Chính T.; Mahadev, N. V. R.; De Werra, D. (1987), "Four classes of perfectly orderable graphs", Journal of Graph Theory, 11 (4): 481–495, doi:10.1002/jgt.3190110405.
  • Dragan, F. F.; Nicolai, F. (1995), LexBFS-orderings of distance-hereditary graphs, Schriftenreihe des Fachbereichs Mathematik der Univ. Duisburg SM-DU-303. Brandstedt가 인용한 바와 같이, Le & Spinrad(1999년).
  • Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Recognition algorithms for orders of small width and graphs of small Dilworth number", Order, 20 (4): 351–364 (2004), doi:10.1023/B:ORDE.0000034609.99940.fb, MR 2079151, S2CID 1363140.
  • Golumbic, Martin Charles; Monma, Clyde L.; Trotter, William T. Jr. (1984), "Tolerance graphs", Discrete Applied Mathematics, 9 (2): 157–170, doi:10.1016/0166-218X(84)90016-7, MR 0761599
  • Hoàng, Chính T.; Maffray, Frédéric; Olariu, Stephan; Preissmann, Myriam (1992), "A charming class of perfectly orderable graphs", Discrete Mathematics, 102 (1): 67–74, doi:10.1016/0012-365X(92)90348-J.
  • Hoàng, Chính T.; Reed, Bruce A. (1989), "Some classes of perfectly orderable graphs", Journal of Graph Theory, 13 (4): 445–463, doi:10.1002/jgt.3190130407.
  • 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, ISBN 0-387-95434-1.
  • Middendorf, Matthias; Pfeiffer, Frank (1990), "On the complexity of recognizing perfectly orderable graphs", Discrete Mathematics, 80 (3): 327–333, doi:10.1016/0012-365X(90)90251-C.
  • Payan, Charles (1983), "Perfectness and Dilworth number", Discrete Mathematics, 44 (2): 229–230, doi:10.1016/0012-365X(83)90064-X, MR 0689816.