분할(그래프 이론)

Split (graph theory)
두 개의 강한 분할(상단)과 분할 분해(하단)가 있는 그래프.세 개의 지수 그래프는 별(왼쪽), 프라임 그래프(가운데), 전체 그래프(오른쪽)이다.
이 기사는 완전한 초당적 그래프를 구성하는 삭감에 관한 것이다.클라이크와 독립 집합으로 분할할 수 있는 그래프는 분할 그래프를 참조하십시오.

그래프 이론에서, 방향이 없는 그래프의 분할은 컷 세트가 완전한 양분 그래프를 형성하는 컷이다.그래프는 분할이 없으면 프라임이다.그래프의 분할은 분할분해 또는 결합분해라고 하는 나무와 같은 구조로 수집할 수 있으며, 이를 선형적으로 구성할 수 있다.이 분해는 그래프 알고리즘의 다른 문제뿐만 아니라 원 그래프와 거리-계통 그래프의 빠른 인식에 사용되어 왔다.

분할 및 분할 분해는 커닝햄(1982)에 의해 처음 도입되었는데, 커닝햄은 지시된 그래프에 대해 동일한 개념의 변형을 연구하기도 했다.[1]

정의들

방향되지 않은 그래프의 자르기란 정점을 두 개의 비어 있지 않은 부분 집합으로 분할한 것으로, 자르기 측면이다.양쪽에 끝점이 하나씩 있는 가장자리의 부분 집합을 컷 집합이라고 한다.컷 세트가 완전한 양분 그래프를 형성할 때 컷을 분할이라고 한다.따라서 분할은 그래프의 정점을 두 개의 부분 집합 X와 Y로 분할하여 Y의 모든 이웃이 Y의 모든 이웃에 인접하도록 설명할 수 있다.[2]

자르거나 갈라지는 것은 양면 중 하나에 하나의 꼭지점만 있을 때 사소한 것이다; 모든 사소한 상처는 갈라진 것이다.그래프는 (분열과 관련하여) 비종교적 분할이 없는 경우 원시라고 한다.[2]

한 분할의 각 면에 다른 분할의 각 면과 비어 있지 않은 교차점이 있으면 두 분할이 교차한다고 한다.스플릿은 다른 스플릿에 의해 교차되지 않을 때 강하다고 불린다.특별한 경우로서 사소한 분열도 모두 강하다.그래프의 강한 분할은 그래프의 분할 분해 또는 결합 분해라는 구조를 발생시킨다.이 분해는 나뭇잎이 주어진 그래프와 일대일로 대응하고, 가장자리가 그래프의 강한 갈라짐과 일대일로 일치하는 나무로 나타낼 수 있는데, 나무에서 어떤 가장자리를 제거하여 형성된 잎의 분할은 연관된 강한 분할에 의해 주어지는 정점 분할과 동일하다.[2]

그래프 G의 분할 분해 트리의 각 내부 노드 i는 노드 i에 대한 지수 그래프라고 불리는 그래프i G와 연관되어 있다.지수 그래프는 트리에서 i를 삭제하고, 결과 하위 트리의 잎에 해당하는 G의 정점 부분 집합을 형성하며, 이러한 정점 집합을 하나의 꼭지점으로 접음으로써 형성될 수 있다.모든 지수 그래프는 세 가지 형태 중 하나를 가지고 있다: 그것은 프라임 그래프, 완전한 그래프 또는 별일 수 있다.[2]

그래프는 기하급수적으로 많은 다른 분할을 가질 수 있지만, 모두 분할 분해 트리에서 나무의 가장자리 또는 전체 또는 항성 지수 그래프의 임의 분할(강하지 않은 분할의 경우)로 표시된다.[2]

예

전체 그래프 또는 전체 양분 그래프에서 모든 절단은 분할이다.

길이 4의 사이클 그래프에서 주기의 2색에 의해 주어지는 정점 분할은 비종교 분할이지만, 더 긴 길이의 사이클의 경우 비종교 분할은 없다.

2개의 가장자리가 연결되지 않은 그래프의 다리는 분할에 해당하며, 분할의 각 면은 교량의 한 면에 정점에 의해 형성된다.스플릿의 컷 세트는 하나의 브릿지 가장자리일 뿐인데, 이것은 완전한 초당파 서브그래프의 특별한 경우다.마찬가지로, v가 2-Vertex 연결되지 않은 그래프의 연결점이라면, 그래프는 v와 삭제에 의해 형성된 모든 구성요소가 한쪽에 있고 나머지 구성요소가 다른 쪽에 있는 다중 분할을 가진다.이러한 예에서 분할의 컷 세트는 별을 형성한다.

알고리즘

커닝햄(1982)은 이미 다항식 시간에 분할분해를 찾을 수 있다는 것을 보여주었다.[1]알고리즘의 후속 개선 후,[3][4] 선형 시간 알고리즘은 Dahlhaus(2000년)[5]와 Charbit, de Montgolfier & Raffinot(2012년)에 의해 발견되었다.[2]

