그래프 분할

Split graph
이 글은 패거리와 독립 집합으로 나눌 수 있는 그래프에 관한 것이다.완전한 초당적 그래프를 구성하는 절단은 분할(그래프 이론)을 참조하십시오.
클라이크와 독립 집합으로 분할된 분할 그래프.

수학의 한 분야인 그래프 이론에서 분할 그래프는 정점을 패거리와 독립 집합으로 분할할 수 있는 그래프다.분할 그래프는 팰데스와 해머(1977a, 1977b)에 의해 처음 연구되었고, 타이슈케비치와 체르냐크(1979)에 의해 독립적으로 도입되었다.[1]

분할 그래프는 클릭과 독립된 집합으로 둘 이상의 파티션을 가질 수 있다. 예를 들어, a-b-c 경로는 분할 그래프로서, 정점은 세 가지 다른 방법으로 분할될 수 있다.

  1. {a,b} 및 독립 집합 {c}
  2. {b,c} 및 독립 집합 {a}
  3. {b} 및 독립 집합 {a,c}

분할 그래프는 금지된 유도 하위 그래프의 관점에서 특징지어질 수 있다. 즉, 유도 하위 그래프가 4개 또는 5개의 정점에 대한 주기 또는 한 쌍의 분리 에지일 경우에만 그래프가 분할된다(4사이클의 보완).[2]

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

정의에서 보면, 분할 그래프는 보완 하에 명확하게 닫힌다.[3]분할 그래프의 또 다른 특성은 보완을 수반한다: 그것들은 화음 그래프인데, 화음 그래프 역시 화음 그래프다.[4]화음 그래프가 나무 하위 트리의 교차 그래프인 것처럼 분할 그래프는 별 그래프의 구별되는 하위 기구의 교차 그래프다.[5]거의 모든 화음 그래프는 분할 그래프다. 즉, n이 무한대로 갈수록 한계에서 분할된 n-Vertex 화음 그래프의 분율이 1에 접근한다.[6]

화음 그래프는 완벽하기 때문에 분할 그래프도 완벽하다.모든 정점을 두 배로 늘려 분할 그래프에서 파생된 그래프 계열인 이중 분할 그래프(따라서 클라이크는 반모형을 유도하고 독립 집합은 일치를 유도한다)는 것은 추드노브스키 외 연구진에서 증명할 수 있는 완벽한 그래프의 5가지 기본 등급 중 하나로 두드러지게 나타난다. (2006)강력완전 그래프 정리.

그래프가 분할 그래프와 구간 그래프 둘 다인 경우, 그 보완물은 분할 그래프와 비교가능성 그래프 둘 다이며, 그 반대도 마찬가지다.분할 비교가능성 그래프, 즉 분할 구간 그래프는 세 가지 금지 유도 하위 그래프로 특징지어질 수 있다.[7]분할된 cographs는 정확히 분계점 그래프다.분할 순열 그래프는 구간 그래프를 보완하는 구간 그래프를 정확히 나타내며,[8] 이는 스큐가 혼합된 순열의 순열 그래프들이다.[9]분할 그래프는 2번 색상을 가지고 있다.

알고리즘 문제

G를 클라이크 C와 독립 집합 I로 분할된 분할 그래프로 하자.그러면 분할 그래프의 모든 최대 클라이크는 C 그 자체 또는 I의 꼭지점 부근이다.따라서, 최대 집단을 쉽게 식별할 수 있으며, 분할 그래프에서 최대 독립 집합을 보완적으로 식별할 수 있다.모든 분할 그래프에서 다음 세 가지 가능성 중 하나가 참이어야 한다.[10]

  1. I에는 C x {x}이(가) 완료되는 꼭지점 x가 있다.이 경우 C ∪ {x}은(는) 최대 클라이크이고 나는 최대 독립 집합이다.
  2. C에 정점 x가 있어 I ∪ {x}이(가) 독립적이다.이 경우 I ∪ {x}은(는) 최대 독립 집합이고 C는 최대 클라이크다.
  3. C는 최대의 패거리고 나는 최대의 독립 세트다.이 경우 G는 패거리와 독립 집합으로 고유한 파티션(C,I)을 가지고 있고, C는 최대 패거리, 나는 최대 독립 집합이다.

그래프 색상을 포함하여 더 일반적인 그래프 제품군의 NP-완전한 일부 다른 최적화 문제는 분할 그래프에서도 마찬가지로 간단하다.해밀턴 사이클을 찾는 것은 강한 화음 그래프인 분할 그래프에서도 NP-완전하다.[11]분할 그래프의 경우 최소 지배 집합 문제가 NP-완전 상태로 남아 있다는 것도 잘 알려져 있다.[12]

도 시퀀스

분할 그래프의 한 가지 주목할 만한 특성은 도표 순서에서만 인식할 수 있다는 것이다.그래프 G의 도 시퀀스를 d1 ≥ d2 ≥ ... ...로 한다.≥ dn, 그리고i d ≥ i - 1과 같은 i의 가장 큰 값이 되게 한다.다음 G는 분할 그래프(경우에만 해당)이다.

만일 이런 경우, 가장 큰 도를 가진 m 정점은 G에서 최대 정점을 형성하고, 나머지 정점은 독립적인 집합을 구성한다.[13]

분할 그래프 카운트

