분기 분해

Branch-decomposition
그리드 그래프의 분기 분해로, e-분리를 보여줍니다.분리, 분해, 그래프 모두 너비가 3입니다.

그래프 이론에서, 무방향 그래프 G의 분기 분해는 G의 가장자리를 잎으로 하는 뿌리 없는 이진수 T로 표현되는 G의 가장자리의 계층적 군집화이다.T에서 엣지를 제거하면 G의 엣지가 2개의 서브그래프로 분할되며, 분해 폭은 이 방법으로 형성된 모든 서브그래프 쌍의 공유 정점의 최대 수입니다.G의 분기 폭은 G의 분기 분해의 최소 폭이다.

분기 폭은 트리 폭과 밀접하게 관련되어 있습니다. 모든 그래프에서 이 두 숫자는 서로 일정한 요인 내에 있으며, 두 수량은 금지된 부계수로 특징지을 수 있습니다.그리고 트리 폭과 마찬가지로, 작은 분기 폭의 그래프에 대해 많은 그래프 최적화 문제를 효율적으로 해결할 수 있다.그러나 나무 너비와 달리 평면 그래프의 분기 너비는 정확하게 다항식 시간으로 계산될 수 있다.분기 분해 및 분기 폭은 그래프에서 매트로이드로 일반화할 수도 있습니다.

정의들

비루트 바이너리 트리는 연결된 무방향 그래프이며, 각 비리프 노드에 정확히 3개의 네이버가 있는 사이클이기는 없습니다.분기 배치는 T의 잎과 주어진 그래프 G=(V,E)의 가장자리 사이의 분기와 함께 미근 2치수 T로 나타나도 좋다.e가 트리 T의 엣지일 경우 T에서e를 삭제하면 2개의 서브트리로1 분할됩니다2.T를 하위 트리로 분할하면 T의 잎과 관련된 에지의 분할이 두 개의 하위 그래프1 G와2 G로 유도된다.G를 두 개의 하위 그래프로 분할하는 것을 e-분리라고 합니다.

e-분리의 폭은 E의1 가장자리와 E의2 가장자리에 모두 입사하는 G의 정점 수이다. 즉, 두 개의 하위 그래프1 G와2 G가 공유하는 정점 수이다.분기 분해의 폭은 전자 분리의 최대 폭입니다.G의 분기폭은 G의 분기분해 최소폭이다.

트리 폭과의 관계

그래프의 분기 분해는 트리 분해와 밀접하게 관련되어 있으며 분기 폭은 트리 폭과 밀접하게 관련되어 있다. 즉, 두 수량은 항상 서로 일정한 요인 내에 있다.특히 Neil Robertson과 Paul Seymour는[1] 분기 폭을 소개한 논문에서 트리 폭 k와 분기 폭 b > 1을 가진 그래프 G에 대해 다음과 같이 보여주었다.

조각 폭

조각 폭은 모서리가 정점으로 대체되는 경우를 제외하고 분기 폭과 유사하게 정의된 개념입니다.조각 분해는 원본 그래프에서 정점을 나타내는 각 잎을 가진 뿌리 없는 이진수 트리로, 절단 폭은 양쪽 서브트리의 정점에 입사하는 가장자리 수(또는 가중 그래프에서는 총 무게)입니다.

분기 폭 알고리즘은 일반적으로 동등한 조각 폭 문제로 감소함으로써 작동합니다.특히 평면그래프의 안쪽 그래프의 조각폭은 원래 [2]그래프의 가지폭의 정확히 2배이다.

알고리즘과 복잡성

그래프 G가 최대 k의 너비의 분기 분해를 가지는지 여부를 결정하는 것은 NP-완전이며,[2] 이때 G와 k는 모두 문제의 입력으로 간주된다.However, the graphs with branchwidth at most k form a minor-closed family of graphs,[3] from which it follows that computing the branchwidth is fixed-parameter tractable: there is an algorithm for computing optimal branch-decompositions whose running time, on graphs of branchwidth k for any fixed constant k, is linear in the size of the input graph.[4]

평면 그래프의 경우 분기폭은 정확하게 다항식 시간으로 계산할 수 있습니다.이는 평면 그래프의 복잡성이 잘 알려진 미해결 [5]문제인 트리 폭과 대조된다.Paul Seymour와 Robin Thomas에 의한 평면 분기 폭의 원래 알고리즘은 n개의 정점이 있는 그래프에서 시간 O(n2)가 걸렸고, 이 너비의 분기 분해를 구성하기 위한 알고리즘은 시간 O(n4)[2]가 걸렸다.이것은 나중에 O(n3)[6]까지 고속화되었습니다.