적용들

다음과 같은 몇 가지 중요한 그래프 클래스의 인식에 분할 분해가 적용되었다.

  • 거리-연속 그래프는 분할 분해에 주요 인수가 포함되지 않은 그래프다.이러한 특성화에 기초해 분할 분해를 이용하여 거리-계통 그래프를 선형 시간 내에 인식할 수 있다.[6][7]
  • 패리티 그래프는 각 분할 지수가 완전하거나 양분되는 그래프로 선형 시간 내에 인식할 수 있다.[8]
  • 원 그래프(circle graph)는 원의 화음 계열을 교차 그래프로 나타낸 것이다.주어진 그래프는 분할 분해의 각 인용 부위가 원 그래프인 경우에만 원 그래프이므로, 그래프가 원 그래프인지 여부를 테스트하는 것은 그래프의 주요 지수 그래프에서 동일한 문제로 축소될 수 있다.또한 원 그래프가 원시일 때 이를 나타내는 화음 집합의 결합 구조가 고유하게 결정되어 이 구조를 인식하는 작업이 단순화된다.이러한 생각을 바탕으로 다항식 시간에 원 그래프를 인식하는 것이 가능하다.[3]

분할 분해는 임의 그래프에서 NP-hard인 일부 문제의 해결책을 단순화하는 데에도 사용되었다.[9]

  • 커닝햄(1982)이 이미 관측했듯이, 어떤 그래프의 최대 독립 집합은 분할 분해 트리의 상향 이동에 있는 동적 프로그래밍 알고리즘에 의해 발견될 수 있다.각 노드에서 우리는 지수 그래프에 있는 최대 중량 독립 세트를 선택하고, 하위 노드에서 이미 계산된 독립 집합의 크기에 따라 가중치를 부여한다.[1]
  • 커닝햄(1982)에 의해 주어진 또 다른 알고리즘에 결함이 있지만, 유사한 상향식 트래버설(bottom-up traversal)을 사용하여 가중치 있는 최대 클릭의 연산을 지수 그래프에 결합함으로써 그래프의 최대 클릭을 계산할 수 있다.[9]
  • Rao(2008)는 또한 연결된 지배 세트, 완전한 지배 세트, 그래프 색칠을 위한 알고리즘을 제시한다.[9]

이러한 방법들은 각 지수 그래프의 하위 문제를 효율적으로 계산할 수 있는 간단한 구조를 가진 그래프의 다항 시간 알고리즘으로 이어질 수 있다.예를 들어, 각 지수 그래프의 크기가 일정한 그래프에 해당된다.[9]

참조

  1. ^ a b c Cunningham, William H. (1982), "Decomposition of directed graphs", SIAM Journal on Algebraic and Discrete Methods, 3 (2): 214–228, doi:10.1137/0603021, MR 0655562.
  2. ^ a b c d e f Charbit, Pierre; de Montgolfier, Fabien; Raffinot, Mathieu (2012), "Linear time split decomposition revisited", SIAM Journal on Discrete Mathematics, 26 (2): 499–514, arXiv:0902.1700, doi:10.1137/10080052X, MR 2967479.
  3. ^ a b Gabor, Csaba P.; Supowit, Kenneth J.; Hsu, Wen Lian (1989), "Recognizing circle graphs in polynomial time", Journal of the ACM, 36 (3): 435–473, doi:10.1145/65950.65951, MR 1072233.
  4. ^ Ma, Tze Heng; Spinrad, Jeremy (1994), "An O(n2) algorithm for undirected split decomposition", Journal of Algorithms, 16 (1): 145–160, doi:10.1006/jagm.1994.1007, MR 1251842.
  5. ^ Dahlhaus, Elias (2000), "Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition", Journal of Algorithms, 36 (2): 205–240, doi:10.1006/jagm.2000.1090, MR 1769515.
  6. ^ Gavoille, Cyril; Paul, Christophe (2003), "Distance labeling scheme and split decomposition", Discrete Mathematics, 273 (1–3): 115–130, doi:10.1016/S0012-365X(03)00232-2, MR 2025945.
  7. ^ Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics, 160 (6): 708–733, arXiv:0810.1823, doi:10.1016/j.dam.2011.05.007.
  8. ^ Cicerone, Serafino; Di Stefano, Gabriele (1997), "On the equivalence in complexity among basic problems on bipartite and parity graphs", Algorithms and computation (Singapore, 1997), Lecture Notes in Comput. Sci., vol. 1350, Springer, Berlin, pp. 354–363, doi:10.1007/3-540-63890-3_38, ISBN 978-3-540-63890-2, MR 1651043.
  9. ^ a b c d Rao, Michaël (2008), "Solving some NP-complete problems using split decomposition", Discrete Applied Mathematics, 156 (14): 2768–2780, doi:10.1016/j.dam.2007.11.013, MR 2451095.