로일(2000년)은 n이 포함된 n-vertex 분할 그래프가 특정 슈페너 계열과 일대일 대응 관계에 있다는 것을 보여주었다.이 사실을 이용하여, 그는 n 정점에 있는 비 이형성 분할 그래프의 수에 대한 공식을 결정했다.n의 작은 값의 경우, n = 1부터 시작하여 이 숫자는 다음과 같다.

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ...(OEIS의 경우 순서 A048194).

이 열거적인 결과는 타이시케비치 & 체르냐크(1990년)에 의해서도 일찍이 증명되었다.

메모들

  1. ^ Földes & Hammer(1977a)는 보다 일반적인 정의를 가지고 있었는데, 여기서 그들이 분할 그래프라고 부르는 그래프에는 또한 양분 그래프(즉, 두 개의 독립된 세트로 분할된 그래프)와 양분 그래프(즉, 두 개의 분류로 분할할 수 있는 그래프)의 보완도 포함되어 있었다.Földes & Hammer(1977b)는 여기에 주어진 정의를 사용하며, 이는 후속 문헌에서 따랐으며, 예를 들어 Brandstédt, Le & Spinrad(1999), Definition 3.2.3, p.41이다.
  2. ^ Földes & Hammer (1977a), Golumbic (1980), 정리 6.3, 페이지 151.
  3. ^ 골룸빅(1980), 정리 6.1, 페이지 150.
  4. ^ Földes & Hammer (1977a), Golumbic (1980), Orgion 6.3, 페이지 151; Brandstet, Le & Spinrad (1999), Orgion 3.2.3, 페이지 41.
  5. ^ McMorris & Shier(1983); Voss(1985); Brandstédt, Le & Spinrad(1999), Orgor 4.4.2, 페이지 52.
  6. ^ 벤더, 리치몬드 & 워먼드(1985)
  7. ^ Földes & Hammer (1977b), Golumbic (1980), Orgor 9.7, 212페이지.
  8. ^ Brandstét, Le & Spinrad(1999), Corollary 7.1.1, 페이지 106, 정리 7.1.2, 페이지 107.
  9. ^ 케즈디, 스니빌리 & 왕(1996년).
  10. ^ 해머&시메오네(1981); 골룸빅(1980), 정리 6.2, 페이지 150.
  11. ^ 뮐러(1996)
  12. ^ 베르토시 (1984)
  13. ^ 해머 & 시메오네(1981);Tyshkevich(1980),티슈케비치, 멜니코프 & 코토프(1981); 골룸빅(1980), 정리 6.7과 코롤라리 6.8, 페이지 154; 브란슈타트, 르& 스핀래드(1999), 정리 13.3.2, 페이지 203.Merris(2003)는 분할 그래프의 정도 시퀀스를 추가로 조사한다.

참조

  • Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi:10.1017/S1446788700023077, MR 0770128.
  • Bertossi, Alan A. (1984), "Dominating sets for split and bipartite graphs", Information Processing Letters, 19: 37–40, doi:10.1016/0020-0190(84)90126-1.
  • 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.
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51, MR 2233847.
  • Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860.
  • Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Split graphs having Dilworth number two", Canadian Journal of Mathematics, 29 (3): 666–672, doi:10.4153/CJM-1977-069-1, MR 0463041.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7, MR 0562306.
  • Hammer, Peter Ladislaw; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica, 1 (3): 275–284, doi:10.1007/BF02579333, MR 0637832.
  • Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), "Partitioning permutations into increasing and decreasing subsequences", Journal of Combinatorial Theory, Series A, 73 (2): 353–359, doi:10.1016/S0097-3165(96)80012-4, MR 1370138.
  • McMorris, F. R.; Shier, D. R. (1983), "Representing chordal graphs on K1,n", Commentationes Mathematicae Universitatis Carolinae, 24: 489–494, MR 0730144.
  • Merris, Russell (2003), "Split graphs", European Journal of Combinatorics, 24 (4): 413–430, doi:10.1016/S0195-6698(03)00030-1, MR 1975945.
  • Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics, 156: 291–298, doi:10.1016/0012-365x(95)00057-4.
  • Royle, Gordon F. (2000), "Counting set covers and split graphs" (PDF), Journal of Integer Sequences, 3 (2): 00.2.6, MR 1778996.
  • Tyshkevich, Regina I. (1980), "[The canonical decomposition of a graph]", Doklady Akademii Nauk SSSR (in Russian), 24: 677–679, MR 0587712
  • Tyshkevich, Regina I.; Chernyak, A. A. (1979), "Canonical partition of a graph defined by the degrees of its vertices", Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (in Russian), 5: 14–26, MR 0554162.
  • Tyshkevich, Regina는 나;Chernyak, A.A.(1990년), Еще один метод перечисления непомеченных комбинаторных объектов, Mat에게. Zametki(러시아어로), 48(6):98–105, MR1102626."표시가 없는 조합 개체를 열거하는 하지만 또 다른 방법"(1990년),, 과학 아카데미의 소련 48(6)의 수학적 팁:1239–1245, doi:10.1007/BF01240267로 번역을 하다.
  • Tyshkevich, Regina I.; Melnikow, O. I.; Kotov, V. M. (1981), "On graphs and degree sequences: the canonical decomposition", Kibernetika (in Russian), 6: 5–8, MR 0689420.
  • Voss, H.-J. (1985), "Note on a paper of McMorris and Shier", Commentationes Mathematicae Universitatis Carolinae, 26: 319–322, MR 0803929.

추가 읽기

  • 분할 그래프에 관한 한 장은 마틴 찰스 골룸빅의 저서 "알고리즘 그래프 이론과 완벽한 그래프"에 등장한다.