트리 폭과 마찬가지로 분기 폭은 입력 그래프 폭 또는 [7]매트로이드의 폭에서 기하급수적인 시간을 사용하여 많은 NP-하드 최적화 문제에 대한 동적 프로그래밍 알고리즘의 기초로 사용될 수 있습니다.예를 들어, 쿡 &, 시모어(2003년)는 단일 지구의 용액 변환, 부분 해결책의 조합에서, 이것의 좋은 branch-decomposition을 찾기한 스펙트럼의 군집화 경험적 사용한 보다 그래프를 작성하여 세일즈 맨 문제에 여러 부분 솔루션 통합한 문제에branchwidth-based 동적 계획 법 적용한다. graph, 동적 프로그래밍을 분해에 적용합니다.Fomin&Thilikos(2006년)이 branchwidth 더 treewidth보다 평면 그래프에fixed-parameter-tractable 알고리즘의 개발에서 일한다, 여러가지 이유, 즉 branchwidth 더 단단히 흥미의 treewidth에 범위보다 매개 변수의 함수와 접경하고 있다고 주장한다, 그것이 정확하게 다항 시간에서 m이상 계산할 수 있의 전에ly 근사치이며, 이를 계산하기 위한 알고리즘에는 큰 숨겨진 상수가 없습니다.

매트로이드에 대한 일반화

그래프의 [8]분기 분해를 일반화하는 매트로이드에 분기 분해의 개념을 정의할 수도 있습니다.매트로이드의 분기 분해는 매트로이드 요소의 계층적 군집화이며, 매트로이드의 요소가 잎에 있는 비근원 이진 트리로 표현된다.전자 분리는 그래프와 같은 방법으로 정의할 수 있으며, 매트로이드 요소의 집합 M을 두 개의 하위 집합 A와 B로 분할한다.θ가 매트로이드의 순위함수일 경우, 전자분리폭은 θ(A)+ θ(B)-θ(M)+1로 하고, 분해폭과 매트로이드의 분기폭은 유사하게 정의한다.그래프의 분기폭과 대응하는 그래픽 매트로이드의 분기폭은 다를 수 있다.예를 들어 3엣지 패스 그래프와 3엣지 별은 각각 다른 분기폭 2와 1을 가지지만 둘 다 분기폭 [9]1을 가진 동일한 그래픽 매트로이드를 유도한다.그러나 트리가 아닌 그래프의 경우 그래프의 분기 폭은 연관된 그래픽 매트로이드의 [10]분기 폭과 동일합니다.매트로이드의 분기 폭은 이중 매트로이드의 분기 폭과 같으며, 특히 트리가 아닌 평면 그래프의 분기 폭은 이중 [9]매트로이드의 분기 폭과 동일하다는 것을 의미한다.

분기 폭은 그래프 마이너 이론을 매트로이드 마이너 이론으로 확장하려는 시도의 중요한 구성요소이다. 트리 폭은 매트로이드로도 [11]일반화될 수 있고 그래프 마이너 이론에서 분기 폭보다 더 큰 역할을 하지만 매트로이드 [12]설정에서 분기 폭은 더 편리한 속성을 가진다.Robertson과 Seymour는 특정 유한장에 걸쳐 표현 가능한 매트로이드가 잘 준순서이며, 이는 Robertson-과 유사하다고 추측했다.그래프에 대한 시모어 정리, 그러나 지금까지 이것은 유계 분기폭의 [13]매트로이드에 대해서만 증명되었다.또한 유한한 필드에 걸쳐 표현 가능한 마트로이드 패밀리가 모든 평면 그래프의 그래픽 매트로이드를 포함하지 않는 경우, 패밀리의 매트로이드 분기 폭에 일정한 경계가 존재하여 마트로이드 [14]패밀리에 대한 유사한 결과를 일반화한다.

임의의 고정 상수 k에 대해 분기폭 k의 매트로이드는 독립성 [15]오라클을 통해 매트로이드에 접근할 수 있는 알고리즘에 의해 다항식 시간에 인식될 수 있다.

금지된 미성년자

가지 너비 3의 그래프에 대해 금지된 4개의 미성년자.

