SPQR 트리

수학의 한 분야인 그래프 이론에서, 쌍접합 그래프의 삼접합 구성 요소들은 그래프에서 모든 2-vertex 절단을 설명하는 작은 그래프의 시스템이다.SPQR 트리는 컴퓨터 과학, 특히 그래프 알고리즘에서 그래프의 연결된 구성요소를 나타내기 위해 사용되는 트리 데이터 구조입니다.그래프의 SPQR 트리는 선형^[1] 시간 내에 생성될 수 있으며 동적 그래프 알고리즘 및 그래프 드로잉에 몇 가지 응용 프로그램이 있습니다.

그 기본 구조는 SPQR 나무는 그래프의triconnected 구성 요소, 이 분해와 평면 그래프의 평면 embeddings 사이의 연결 내부 먼저 손 더스 매클레인(1937년)에 의해; 이러한 구조물 효율적인 알고리즘에서 몇몇 다른 researchers[2]에 의해 전 형식화하는 사용된 조사를 받았다. SPQ디 바티스타와 타마시아(1989년, 1990년, 1996년)의 R 트리.

구조.

SPQR 트리는 각 노드 x에 대해 무방향 그래프 또는 멀티그래프_x G가 관련지어져 있는 비루트 트리의 형태를 취한다.SPQR이라는 이니셜이 지정된 노드 및 연관된 그래프에는 다음 4가지 유형 중 하나가 있을 수 있습니다.

• S 노드에서 연관된 그래프는 3개 이상의 정점과 모서리를 가진 주기 그래프입니다.이 경우 직렬-병렬 그래프의 직렬 구성과 유사합니다. S는 "계열"^[3]을 나타냅니다.
• P노드에서 관련 그래프는 2개의 정점과 3개 이상의 엣지를 가진 쌍극자 그래프, 사이클 그래프에 대한 평면 쌍대 그래프이다.이 경우 직렬-병렬 그래프의 병렬 구성과 유사합니다. P는 "병렬"^[3]을 나타냅니다.
• Q 노드에서 연관된 그래프는 단일 실제 에지를 가집니다.이 간단한 경우는 모서리가 하나만 있는 그래프를 처리하기 위해 필요합니다.SPQR 트리에 대한 일부 작업에서는 이러한 유형의 노드가 둘 이상의 에지를 가진 그래프의 SPQR 트리에 나타나지 않으며, 다른 작업에서는 가상 이외의 모든 에지가 하나의 실제 에지와 하나의 가상 에지를 가진 Q노드로 표현되어야 하며, 다른 노드 유형의 에지는 모두 가상이어야 합니다.
• R 노드에서 관련 그래프는 사이클 또는 쌍극자가 아닌 3연결 그래프입니다.R은 "강성"을 의미합니다. 평면 그래프 임베딩에서 SPQR 트리를 적용할 때 R 노드의 관련 그래프는 고유한 평면 ^[3]임베딩을 가집니다.

SPQR 트리의 2개 노드 사이의 각 엣지 xy는 2개의 지향성 가상 엣지와 관련지어지며, 하나는 G의_x 엣지이고 다른 하나는 G의_y 엣지입니다.그래프_x G의 각 엣지는 최대 1개의 SPQR 트리 엣지에 대해 가상 엣지가 될 수 있습니다.

SPQR 트리 T는 다음과 같이 형성된 2연결_T 그래프 G를 나타낸다.SPQR 트리 에지 xy가 G의_x 가상 에지 ab와 G의_y 가상 에지 cd를 관련지을 때마다 a와 c를 단일 슈퍼텍스로 병합하고 b와 d를 다른 단일 슈퍼텍스로 병합한 후 두 개의 가상 에지를 삭제하여 하나의 큰 그래프를 형성합니다.즉, 큰 그래프는 G와_y G의_x 2-clique-sum입니다. SPQR 트리의 각 가장자리에서 이 접착 단계를 수행하면 그래프_T G가 생성됩니다. 접착 단계를 수행하는 순서는 결과에 영향을 주지 않습니다.그래프_x G의 각 정점은 이와 같이 G의_T 고유한 정점과 관련지어질 수 있으며, G가 병합된 슈퍼버텍스이다.

