직렬-병렬 그래프

Series–parallel graph
직렬-병렬 그래프에 대한 직렬 및 병렬 구성 연산

그래프 이론에서, 직렬-병렬 그래프는 단자라고 불리는 두 개의 구별되는 정점을 갖는 그래프이며, 두 개의 단순한 구성 연산에 의해 재귀적으로 형성됩니다. 직렬 및 병렬 전기 회로를 모델링하는 데 사용할 수 있습니다.

정의 및 용어

이런 맥락에서 그래프라는 용어는 멀티그래프를 의미합니다.

직렬-병렬 그래프를 정의하는 방법은 여러 가지가 있습니다. 다음 정의는 기본적으로 David Eppstein이 사용한 정의를 따릅니다.[1]

두 말단 그래프(TTG)는 소스와 싱크라고 불리는 두 개의 구별되는 정점 s와 t를 각각 갖는 그래프입니다.

X와 Y의 두 개의 TTG의 병렬 구성 Pc = Pc(X,Y)는 X와 Y의 소스를 병합하여 Pc의 소스를 생성하고, X와 Y의 싱크를 병합하여 Pc의 싱크를 생성함으로써 그래프 X와 Y의 이산 결합으로 생성된 TTG입니다.

두 개의 TTG X와 Y의 직렬 구성 Sc = Sc(X,Y)는 X의 싱크와 Y의 소스를 병합하여 그래프 X와 Y의 이산 결합으로부터 생성된 TTG입니다. X의 근원은 Sc의 근원이 되고 Y의 싱크는 Sc의 싱크가 됩니다.

TTSPG(two-terminal series-parallel graph)는 단자가 할당된 단일 에지 그래프 K의2 복사본 세트에서 시작하는 직렬 및 병렬 구성의 시퀀스에 의해 구성될 수 있는 그래프입니다.

정의 1. 마지막으로 그래프의 정점 중 일부가 소스 및 싱크로 간주될 때 TTSPG인 경우 그래프를 직렬-병렬(SP-graph)이라고 합니다.

유사한 방법으로 단일 아크 그래프의 복사본으로 구성된 직렬-병렬 디그래프를 정의할 수 있으며 소스에서 싱크로 향하는 아크가 있습니다.

대안적 정의

다음 정의에서는 동일한 클래스의 그래프를 지정합니다.[2]

정의 2. 그래프는 다음 작업의 시퀀스에 의해 K로 변환될2 수 있는 경우 SP-그래프입니다.

  • 한 쌍의 평행 모서리를 공통 끝점을 연결하는 단일 모서리로 대체
  • 소트가 아닌 2도의 꼭짓점에 결합된 한 쌍의 간선을 단일 간선으로 대체하는 것.

특성.

모든 직렬-병렬 그래프의 트리 너비는 최대 2이고 분기 너비는 최대 2입니다.[3] 실제로, 연결된 모든 구성 요소가 직렬-병렬 그래프인 경우, 최대 2개의 분기 폭을 갖는 경우에만, 그래프의 트리 폭은 최대 2개입니다.[4][5] 직렬-병렬 구조를 파괴하지 않고 추가 간선을 추가할 수 없는 그래프인 최대 직렬-병렬 그래프는 정확히 2-트리입니다.

2-연결된 직렬-병렬 그래프는 K와4 동형인 부분 그래프가 없는 것이 특징입니다.[3]

직렬 병렬 그래프는 귀 분해도 특징으로 할 수 있습니다.[1]

계산복잡도

SP-그래프는 선형[6] 시간에서 인식될 수 있으며 선형 시간에서도 직렬-병렬 분해가 구성될 수 있습니다.

특정 유형의 전기 네트워크 모델인 것 외에도, 이 그래프는 최대 일치, 최대 독립 집합, 최소 지배 집합 및 해밀턴 [7]완성을 포함하여 SP 그래프에서 선형 시간으로 많은 표준 그래프 문제를 해결할 수 있기 때문에 계산 복잡도 이론에서 관심이 있습니다. 이러한 문제 중 일부는 일반 그래프의 경우 NP-완전입니다. 이 솔루션은 이러한 문제 중 하나에 대한 답이 두 개의 SP-그래프에 대해 알려진 경우 직렬 및 병렬 구성에 대한 답을 빠르게 찾을 수 있다는 사실을 활용합니다.

일반화

일반화된 직렬-병렬 그래프(GSP-그래프)는 언급된 문제에 대해 동일한 알고리즘 효율성을 갖는 SP-그래프의[8] 확장입니다. GSP 그래프 클래스에는 SP 그래프 클래스와 외부 평면 그래프 클래스가 포함됩니다.

GSP 그래프는 달링 정점(도 1의 정점)의 세 번째 삭제 작업으로 증강된 정의 2에 의해 지정될 수 있습니다. 또는 아래와 같은 작업으로 Definition 1을 증강할 수 있습니다.

  • 두 개의 TTG X와 Y의 소스 병합 S = M(X,Y)는 그래프 X와 Y의 소스를 병합하여 생성된 TTG입니다. X의 소스와 싱크는 각각 S의 소스와 싱크가 됩니다.

SPQR 트리는 임의의 2-정점 연결 그래프에 대해 정의할 수 있는 트리 구조입니다. 직렬-병렬 그래프의 직렬 구성 연산과 유사한 S-노드, 직렬-병렬 그래프의 병렬 구성 연산과 유사한 P-노드, 직렬-병렬 구성 연산에 해당하지 않는 R-노드가 있습니다. 2-연결된 그래프는 SPQR 트리에 R-노드가 없는 경우에만 직렬-병렬입니다.

참고 항목

참고문헌

  1. ^ a b Eppstein, David (1992). "Parallel recognition of series–parallel graphs" (PDF). Information and Computation. 98 (1): 41–55. doi:10.1016/0890-5401(92)90041-D.
  2. ^ Duffin, R. J. (1965). "Topology of Series–Parallel Networks". Journal of Mathematical Analysis and Applications. 10 (2): 303–313. doi:10.1016/0022-247X(65)90125-3.
  3. ^ a b Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Graph classes: a survey. SIAM Monographs on Discrete Mathematics. and Applications. Vol. 3. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 172–174. ISBN 978-0-898714-32-6. Zbl 0919.05001.
  4. ^ Bodlaender, H. (1998). "A partial k-arboretum of graphs with bounded treewidth". Theoretical Computer Science. 209 (1–2): 1–45. doi:10.1016/S0304-3975(97)00228-4. hdl:1874/18312.
  5. ^ Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "On matroids of branch-width three". Journal of Combinatorial Theory, Series B. 86 (1): 148–171. doi:10.1006/jctb.2002.2120.
  6. ^ Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982). "The recognition of series parallel digraphs". SIAM Journal on Computing. 11 (2): 289–313. doi:10.1137/0211023.
  7. ^ Takamizawa, K.; Nishizeki, T.; Saito, N. (1982). "Linear-time computability of combinatorial problems on series–parallel graphs". Journal of the ACM. 29 (3): 623–641. doi:10.1145/322326.322328. S2CID 16082154.
  8. ^ Korneyenko, N. M. (1994). "Combinatorial algorithms on a class of graphs". Discrete Applied Mathematics. 54 (2–3): 215–217. doi:10.1016/0166-218X(94)90022-1. BSSR 과학 아카데미 공지사항에서 번역, Ser. 피지컬.-수학. Sci., (1984) No. 3, pp. 109–111 (러시아어)