로버트슨 씨에 의해...시모어 정리, 분기 폭 k의 그래프는 제한된 부차자 집합으로 특징지을 수 있다.분기 폭 0의 그래프는 일치합니다.최소 금지된 마이너 그래프는 2엣지 경로 그래프와 삼각형 그래프(단순 그래프가 아닌 멀티 그래프가 [16]고려되는 경우 2엣지 사이클)입니다.분기 폭 1의 그래프는 연결된 각 구성요소가 별인 그래프입니다. 분기 폭 1의 최소 금지 부차적 그래프는 삼각형 그래프(단순 그래프가 아닌 다중 그래프가 고려되는 경우 2 에지 사이클)와 3 에지 경로 [16]그래프입니다.분기 폭 2의 그래프는 각 쌍커넥트 성분이 직렬-병렬 그래프인 그래프이다. 유일하게 최소 금지 부차적 그래프 K는 4개의 [16]정점에 있는 완전한 그래프이다4.그래프는 트리 폭 3을 가지며 마이너로서 큐브 그래프가 없는 경우에만 분기 폭 3을 가지며, 따라서 4개의 최소 금지된 마이너 [17]그래프는 큐브 그래프와 함께 트리 폭 3(팔면체 그래프, 완전 그래프5 K 및 와그너 그래프)에 대한 4개의 금지된 마이너 그래프 중 3개입니다.

금지된 미성년자들도 로버트슨에 대한 완전한 유사점이 없음에도 불구하고 매트로이드 분기폭에 대해 연구되었다.이 경우 시모어 정리입니다.매트로이드는 모든 요소가 루프 또는 콜루프 중 하나일 경우에만 분기폭을 가지므로 고유한 최소 금지 마이너 매트로이드 U(2,3)는 삼각형 그래프의 도형 매트로이드이다.매트로이드는 분기폭 2의 그래프의 도형매트로이드인 경우에만 분기폭 2를 가지므로 최소금지 마이너 매트로이드로는 K의4 도형매트로이드와 비도형매트로이드 U(2,4)를 들 수 있다.분기폭 3의 매트로이드는 유한한 필드에 대한 표현성의 추가 가정이 없으면 반순서가 잘 잡히지 않지만, 그럼에도 불구하고 분기폭에 유한한 경계가 있는 매트로이드는 분기폭에서 [18]가장 기하급수적인 많은 최소 금지 마이너 요소를 가지고 있다.

메모들

Wikimedia Commons에는 트리 분해와 관련된 미디어가 있습니다.
  1. ^ 로버트슨 & 시모어 1991, 정리 5.1, 페이지 168.
  2. ^ a b c Seymour & Thomas(1994년).
  3. ^ 로버트슨 & 시모어(1991), 정리 4.1, 페이지 164.
  4. ^ Bodlaender & Thilikos(1997).Fomin, Mazoit & Todinca(2009)는 선형에서 2차로의 정점 수에 대한 의존성 증가를 희생하면서 k, (2⁄k3)에 대한 의존성이 개선된 알고리즘을 설명한다.
  5. ^ Kao, Ming-Yang, ed. (2008), "Treewidth of graphs", Encyclopedia of Algorithms, Springer, p. 969, ISBN 9780387307701, Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.
  6. ^ 구와 타마키(2008년).
  7. ^ 힉스(2000);Hlinnn ( (2003).
  8. ^ 로버트슨 & 시모어 1991.섹션 12, "탱글과 매트로이드", 188–190페이지.
  9. ^ a b Mazoit & Thomassé (2007)
  10. ^ Mazoit & Thomassé (2007);Hicks & McMurray (2007년).
  11. ^ Hlinnn & & Whittle (2006).
  12. ^ Geelen, Gerards & Whittle (2006).
  13. ^ Geelen, Gerards & Whittle (2002);Geelen, Gerards & Whittle (2006).
  14. ^ Geelen, Gerards & Whittle (2006)Geelen, Gerards & Whittle (2007).
  15. ^ Oum & Seymour (2007년).
  16. ^ a b c 로버트슨 & 시모어(1991), 정리 4.2, 페이지 165.
  17. ^ Bodlaender & Thilikos(1999년).네 번째 금지된 트리 폭 3의 단조인 오각 프리즘은 입방체 그래프가 단조로 있기 때문에 가지 폭 3의 경우 최소가 아닙니다.
  18. ^ 홀 등 (2002년);Geelen 등 (2003년).

레퍼런스