일반적으로 SPQR 트리 내에서는 2개의 S노드가 인접하거나2개의 P노드가 인접하는 것은 허용되지 않습니다.이는 이러한 인접관계가 발생했을 경우 2개의 노드가 하나의 큰 노드로 Marge될 수 있기 때문입니다.이러한 가정 하에 SPQR 트리는 그래프에서 고유하게 결정됩니다.그래프 G를 인접한 P 노드 및 인접 S 노드가 없는 SPQR 트리로 나타낼 때 SPQR 트리의 노드와 관련된 그래프_x G를 G의 삼연결 성분으로 한다.

건설

주어진 2-vertex 연결 그래프의 SPQR 트리는 선형 ^[1]시간으로 구성할 수 있습니다.

그래프의 삼접합 구성요소를 구성하는 문제는 Hopcroft & Tarjan(1973년)에 의해 선형 시간 내에 처음 해결되었다.이 알고리즘을 바탕으로 Di Battista & Tamassia(1996)는 컴포넌트 리스트뿐만 아니라 완전한 SPQR 트리 구조를 선형 시간 내에 구축할 수 있어야 한다고 제안했다.GDToolkit 라이브러리의 일부로 SPQR 트리의 느린 알고리즘 구현이 제공된 후 Gutwenger & Mutzel(2001)은 최초의 선형 시간 구현을 제공했다.이 알고리즘의 실장 프로세스의 일환으로서 Hopcroft & Tarjan(1973년)의 초기 작업에서의 에러도 수정했습니다.

Gutwenger & Mutzel(2001) 알고리즘에는 다음과 같은 전체적인 단계가 포함되어 있습니다.

1. 각 끝점에 대해 하나씩 버킷 정렬을 두 번 수행하는 기수 정렬의 변형을 사용하여 끝점의 숫자 인덱스 쌍을 기준으로 그래프의 가장자리를 정렬합니다.이 정렬 단계 후 동일한 두 정점 사이의 병렬 가장자리는 정렬 목록에서 서로 인접하며, 나머지 그래프는 단순하게 남겨두고 최종 SPQR 트리의 P 노드로 분할할 수 있습니다.
2. 그래프를 분할 컴포넌트로 분할합니다.이러한 그래프는 분리된 정점의 쌍을 찾아 이들 두 정점의 그래프를 2개의 작은 그래프로 분할하고(가상 에지의 링크된 쌍이 엔드포인트로 포함), 분리된 쌍이 더 이상 존재하지 않을 때까지 이 분할 프로세스를 반복함으로써 형성할 수 있습니다.SPQR 트리의 S-노드가 되어야 하는 그래프의 부분이 여러 삼각형으로 분할되기 때문에 이 방법으로 발견된 파티션은 고유하게 정의되지 않습니다.
3. 각 분할 구성요소에 P(여러 모서리가 있는 2개의 수직 분할 구성요소), S(삼각형 형태의 분할 구성요소) 또는 R(기타 분할 구성요소)로 레이블을 지정합니다.링크된 가상 엣지 쌍을 공유하는 두 개의 분할 컴포넌트가 있으며 두 컴포넌트 모두 타입 S이거나 둘 다 타입 P인 경우 이들을 같은 유형의 보다 큰 단일 컴포넌트로 병합합니다.

분할된 컴포넌트를 찾기 위해 Gutwenger & Mutzel(2001)은 깊이 우선 검색을 사용하여 팜 트리라고 불리는 구조를 찾습니다.이것은 깊이 우선 검색 트리이며, 가장자리는 트리의 뿌리에서 멀리 떨어져 있고, 트리에 속하는 가장자리에는 루트를 향하고 있습니다.그런 다음 트리에서 노드의 특별한 사전 순서 번호를 찾고 이 번호의 특정 패턴을 사용하여 그래프를 더 작은 구성 요소로 분리할 수 있는 정점 쌍을 식별합니다.이러한 방법으로 구성요소가 발견되면 스택 데이터 구조가 새 구성요소의 일부가 되어야 하는 가장자리를 식별하는 데 사용됩니다.

사용.

2개의 버텍스 컷을 찾아내기

그래프 G의 SPQR 트리(Q 노드 없음)를 사용하면 G에서 u와 v를 제거하면 끊어진 그래프와 나머지 그래프의 연결된 구성 요소가 남도록 G에서 모든 정점 u와 v 쌍을 쉽게 찾을 수 있습니다.

