클라이크섬
Clique-sum
수학의 한 분야인 그래프 이론에서, clique-sum은 위상에서의 연결된 sum 연산과 유사하게, 두 그래프를 하나의 clique에서 함께 붙여서 결합하는 방법이다.두 개의 그래프 G와 H가 각각 동일한 크기의 집단을 포함하는 경우, G와 H의 집단은 이 두 집단에서 하나의 공유된 집단을 형성하기 위해 정점 쌍을 식별한 다음, 일부 집단의 가장자리를 삭제함으로써 이들의 분리 결합으로부터 형성된다.k-clike-sum은 두 집단 모두 최대 k-정점을 갖는 clique-sum이다.또한 2-그래프 클릭-섬 연산을 반복적으로 적용하여 세 개 이상의 그래프의 클릭-섬과 k-클릭섬을 형성할 수도 있다.
서로 다른 출처는 clique-sum 연산의 일부로 어떤 가장자리를 제거해야 하는지에 대해 일치하지 않는다.코드 그래프의 분해 또는 질식된 그래프의 분해와 같은 일부 컨텍스트에서는 가장자리를 제거하면 안 된다.그래프의 SPQR-트리 분해와 같은 다른 맥락에서 3-Vertex 연결 성분으로 모든 가장자리를 제거해야 한다.그리고 단순 그래프의 마이너 폐쇄 패밀리에 대한 그래프 구조 정리 같은 다른 맥락에서 제거된 가장자리 집합을 연산의 일부로 지정할 수 있도록 하는 것은 당연하다.
관련개념
클릭섬은 나무 폭과 밀접한 관계가 있다: 두 개의 그래프가 최대 k까지 나무 폭을 갖는다면, 그들의 k-클릭섬도 마찬가지다.모든 나무는 가장자리의 1-크리크섬이다.모든 직렬-병렬 그래프 또는 일반적으로 트리 너비가 최대 두 개인 모든 그래프는 2-클릭-섬 삼각형으로 형성될 수 있다.동일한 유형의 결과가 더 큰 k 값으로 확장된다. 최대 k에 트리 너비가 있는 모든 그래프는 최대 k + 1 정점을 가진 그래프의 집단 합으로 형성될 수 있다. 이것은 반드시 k-클릭 합이다.[1]
또한 clique-sum과 그래프 연결성 사이에는 밀접한 연관성이 있다. 즉, 그래프가 (k + 1)-vertex-connected가 아닌 경우(그래서 k 정점이 존재하여 그래프를 분리하는) 작은 그래프의 k-clike-sum으로 나타낼 수 있다.예를 들어, 2차원 그래프의 SPQR 트리는 3차원 구성요소의 2차원 합으로 그래프를 나타낸 것이다.
그래프 구조 이론에서의 적용
clique-sum은 그래프 구조 이론에서 중요한데, 여기서 그것들은 특정 그룹의 그래프를 단순한 그래프의 clique-sum에 의해 형성된 그래프로 특징짓는 데 사용된다.바그너(1937년)의 평면 그래프의eight-vertex 바그너 그래프는 미성년자로five-vertex 완전 그래프를 갖고 있지 않은 그래프는 3-clique-sums, 이 구조체 정리는 4색 정리 이 사건 k에=동일한지 보여 주기 위해 사용될 수 있다는 것을 입증 이 type[2]의 첫번째 결과는 정리, 5Hadwiger conjec.ture. 화음 그래프는 정확히 가장자리를 삭제하지 않고 패거리의 합계에 의해 형성될 수 있는 그래프이며, 질식된 그래프는 가장자리를 삭제하지 않고 패거리의 합과 최대 평면 그래프에 의해 형성될 수 있는 그래프다.[3]길이 4 이상의 모든 유도 사이클이 최소 분리형 그래프를 형성하는 그래프(그 제거는 그래프를 둘 이상의 분리된 구성요소로 분할하고 주기의 하위 집합은 동일한 특성을 가지지 않음)는 에지 삭제 없이 정확히 패거리와 최대 평면 그래프의 합이다.[4]Johnson & McKee(1996)는 확실한 확실한 보완을 가진 부분 행렬을 특징짓기 위해 코드 그래프와 직렬-병렬 그래프의 클릭섬을 사용한다.
그래프 사소한 연산에 따라 닫힌 그래프 계열에 대해 클릭섬 분해를 도출할 수 있다: 모든 마이너 클로즈드 계열의 그래프는 경계 속 표면에서 "가까이 내장되어 있는" 그래프의 클릭섬에서 형성될 수 있다. 즉, 임베딩이 소수의 꼭지점(연결될 수 있는 수직)을 생략할 수 있다는 것을 의미한다.다른 정점의 임의 부분 집합) 및 포트(표면 내장면을 대체하는 낮은 경로 너비로 표시)[5]이러한 특성화는 마이너 클로즈드 그래프 패밀리의 NP-완전 최적화 문제를 위한 근사 알고리즘과 하위 시간 알고리즘의 구성에 중요한 도구로 사용되어 왔다.[6]
일반화
clique-sum 이론은 또한 그래프에서 모태까지 일반화될 수 있다.[1]특히 세이모어의 분해 정리는 일반 매트로이드(전혀 단조로운 매트로이드로 표현할 수 있는 매트로이드)를 그래픽 매트로이드(그래프로 스패닝 트리를 나타내는 매트로이드), 코그래픽 매트로이드, 특정 10요소 매트로이드의 3섬으로 특징짓는다.[1][7]
메모들
- ^ a b c 로바스 (2006년).
- ^ Kiž & Thomas(1990년)가 인정한 바와 같이, 그래프 계열의 여러 추가적인 clique-sum 기반 특성화 목록을 작성한다.
- ^ 시모어 & 위버(1984년).
- ^ 디에스텔 (1987년).
- ^ 로버트슨 & 시모어(2003)
- ^ 데메인 외 (2004);데메인 외 (2005);데메인, 하지아헤이 & 카와라바야시(2005년).
- ^ 시모어(1980).
참조
- Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammedTaghi; Thilikos, Dimitrios (2005), "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs", Journal of the ACM, 52 (6): 866–893, arXiv:1104.2230, doi:10.1145/1101821.1101823, MR 2179550.
- Demaine, Erik D.; Hajiaghayi, MohammedTaghi; Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios (2004), "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors", Journal of Computer and System Sciences, 69 (2): 166–195, doi:10.1016/j.jcss.2003.12.001, MR 2077379.
- Demaine, Erik D.; Hajiaghayi, MohammedTaghi; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: decomposition, approximation, and coloring" (PDF), Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (PDF), pp. 637–646, doi:10.1109/SFCS.2005.14.
- Diestel, Reinhard (1987), "A separation property of planar triangulations", Journal of Graph Theory, 11 (1): 43–52, doi:10.1002/jgt.3190110108, MR 0876203.
- Kříž, Igor; Thomas, Robin (1990), "Clique-sums, tree-decompositions and compactness", Discrete Mathematics, 81 (2): 177–185, doi:10.1016/0012-365X(90)90150-G, MR 1054976.
- Johnson, Charles R.; McKee, Terry A. (1996), "Structural conditions for cycle completable graphs", Discrete Mathematics, 159 (1–3): 155–160, doi:10.1016/0012-365X(95)00107-8, MR 1415290.
- Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8, MR 2188176.
- Robertson, N.; Seymour, P. D. (2003), "Graph minors XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X, MR 1999736.
- Seymour, P. D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, MR 0579077.
- Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
- Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen, 114: 570–590, doi:10.1007/BF01594196.