• 두 개의 꼭지점 u와 v는 R 노드와 연관된 그래프에서 가상 에지의 두 끝점이 될 수 있습니다. 이 경우 두 구성 요소는 해당하는 SPQR 트리 에지를 제거하여 형성된 SPQR 트리의 두 하위 트리로 표시됩니다.
• 두 개의 꼭지점 u와 v는 두 개 이상의 가상 에지를 가진 P 노드와 연관된 그래프에서 두 개의 꼭지점일 수 있습니다.이 경우 u와 v를 제거하여 형성된 구성 요소는 노드의 각 가상 에지에 하나씩 SPQR 트리의 하위 트리로 표시됩니다.
• 두 개의 정점 u와 v는 S 노드와 연관된 그래프에서 두 개의 정점일 수 있으며 u와 v가 인접하지 않거나 엣지 uv가 가상입니다.엣지가 가상인 경우 쌍(u,v)도 타입 P 및 R의 노드에 속하며 컴포넌트는 위와 같습니다.2개의 정점이 인접하지 않은 경우, 2개의 구성요소는 S노드와 관련된 사이클 그래프의 2개의 경로 및 이들 2개의 경로에 부착된 SPQR 트리 노드로 나타난다.

평면 그래프의 모든 임베딩 표시

평면 그래프가 3접속되어 있는 경우, 면은 바깥쪽 면이며, 면은 삽입의 방향 중 어느 쪽인지 선택할 수 있는 독특한 평면 매립이 있습니다. 즉, 매립의 면은 그래프의 정확히 비분리 사이클입니다.그러나 2-연결되었지만 3-연결되지 않은 평면 그래프(정점 및 모서리 레이블 포함)의 경우 평면 매립을 찾는 데 더 많은 자유가 있을 수 있습니다.구체적으로는 그래프의 SPQR 트리 내의 2개의 노드가 한 쌍의 가상 에지에 의해 접속될 때마다 노드 중 하나의 방향(미러 이미지로 대체)을 다른 노드에 대해 플립할 수 있다.또한 SPQR 트리의 P 노드에서 P 노드의 가상 에지에 접속된 그래프의 다른 부분을 임의로 순열해도 된다.모든 평면 표현은 다음과 ^[4]같이 설명할 수 있습니다.

「 」를 참조해 주세요.

• 블록 컷 트리, 2-vertex 연결 컴포넌트에 대한 유사한 트리 구조
• Gomory-Hu 트리 그래프의 가장자리 연결을 특징짓는 다른 트리 구조
• 트리 분해(더 이상 고유하지 않음)를 더 큰 컷으로 일반화

메모들

레퍼런스

• 를 클릭합니다Bienstock, Daniel; Monma, Clyde L. (1988), "On the complexity of covering vertices by faces in a planar graph", SIAM Journal on Computing, 17 (1): 53–76, CiteSeerX 10.1.1.542.2314, doi:10.1137/0217004.
• 를 클릭합니다Di Battista, Giuseppe; Tamassia, Roberto (1989), "Incremental planarity testing", Proc. 30th Annual Symposium on Foundations of Computer Science, pp. 436–441, doi:10.1109/SFCS.1989.63515.
• 를 클릭합니다Di Battista, Giuseppe; Tamassia, Roberto (1990), "On-line graph algorithms with SPQR-trees", Proc. 17th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 443, Springer-Verlag, pp. 598–611, doi:10.1007/BFb0032061.
• 를 클릭합니다Di Battista, Giuseppe; Tamassia, Roberto (1996), "On-line planarity testing" (PDF), SIAM Journal on Computing, 25 (5): 956–997, doi:10.1137/S0097539794280736.
• 를 클릭합니다Gutwenger, Carsten; Mutzel, Petra (2001), "A linear time implementation of SPQR-trees", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, pp. 77–90, doi:10.1007/3-540-44541-2_8.
• 를 클릭합니다Hopcroft, John; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing, 2 (3): 135–158, doi:10.1137/0202012, hdl:1813/6037.
• 를 클릭합니다Mac Lane, Saunders (1937), "A structural characterization of planar combinatorial graphs", Duke Mathematical Journal, 3 (3): 460–472, doi:10.1215/S0012-7094-37-00336-3.

외부 링크

• Open Graph Drawing Framework의 SPQR 트리 구현.
• jBPT 라이브러리의 Trconnected 컴포넌트 Java 구현 트리(TCTree 클래스 참조).