평면 분리 정리

그래프 이론에서 평면 분리기 정리는 평면 그래프의 등측 불평등의 한 형태로서, 모든 평면 그래프는 정점을 조금만 제거하면 작은 조각으로 분할될 수 있다고 명시한다.특히, $n{\displaystyle }$ ${\displaystyle n}$ -vertex$$ 그래프($O{\displaystyle }$ ${\displaystyle O}$이(가) 빅 O 표기법을 호출하는$$ 경우)에서 $O{\displaystyle }$(${\displaystyle n}$) ${\displaystyle O}$ 정점을$$ 제거하면 그래프를 $각각{\displaystyle \mathrm{}\mathrm{최대}}$ $/$3 {\$displaystyle 2n/$3$$} 정점을 갖는 분리할 수 있다.

구분 정리의 O형인 더 약한 형태(n로그 3/2⁡ n)O(n){O({\sqrt{n}})\displaystyle}대신 구분에{O({\sqrt{n}}\log ^{3/2}n)\displaystyle}vertices는 원래 Ungar(1951년)에 의해,와 힘든 asymptotic 분리기에 크기에 마련과 먼저 립톤 &a에서 증명된 것으로 밝혀졌다.융점.타르잔(1979년).그들의 작업 이후 분리막 정리는 몇 가지 다른 방법으로 재책정되었는데, 정리의 $O{\displaystyle }$($){\displaystyle$O$({\sqrt{n}}}}}$ 기간에$$ 있는 상수가 개선되었고, 특정 종류의 비 평면 그래프로 확대되었다.

분리기 정리를 반복적으로 적용하면 분리기 계층 구조가 생성되는데, 이 계층 구조는 그래프의 나무 분해 또는 가지 분해의 형태를 취할 수 있다.분리 계층 구조는 평면 그래프의 효율적인 분할 및 정복 알고리즘을 고안하는 데 사용될 수 있으며, 이러한 계층 구조에서의 동적 프로그래밍은 이러한 그래프에서 NP-하드 최적화 문제를 해결하기 위한 지수적 시간 및 고정 매개변수 추적 가능한 알고리즘을 고안하는 데 사용될 수 있다.분리기 계층 구조는 유한 요소 방법에서 발생하는 희박한 선형 방정식 시스템을 해결하기 위한 가우스 제거의 효율적인 변종인 내포 해부에도 사용될 수 있다.

평면 그래프를 넘어, 고정된 부차, 가장 가까운 인접 그래프, 유한 요소 메쉬를 제외한 그래프를 포함한 다른 종류의 그래프에 구분자 이론이 적용되었다.그래프의 종류에 대한 구분 정리의 존재는 트리 너비와 다항식 확장의 개념에 의해 공식화되고 정량화할 수 있다.

정리명세서

As it is usually stated, the separator theorem states that, in any ${\displaystyle n}$-vertex planar graph ${\displaystyle G=(V,E)}$, there exists a partition of the vertices of ${\displaystyle G}$ into three sets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$, such thateach of ${\displaystyle A}$ and ${\displaystyle B}$ has at most ${\displaystyle 2n/3}$ vertices, ${\displaystyle S}$ has ${\displaystyle O({\sqrt {n}})}$ vertices, and there are no edges with one endpoint in ${\displaystyle A}$ and one endpoint in ${\displaystyle B}$. It is$G{\displaystyle }$ ${\displaystyle G}$의 하위 그래프를 A ${\displaystyle A}$ 또는$$ $B{\displaystyle }$ ${\displaystyle B}$ 양식이$$ 연결되어야 하는 것은 아니다$.$ $S{\displaystyle }$ ${\displaystyle S}$는 이 파티션의 구분자로 불린다.

등가 공식은 $모든{\displaystyle }$ n ${\displaystyle \{\backslash }$$displaystyle$n} -vertex$$ 평면 $그래프{\displaystyle }$G ${\$$displaystyle G_{1}$및 $G$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ $G_$${2$}}의$$ $가장자리-분할$ 수 있는 두 개의 가장자리-분할 수$$$$있는 $것이다.$두 하위 그래프의 정점 집합의 교차점에 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O({\sqrt{n}})$ 정점이$$ 포함되도록 한다.그러한 칸막이를 분리라고 한다.^[1]분리가 주어지면, 정점 세트의 교차점은 분리기를 형성하고, 하나의 서브그래프에 속하지만 다른 형태는 분리되지 않은 정점은 각각 최대 ${\displaystyle \mathrm{2n}}$/ ${\displaystyle 3\mathrm{}}$ ${\displaystyle 2n/3}$의 정점을 갖는 부분 집합이다.다른 방향에서 평면 분리기 정리 조건을 만족하는$$ 세 개의 $집합{\displaystyle }$ A ${\displaystyle$A$\},$ $S{\displaystyle }${\$displaystyle$S$\}$ $및{\displaystyle }$ B ${\displaystyle B}$로 분할이 주어지면 $A{\displaystyle }$ ${\displaystyle$ A$}$에 끝점이 있는 가장자리가 G ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에$$ 속하는 분리가 형성될 수 있다.$Yle G_{1$ 끝점이 $B{\displaystyle }$ ${\displaystyle B}$인 가장자리는 G ${\displaystyle {2\mathrm{}}_{}}$ ${\$2}}에 속하며$$$,$ 나머지 가장자리(두 끝점이 모두 $S{\displaystyle }$ ${\displaysty$ S$\})$는 임의로 분할된다.

분리기 정리 문장의$$ $상수{\displaystyle \mathrm{}}$ 2${\displaystyle }$/ ${\displaystyle 3\mathrm{}}$ ${\displaystyle 2/$${\displaystyle 3}$$}$은 임의적이며 정리 형식을 변경하지 않고$$ 열린 간격$({\displaystyle 1}$/ 2${\displaystyle }$, 1${\displaystyle }$) {\$displaystyle (1/2,1$)의 다른 숫자로 대체될 수 있다: 보다 평등한 하위 집합으로의 분할은 반복적인 sp에 의해 보다 평등한 분할에서 얻을 수 있다.고르지 않은 파티션에 더 큰 세트를 장착하고 결과적으로 연결된 구성 요소를 다시 그룹화한다.^[2]

예

$r{\displaystyle }$ ${\displaystyle r}$ $행$과 c ${\displaystyle c}$ 열이$$ 있는 그리드 그래프를 생각해 보십시오.$$정점의 $숫자$ n ${\displaystyle n}$은 $r{\displaystyle }$${\displaystyle \mathrm{c}}$ ${\displaystyle r=$$5$$\},$ c${\displaystyle }$= ${\displaystyle 8},$ ${\displaystyle n}$=$$= ${\displaystyle 40}$ ${\displaystystyle n=40}.$ 예를 들어$,$ 만약 $그렇다면{\displaystyle }$ .${\displaystyle r}$ ${\displaystyle r}$은(는) 홀수이고, 중앙 행이 하나 있고, 그 이외의 행은 중앙과 똑같이 가까운 두 개가 있다. 마찬가지로 $c{\displaystyle }$ ${\displaystyle c}$이(가) 홀수이면 중앙 열이 하나 있고, 그렇지 않으면 중앙과 똑같이 가까운 두 개의 열이 있다.$이러한{\displaystyle }$ 중앙 행$또는$ 열 중 하나로 S {\$displaystyle$ S}을$($를) 선택하고 그래프에서$$ $S{\displaystyle }$ ${\displaystyle S$$}$을(를) 제거하면 그래프를 두 개의 더 작은 연결된 하위 $그래프{\displaystyle }$ A ${\displaystyle A}$ $및$ B$$${\$$displaystystyle n/2$}의$$ 정점을 $갖는{\displaystyle }$ 두 ${\displaystyle 개}$의 작은 하위 그래프로 분할한다$.$${\displaystyle r}$ ${\displaystyle \le }$ c ${\displaystyle r\leq c}($그림과 동일)인 경우 중앙 열을 선택하면 $r{\displaystyle }$≤${\displaystyle n\sqrt{}}$ ${\$ 정점이$$ 있는$$ 분리자 $S{\displaystyle }$ ${\\displaystyle$ $S$$}$이(가) 표시되며, $마찬가지$로 ${\displaystyle c}$ ${\displaystyle \le }$ r ${\displaystyleq r}$인 분리자를$$ 선택하면 최대 {di가 $표시된다$$.$$splaystyle {\sqrt{n}}$정점$$.따라서 모든 그리드 그래프에는 $최대{\displaystyle \sqrt{}}$ n ${\$ 크기의 구분자$$ $S{\displaystyle }$ ${\displaystyle$ $S$$}$이(가) 있으며$,$ 이 구분자를 제거하여 각각 $최대{\displaystyle }$ ${\displaystyle n\mathrm{}}$/ 2 ${\displaystyn/2$}의 크기를 연결된 두 구성 요소로 분할한다$.$^[3]

평면 분리막 정리는 유사한 칸막이를 어떤 평면 그래프에서도 구성할 수 있다고 명시하고 있다.임의 평면 그래프의 경우는 분리기의 크기가 $O{\displaystyle }$$($$){\displaystyle O({\$$sqrt{n}})$이지만 $두{\displaystyle \sqrt{}}$ 하위 집합 $A{\displaystyle }$ ${\displaystyle A}$ $및{\displaystyle }$ B$$ ${\displaystyle B}$보다 클 수 있다는 점에서 그리드 그래프의 경우와 다르다$($$$가장 일반적인 버전에서).정리의 s)는 ${\displaystyle n\mathrm{}}$/${\displaystyle }$2 ${\displaystyle n/2$}이$($가) 아닌 $2{\displaystyle \mathrm{}}$ ${\displaystyle n}$ / ${\displaystyle 3\mathrm{}}$ ${\displaystyle 2n/3}$이며$,$ 두 하위 집합 $A{\displaystyle }$ ${\displaystyle A}$ 및$$ $B{\displaystyle }$ ${\displaystystyle B}$ 자체는 연결된 하위 그래프를 형성할 필요가$$ 없다.

시공

너비 퍼스트 레이어링

립톤&타르잔(1979)은 필요한 경우 주어진 평면 그래프를 추가 에지로 증가시켜 최대 평면 그래프가 된다(평면 내장의 모든 면은 삼각형이다).그런 다음 임의의 꼭지점 $v{\displaystyle }$ ${\displaystyle v$에서 뿌리를 내린 너비 우선 검색을 수행하고 $v{\displaystyle }$ ${\displaystyle$ v$}$에서 거리를 기준으로 정점을 레벨로 분할한다$.$ ${\displaystyle {l\mathrm{}}_{}}$ 1 ${\$1}가 중위수 수준(높은 수준과 낮은 수준의 정점 수가 최대 $n개{\displaystyle }$)인$$ 경우${\displaystyle n/2}$) then there must be levels ${\displaystyle l_{0}}$ and ${\displaystyle l_{2}}$ that are ${\displaystyle O({\sqrt {n}})}$ steps above and below ${\displaystyle l_{1}}$ respectively and that contain ${\displaystyle O({\sqrt {n}})}$ vertices, res따라서, 그렇지 않으면 ${\displaystyle {l\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$}에 가까운 레벨에 $n{\displaystyle }${\$displaystyle n}$ 이상의$$ 정점이 있을 것이다$.$그들은 폭 우선 검색 트리에 속하지 않고 두 수준 사이에 있는 $G$ ${\displaystyle$ G$}$의 $에지$ e ${\displaystyle$ e$}$의 끝점인$$${\displaystyle {l\mathrm{}}_{}}$ 0 ${\$$0}$과 ${\displaystyle {l\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$2}}의 결합으로 형성된$$ $분리형{\displaystyle }$ S${\$derministerator S}이 있어야 한다는 것을 보여준다.$그리고{\displaystyle }$ e ${\$$displaystyle e$$}$의 끝점에서 두 폭의 첫 번째 검색 트리 경로에 있는 정점을 $레벨{\displaystyle {}_{}}$ l ${\displaystyle 0_{}}$으로 $다시$ 되돌린다$.$이러한 방식으로 구성된$$ $분리기{\displaystyle }$ S ${\displaystyle S}$의 크기는 최대 ${\displaystyle \sqrt{\mathrm{8n}}}$ ${\displaystyle \approx }$ ${\displaystyle 2.83n\sqrt{}}$ ${\$ 2$.83{\sqrt{n}}}$이다$.$분리기의 정점과 두 개의 분리형 서브그래프는 선형 시간에서 찾을 수 있다.^[4]

분리기 정리의 이 증거는 가중 평면 그래프에도 적용되며, 각 정점에 음이 아닌 비용이 발생한다.The graph may be partitioned into three sets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$ such that ${\displaystyle A}$ and ${\displaystyle B}$ each have at most ${\displaystyle 2/3}$ of the total cost and ${\displaystyle S}$ has ${\displaystyle O({$좀 더 신중하게 비슷한 분리기 건설 분석까지 한{A\displaystyle}과 B{B\displaystyle}.[4]에서 아무런 가장자리에 \sqrt{n}})}vertices, Djidjev(1982년)2.45n{\displaystyle{\sqrt{6n}}\approx 2.45{\sqrt{n}}}≈은 S의 크기에 반드시{S\displaystyle}6n로 줄어들 수 있다. 경우 2을 보여 준다.]

홀저 외 (2009) 이 접근법의 단순화된 버전을 제안한다: 그들은 그래프를 최대 평면도로 증가시키고 이전과 같이 넓은 첫 번째 검색 트리를 구성한다.그런 다음 트리의 일부가 아닌$$ 각 $에지{\displaystyle }$ e ${\displaystyle e}$에 대해 $e{\displaystyle }$ ${\displaystyle e}$을(를) 끝점을 연결하는 트리 경로와$$ 결합하여 주기를 형성한다.그런 다음 이러한 주기 중 하나의 정점을 구분자로 사용한다.비록 이 접근방식이 높은 직경의 평면 그래프를 위한 작은 구분자를 찾을 수 있다고 보장할 수는 없지만, 그들의 실험은 많은 종류의 평면 그래프에서 립톤-타르잔 및 지드예프 폭 우선 계층화 방법을 능가한다는 것을 보여준다.^[5]

단순 주기 구분자

이미 최대 평면인 그래프의 경우, 간단한 주기 구분 기구의 더 강한 구성을 보여줄 수 있으며, 주기의 내부와 외부(그래프의 고유한 평면 포함에서) 각각 최대 $[\displaystyle 2n/3}$ 정점을$$ 갖는 작은 길이의 사이클을 보여줄 수 있다.밀러(1986)는 검색 수준이 단순 순환을 이루는 범위 첫 번째 검색의 수정된 버전에 Lipton-Tarjan 기법을 사용하여 ${\displaystyle \sqrt{\mathrm{8n}}}$ ${\$의 구분자 크기로 이를 증명한다$.$^[6]

Alon, 시모어&토마스(1994년):그들은 대부분에 8n{\displaystyle{\sqrt{8n}의 C{C\displaystyle} 사이클}}, C{C\displaystyle}밖에서/에서 대부분의 2n3{2n/3\displaystyle}vertices와 같이 형성된다 vertices 단순 사이클 분리기 더 직접적으로의 존재를 증명한 파티션 안에 a알몬드 제일의 것이다가능한 한 우트사이드(Utside)와 이러한 가정은 $C{\displaystyle }$ ${\displaystyle C}$을(를) 분리자로 강제한다는$$ 것을 보여준다.그렇지 않은 경우, $C{\displaystyle }$ ${\displaystyle C}$의 거리는 $C{\displaystyle }$ ${\displaystyle C}$에 둘러싸인 디스크의 거리와 같아야$$ 한다($$디스크 내부를 통과하는 더 짧은 경로는 더 나은 사이클의 경계의 일부를 형성할 것이다).또한 $C{\displaystyle }$ ${\displaystyle C}$의 길이는 정확히 ${\displaystyle \sqrt{\mathrm{8n}}}$ ${\$이어야 하며$$$,$ 그렇지 않으면 가장자리 중 하나를 삼각형의 다른 두 면으로 교체하여 개선할 수 있다.If the vertices in ${\displaystyle C}$ are numbered (in clockwise order) from ${\displaystyle 1}$ to ${\displaystyle {\sqrt {8n}}}$, and vertex ${\displaystyle i}$ is matched up with vertex ${\displaystyle {\sqrt {8n}}-i+1}$, then these matched pairs can be connected by vertex-disjoint pa평면 그래프를 위한 Menger의 정리 형태에 의한 디스크 내.그러나 이러한 경로의 총 길이는 반드시 모순인$$$n{\displaystyle }$ ${\displaystyle n}$을 초과할 것이다.일부 추가 작업을 통해 유사한 방법으로 $크기$가 ${\displaystyle \sqrt{\mathrm{최대}}}$9n${\displaystyle \mathrm{/}\sqrt{2\mathrm{}}}$ ${\displaystyle 12\sqrt{}}$ 2.12n$${\$displaystyle${\$sqrt{9n/2}}\$약$$2.12${\sqrt{n}}}$인 단순 주기 분리기가 존재함을 보여준다$.$^[7]

지드예프 & 벤카테산(1997)은 단순 주기 분리막 정리의 상수 인자를 $1{\displaystyle \mathrm{.}97n\sqrt{}}$ ${\$ 1$.97{\sqrt{n}}$로 더욱 개선했다$.$그들의 방법은 또한 최대 ${\displaystyle 2n\sqrt{}}$ ${\$ 2${\sqrt{n$의 분리기 크기를 가진 음의 정점 가중치를 가진 그래프에 대한 간단한 사이클 분리기를 찾을 수 있으며, 그래프의 더 고르지 않은 분할을 희생하여 더 작은 크기의 분리기를 생성할 수 있다.^[8]최대치가 아닌 쌍방향 평면 그래프에는 거의 선형 시간에 찾을 수 있는 얼굴 길이 벡터의 유클리드 규범에 비례하는 크기를 가진 단순한 주기 분리기가 존재한다.^[9]

원 구분자

Koebe-Andreev-Thurston 원형 포장 정리에 따르면, 모든 평면 그래프는 해당 디스크 쌍이 상호 접하는 경우에만 그래프에서 두 꼭지점이 인접하도록 이음새가 없는 평면 내의 원형 디스크 패킹으로 나타낼 수 있다.밀러 외 연구진(1997)이 보여주듯이, 그러한 패킹의 경우, 최대 ${\displaystyle \mathrm{3n}}$${\displaystyle }$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle 3n/$4$$}개의 디스크가 그 안에 닿거나 그 안에 있고, 3n${\displaystyle }$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle$ $3n$$/4}$개의$$ 디스크가 닿거나 그 밖에 있으며$,$ $O{\displaystyle }$(${\displaystyle n\sqrt{}}$ $){\sqrt{n}}$개의 디스크를$$ 교차하는 원이 존재한다.^[10]

이를 증명하기 위해 밀러 외 연구진.입체 투영을 사용하여 패킹을 3차원의 단위 구면 표면에 매핑한다.투영을 주의 깊게 선택함으로써 구면의 중심은 표면의 디스크 중심점으로 만들어질 수 있으며, 구면의 중심을 통과하는 평면이 각각 디스크의$$ 최대 ${\displaystyle \mathrm{3n}/4\mathrm{}}$ ${\displaystyle 3n/4}$을(를) 포함하거나 교차하는 두 개의 반공간으로 분할한다.중심을 통과하는 평면이 무작위로 균일하게 선택되면 디스크는 반지름에 비례하는 확률로 교차한다.따라서 교차되는 예상 디스크 수는 디스크의 반지름 합계에 비례한다.그러나 반지름의 제곱합은 디스크의 총 면적에 비례하며, 단위 구면의 총 표면적이 상수인 것이 대부분이다.젠센의 불평등과 관련된 주장은 $n{\displaystyle }$ ${\displaystyle n}$ 비-음수$$ 실수의 제곱합이 상수에 의해 제한될 때 숫자 자체의 $합$은 ${\displaystyle O\sqrt{}}$( n${\displaystyle }$) ${\displaystyle O({\sqrt{n}}})$가 된다는 것을 보여준다$.$따라서 무작위 평면에 의해 교차되는 예상 디스크 $수$는 O${\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O({\sqrt{n}})$이며, 최대$$ 수의 디스크를 교차하는 평면이 존재한다.이 평면은 구를 큰 원을 그리며 교차하는데, 이 평면은 원하는 특성과 함께 평면의 원까지 아래로 투영된다.이 원이 교차하는 $O{\displaystyle }$(${\displaystyle n\sqrt{}}$ ${\displaystyle )}$ ${\displaystyle O({\sqrt{n}})$ 디스크는$$ 원 안에 있는 디스크가 원 외부에 있는 정점과 분리되는 평면 그래프 구분 기호의 정점에 해당하며, 이 두 하위 집합 각각에 최대 ${\displaystyle \mathrm{3n}}$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle 3n/4}$ 정점이$$ 있다.^[11]

이 방법은 선형 시간에서 그러한 구분자를 찾는 임의화된 알고리즘과 동일한 선형 시간 경계를 갖는 덜 실용적인 결정론적 알고리즘으로 이어진다.^[10][12]원 패킹의 패킹 밀도에 대해 알려진 한계를 사용하여 이 알고리즘을 주의 깊게 분석함으로써 기껏해야^[13] 크기의 구분자를 찾을 수 있음을 알 수 있다.

비록 이 개선된 분리막 크기 제한은 그래프의 더 불규칙한 분할을 희생시키지만, 스필먼 & 텡(1996)은 알론, 세이모어 & 토마스(1990)의 분리막과 비교하여 내포된 분리의 시간 제한에 개선된 상수 인자를 제공한다고 주장한다.실제로 랜덤 절단면에 대해 균일하지 않은 분포를 사용함으로써 그것이 생산하는 분리기 크기를 더욱 개선할 수 있다.^[14]

밀러 외 인수의 입체 투영은 디스크 중심부의 일정한 부분을 포함하는 가장 작은 원을 고려한 다음 [${\displaystyle 1},{\displaystyle 2}$ ${\displaystyle ]}$ ${\디스플레이$ 스타일 $[1,2]$ 범위에서 균일하게 선택한 상수로 확장함으로써 피할 수 있다$.$ 밀러 외 인수의 경우와 같이 확장된 원을 교차하는 원반은 vali를 형성한다.d 분리기, 예상 시 분리기 크기가 적절하다.결과 상수는 다소 더 나쁘다.^[15]

스펙트럼 분할

그래프의 정점이 그래프에서 파생된 행렬의 고유 벡터 좌표에 의해 그룹화되는 스펙트럼 클러스터링 방법은 오랫동안 비 평면 그래프의 그래프 분할 문제에 대해 경험적 접근법으로 사용되어 왔다.^[16]스필먼 & 텡(2007)이 보여주듯이 스펙트럼 클러스터링은 경계가 있는 평면 그래프에 적용되는 약화된 형태의 평면 분리기 정리에 대한 대체 증거를 도출하는 데도 사용될 수 있다.그들의 방법에서, 주어진 평면 그래프의 정점은 그래프의 라플라시안 행렬의 고유 벡터들의 두 번째 좌표에 의해 정렬되고, 이 정렬된 순서는 칸막이의 작은 면의 정점 수에 대한 칸막이의 절단된 가장자리 수의 비율을 최소화하는 지점에서 분할된다.그들이 보여주는 바와 같이, 경계도의 모든 평면 그래프는 이 유형의 칸막이를 가지고 있는데, 그 비율은 ${\displaystyle \mathrm{O}}$( ${\displaystyle 1\sqrt{}}$/${\displaystyle }$n $){\displaystyle O (1/{\sqrt{n}}}}}.$ 이 칸막이는 균형이 맞지 않을 수도 있지만, 양쪽의 큰 부분 내에서 칸막이를 반복하고 각 반복에서 형성된 컷들의 조합을 취하게 되면 결국 이 칸막이를 얻게 될 것이다$.$$O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle$ O$({\sqrt{n}})$ 가장자리가$$ 있는 균형 파티션.이러한 가장자리의 끝점은 크기 $O{\displaystyle (n}$) ${\displaystyle$ O$({\sqrt{n}})$의 구분자를 형성한다$.$^[17]

모서리 구분 기호

평면 분리기 정리의 변동은 그래프 정점의$$ $두{\displaystyle }$ 부분 집합 A ${\displaystyle A}$과 $B{\displaystyle }$ ${\displaystyle B}$ 사이에서 절단을 형성하는 작은 모서리 집합인 가장자리 분리를 포함한다.두 세트 $A{\displaystyle }$ ${\displaystyle A}$ $및$ B ${\displaystyle B}$은(의견적으로 두 $세트{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{모두}}$ 최대 2n / 3 {\$displaystyle 2n/3})$의 $숫자{\displaystyle }$ n ${\displaysty$ n$}$의 최대 일정 부분 크기를 가져야 하며$$,$$ 그래프의 각 꼭지점은 $정확히{\displaystyle }$ A ${\displayst$의 하나에 속해야 한다${\displaystyle .}$$yle{\displaystyle }$ $A}$ 및 B$$ ${\displaystyle$ B$\}.$구분 기호는 $A{\displaystyle }$ ${\displaystyle A}$에 끝점이 하나 있고 $B{\displaystyle }$ ${\displaystyle B}$에 끝점이 하나 있는 가장자리로 구성된다$.$ 가장자리 구분 기호의 크기에 대한 경계는 정점 수뿐만 아니라 그래프에서 꼭지점 수$:$ 하나의$$꼭지점이 $n{\displaystyle }$- ${\displaystyle 1}$을$$갖는 평면 그래프와 관련이 $있다$.가장자리 구분 기호는 절단의 반대편의 꼭지점에 높은 도 정점을 연결하는 모든 가장자리를 포함해야 하기 때문에 휠 그래프와 별 그래프를 루딩하면 가장자리 수가 하위 선형으로 된 가장자리 구분 기호가 없다.그러나 최대 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$을(를) 가진 모든 평면 그래프에는 크기 $O{\displaystyle (\sqrt{\mathrm{\Delta n}}}$ $){\displaystyle$ O$({\sqrt {\Deltan})$의 가장자리 구분 기호가 있다$$$.$^[18]

평면 그래프의 이중 그래프에 있는 단순 주기 구분 기호는 원래 그래프에서 가장자리 구분 기호를 형성한다.^[19]주어진 평면 그래프의 쌍대 그래프에 Gazit의 단순 사이클 분리기 정리, 밀러(1990년)을 적용해 O(nΔ)로 날카로운 분리기의 크기를 위해 모든 평면 그래프의 크기는 그 벡터의 유클리드 규범에 비례한 가장자리를 말하분리기를 보여 줌으로써 반드시{O({\sqrt{\Delta n}})\displaystyle}을 강화해 준다.의정점 도

Papadimitriou & Sideri(1996)는 $G{\displaystyle }$ ${\displaystyle G}$을(를) 동일한 크기의 두 하위 그래픽으로 분할하는$$ 가장 작은 에지 분리기를 찾기 위한 다항식 시간 알고리즘을 설명한다. $G{\displaystyle }$ ${\displaystyle G}$은 구멍이 없거나 일정한 수의 구멍이 있는 그리드 그래프의 유도 하위 그래프일$$ 때.그러나 임의의 평면 그래프의 경우 문제가 NP-완전하다고 추측하고 임의의 구멍이 많은 그리드 그래프의 경우 임의의 평면 그래프와 문제의 복잡성이 동일하다는 것을 보여준다.

하한

오빠×n{\displaystyle{\sqrt{n}에서};n{\displaystyle s<,{\sqrt{n}}}포인트 최대 S{S\displaystyle}마련함으로써 달성된다 대부분의 그것에(s− 1)/2{\displaystyle s(s-1)/2}그리드 지점의 하위 집합을 동봉할 수 있{\sqrt{n}}}그리드 그래프, s의 집합 S{S\displaystyle}<>\times. 는 d에격자 모서리 근처에 있는 이각선따라서 점의 ${\displaystyle 최소\mathrm{}}$n /$$3 {\$displaystyle n/$3$$}을(를) 나머지 그리드에서 분리하는 구분자를 형성하려면 $s{\displaystyle }$ ${\displaystyle s}$이(가) 최소 ${\displaystyle \sqrt{\mathrm{2n}}}$/ ${\displaystyle \sqrt{3\mathrm{}}}$ ${\displaystyle \approx }$ 0${\displaystyle \mathrm{.}82n\sqrt{}}$ ${\sqrt {2n/3}\sqrt {$n}\$n}이($가)가 되어야$$ 한다$.$

$나머지{\displaystyle }$ 그래프를 최대 ${\displaystyle \mathrm{2n}}$/ $(\displaystyle 2n/3}$ 정점의$$ 하위 그래프로 분할하는$$ 모든 $분리자{\displaystyle }$ S$$${\$$displaystyle$S}에 $대해{\displaystyle }$ S$${\$displaystyle S}$이$($$가{\displaystyle }$) $최소{\displaystyle \sqrt{\mathrm{}}}$ ${\displaystyle \sqrt{4}}$ ${\displaystyle \sqrt{n}}$ n${\displaystyle \sqrt{}}$/ 를 가질$$ 수 있는 n이 $있다$.$27$ 1.${\displaystyle 56n\sqrt{}}$ ${\$ 약$1.56{\sqrt{n$^[2]이 구조는 볼록한 다면체에 의해 구체의 근사치를 하고, 다면체의 각 면을 삼각망으로 교체하며, 구의 표면에 이등분산적 정리를 적용하는 것을 포함한다.

구분 계층

구분자는 평면 그래프의 구분자 계층 구조로 결합할 수 있으며, 반복 분해는 더 작은 그래프로 결합할 수 있다.분리막 계층 구조는 루트 노드가 주어진 그래프 자체를 나타내는 이진 트리로 나타낼 수 있으며, 뿌리의 두 하위 집합 $A{\displaystyle }$ ${\displaystyle A}$ $및$ B$$ ${\displaystyle B}$에서 형성된 유도 하위 그래프에 대한 반복적으로 구성된 분리막 계층 구조의 루트다.

이 유형의 분리자 계층 구조는 주어진 그래프의 트리 분해의 기초를 형성하는데, 여기서 각 트리 노드와 관련된 정점 집합은 해당 노드에서 트리의 루트까지의 경로에 있는 분리자의 결합이다.그래프의 크기는 트리의 각 수준에서 상수 인자에 의해 내려가기 때문에, 분리자의 크기에 대한 상한도 각 수준에서 상수 인자에 의해 내려가기 때문에, 이러한 경로의 분리자의 $크기$는 기하학적 시리즈로 O${\displaystyle }$( $){\displaystyle$ O$({\sqrt{n}}})$에 추가된다$.$즉, 이러한 방식으로 형성된 구분자는 너비 $){\displaystyle$ O$({\sqrt{n}})$를 가지며$,$ 모든 평면 그래프에 트리 $너비{\displaystyle }$ O$){\displaysty O({\sqrt{n})}$가 있음을 보여주는 데 사용할 수 있다$.$

바이너리 트리 상단을 아래로 가로지르고 바이너리 트리의 각 노드와 연관된 유도 하위 그래프 각각에 선형 시간 평면 구분 알고리즘을 적용하여 분리기 계층을 직접 구성하면 $총{\displaystyle }$ O${\displaystyle (n}$ ${\displaystyle \log }$ $){\displaystyle O(n\logn)}$시간이$$ 소요된다.그러나 Lipton-Tarjan 폭 우선 계층화 접근법을 사용하고 적절한 데이터 구조를 사용하여 각 분할 단계를 비선형 시간에 수행함으로써 전체 분리자 계층 구조를 선형 시간 내에 구성할 수 있다.^[20]

루트 노드의 두 자녀가 해당 그래프의 분리 G$$$$1{\$displaystyle G_{1}$및 ${\displaystyle G_{}}$ $2{\displaystyle {}_{}}$ ${\$}}개의 하위 그래프에 대해 재귀적으로 구성된 계층의 루트인 분리가 아닌 분리에 기반한 관련 유형의 계층을 형성하는 경우 전체 구조가 a를 형성한다.나무 분해 대신 나뭇가지 분해이 분해에서 분리의 폭은 다시 어떤 노드에서 계층의 루트까지의 경로에 있는 분리의 크기 합계에 의해 제한되므로, 이러한 방식으로 형성된 모든 분기의 구성은 폭 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O({\sqrt{n})$를 가지폭 O$){\displaystysty$O({\$sq$})를 가지고 있고 평면 그래프는 가지폭 $({\$sq)를 가진다.$rt{n$ 다른 관련 그래프 분할 문제는 NP-완전하지만 평면 그래프의 경우라도 다항 시간 내에 평면 그래프의 최소 너비 분기-배열을 찾을 수 있다.^[21]

분지분지 구성에서 알론, 세이모어 & 토마스(1994)의 방법을 더 직접적으로 적용함으로써, 포민 & 틸리코스(2006a)는 모든 평면 그래프는 알론 외 연구소의 단순 주기 분리 정리에서와 동일한 상수로 최대${\displaystyle \mathrm{}}2$.$[\$의 가지 폭을 가지고 있음을 보여준다.그래프의 트리 너비가 최대 $3{\displaystyle \mathrm{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle 3/2}$이므로 평면 그래프의 트리${\displaystyle \mathrm{너비}}$가$$ 3.18n {\$displaystyle$3.$18{\$sqrt{$n}}$임을 알 수 있다$.$

기타 클래스 그래프

일부 희소성 그래프에는 하위 선형의 구분자가 없다. 확장기 그래프에서 정점의 일정 부분까지의 삭제는 여전히 하나의 연결된 구성요소만 남는다.^[22]

아마도 가장 초기에 알려진 분리막 정리는 요르단(1869)의 결과일 것이다. 어떤 트리는 하나의 꼭지점을 제거하여 각각 $최대{\displaystyle }$ ${\displaystyle n\mathrm{}}$/ 2 ${\displaystyle n/2}$정점의$$ 하위 트리로 분할될 수 있다.^[10]특히 최대 성분 크기를 최소화하는 정점에는 이 특성이 있는데, 만약 그렇지 않다면 고유한 큰 하위 트리의 인접 부분이 훨씬 더 좋은 파티션을 형성할 것이기 때문이다.임의 그래프의 트리 분해에 동일한 기법을 적용하면 어떤 그래프가든 트리 너비와 가장 동일한 크기의 구분자를 가지고 있음을 보여줄 수 있다.

그래프 $G{\displaystyle }$ ${\displaystyle G}$이(가) 평면은 아니지만 속 $g{\displaystyle }$ ${\displaystyle g}$의 표면에 삽입될 수 있는 경우$,$ $O{\displaystyle }$( ${\displaystyle \sqrt{g}}$)$${\$displaysty$ O$({\sqrt {gn})}$ 정점을$$ 갖는 구분 기호가 있다.길버트, 허친슨 & 타르잔(1984)은 립톤 & 타르잔(1979)과 비슷한 접근법을 사용함으로써 이를 증명한다.그들은 그래프의 정점을 너비 우선 수준으로 분류하고, 제거되는 두 가지 수준을 찾아낸다. 이 수준을 제거하면 작은 숫자의 레벨로 구성된 하나의 큰 구성요소가 된다.이 남은 성분은 속주에 비례하는 여러 폭 우선 경로를 제거하여 평면도를 만들 수 있으며, 그 후 나머지 평면 그래프에 립톤-타르잔 방법을 적용할 수 있다.그 결과는 제거된 두 수준과 제거된 두 수준 사이의 수준 수의 균형을 주의 깊게 균형잡은 데서 비롯된다.입력의 일부로 그래프 임베딩이 주어지면, 선형 시간 내에 그 분리기를 찾을 수 있다.$속{\displaystyle }$ g$${\$displaystyle g}$의 그래프에도$$ 크기 $O{\displaystyle (g\sqrt{}}$ $){\displaystyle O({\sqrt {g\Delta$ n$})$의 가장자리 구분자가 있다$.$^[23]

경계 속 그래프는 미성년자 취급을 운영하면서 닫힌 그래프 계열의 예를 형성하고 구분자 이론은 임의의 마이너 폐쇄 그래프 계열에도 적용된다.만약 그래프를 가족 h{h\displaystyle}vertices과 금지된 미성년자가 특히, 그것은, 그와 같은 분리 시간에 O어떤ε 을에{O(n^{1+\varepsilon})\displaystyle}(n1+ ε);0{\displaystyle \varepsilon 을 발견될 O(hn){O(h{\sqrt{n}})\displaystyle}vertices과 격리판다.;0}.^[24]

밀러 외 연구진(1997)의 원 분리기법은 $공간$의 어떤 점이든 일정한 수 $k{\displaystyle }$ ${\$$displaystyle$ $k$$}$에 의해 덮인 속성이 있는 $d{\displaystyle }$ ${\$$displayty$ d}$차원$ 볼 시스템의 교차 그래프로 일반화한다$.$$aystyle d}$ 치수$$ ^[10]및 유한 요소 중첩에서 발생하는 그래프.^[25]이러한 방식으로 구성된 구면 구분자는 입력 그래프를 $최대{\displaystyle }$ n${\displaystyle }$( ${\displaystyle d}$+ ${\displaystyle 1}$)${\displaystyle }$/${\displaystyle }$( ${\displaystyle \mathrm{d}}$+ ${\displaystyle 2}$) ${\displaystyle n(d+1)/(d+2)}$ 정점의$$ 하위 그래프로 분할한다.$k{\displaystyle }$ ${\displaystyle k}$ -ply$$ ball 교차로 그래프와 $k{\displaystyle }$ ${\displaystyle k}$ -near-nearbor$$ 그래프의 구분자 크기는 $O{\displaystyle ({}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/ ${\displaystyle d^{}}$ n ${\displaystyle {1\mathrm{}}^{}}$- 1${\displaystyle {}^{}}$/ ${\displaystyle d^{}}$ ${\displaystystyle O(k^{1/d}$n^{$1-1/d$^[10]

세습적인 그래프 계열이 $크기$가 ${\displaystyle n^{}}$ c$${\$displaystyle$ n$^{c$인 구분자를 가진 분리자 정리를 가지고 있다면, c < {\$displaystyle c<1$}에 대해 그것은 반드시 그것의 얕은 미성년자의 밀도에 대한 다항식인 다항식 확장을 가지고 있다.반대로 다항식 확장을 갖는 그래프는 하위 선형의 구분자 이론이 있다.^[26]

적용들

알고리즘 분할 및 정복

분리기 분해는 평면 그래프의 문제 해결을 위한 알고리즘을 효율적으로 분할하고 정복하는 데 유용할 수 있다.예를 들어, 이런 방법으로 해결할 수 있는 한 가지 문제는 가중 평면 디그래프에서 가장 짧은 주기를 찾는 것이다.이 문제는 다음 단계를 통해 해결할 수 있다.

• 평면 분리기 정리에 따라$$ 지정된 $그래프{\displaystyle }$ G ${\displaystyle$ $G$$}$을(를) 세 하위 $집합{\displaystyle }$ S ${\displaystyle$ $S$$\},$ $A{\displaystyle }$ ${\displaystyle$ A$\},$ $B{\displaystyle }$ ${\displaystyle$ B$}$로 분할
• $A{\displaystyle }$ ${\displaystyle A}$ 및$$ $B{\displaystyle }$ ${\displaystyle B}$에서 최단 주기 재귀적으로 검색
• Dijkstra 알고리즘을 사용하여 $S{\displaystyle }$ ${\displaystyle$ S$}$의 각 $꼭지점{\displaystyle }$ ${\displaystyle$ s$}$에 대해$$$G{\displaystyle }$ ${\displaystyle$ G$}$의 $s$ ${\displaystyle$ s$}$을(를) 통해 가장 짧은 사이클을 찾으십시오$.$
• 위의 단계에서 찾은 사이클 중 가장 짧은 사이클을 반환하십시오.

The time for the two recursive calls to ${\displaystyle A}$ and ${\displaystyle B}$ in this algorithm is dominated by the time to perform the ${\displaystyle O({\sqrt {n}})}$ calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in ${\displaystyle O(n^{3/2}\log n$$)}$시간$$.

동일한 최단 주기 문제에 대한 더 빠른 $알고리즘$이 시간${\displaystyle }$O(${\displaystyle n^{}}$ ${\displaystyle {log\mathrm{}}^{}}$ 3${\displaystyle {}^{})n}$ $){\displaystyle O(n\log$ $^{3}n)$에 의해 제공되었다.그의 알고리즘은 동일한 분리자 기반 분할 및 정복 구조를 사용하지만 임의 분리자보다는 단순한 주기 분리자를 사용하므로 $S{\displaystyle }$ ${\displaystyle S}$의 정점이 주기 분리자 내외의 그래프의 단일 면에 속한다$$.그런 다음 그는 평면 그래프의 단일 면에 있는 모든 정점으로부터 최단 경로를 찾고 두 하위 그래프로부터의 거리를 결합하기 위해 더 정교한 알고리즘으로 Dijkstra의 알고리즘에 $대한{\displaystyle }$ O${\displaystyle }$($){\displaystyle O({\sqrt{n}}})$의 개별 호출을 대체한다.하지만 지도자 없는 가중 평면 그래프로 가장 짧은 사이클은 쌍대 그래프의 최소 상처에 그리고 O에서 부담이 없는 지도자 없는 평면 그래프(그것의 둘레)에{O(n\log\log n)\displaystyle}time,[27]과 최단 주기(n로그 ⁡ 로그⁡ n)시간에 O{O(n)\displaystyle}.[28](Howev(n) 찾을 수 있을 것 찾을 수 있는 동일한 있다.어,가중치가 없는 그래프에 대한 더 빠른 알고리즘은 분리자 정리를 기반으로 하지 않는다.)

프레드릭슨은 평면 그래프에서 분리기 정리를 구현함으로써 단일 소스의 최단 경로에 대한 또 다른 더 빠른 알고리즘을 제안했다.^[29]이것은 정점의 세심하게 선택된 부분집합에 반복적인 검색으로 Dijkstra 알고리즘의 개선이다.이 버전은 $n{\displaystyle }$ ${\displaystyle n}$ -vertex$$ 그래프에서 $O{\displaystyle (n}$ ${\displaystyle \sqrt{\log }}$ ${\displaystyle \sqrt{n}}$) ${\displaystyle O(n{\sqrt {\log n})}$시간이$$ 소요된다.구분자는 그래프의 분할, 즉 에지 집합의 분할을 두 개 이상의 부분 집합(지역이라고 함)으로 찾는 데 사용된다.노드의 일부 가장자리가 노드와 충돌할 경우 노드가 지역에 포함된다고 한다.둘 이상의 영역에 포함된 노드를 이를 포함하는 영역의 경계 노드라고 한다.$이{\displaystyle }$ 방법에서는 O ($){\displaystyle O$$$$({\sqrt$${$r$$$})$ 경계$$ 노드를 포함한 $O{\displaystyle }$( r${\displaystyle }$) ${\displaystyle O(r)}$ 노드를$$ 각각 포함하는 그래프 $구획$인 n$$${\$$displaystystyle n$$}$ -node$$$$ 그래프의${\displaystyle }개념$을 사용한다${\displaystyle .}$프레드릭슨은 분리기 정리의 재귀적 적용에 의해 $($ ${\displaystyle \log }$ ${\displaystyle }$$n$${\displaystyle }$){\$displaystyle O(n\log$ n$)}$시간$$ $내$에 r$${\displaystyle $r}$ $-division$을 찾을 수 있다는$$ 것을 보여주었다.

문제를 해결하기 위한 그의 알고리즘의 스케치는 다음과 같다.

1. 사전 처리 단계: 그래프를 신중하게 선택한 정점의 하위 집합으로 분할하고 이 하위 집합에서 이 경로의 중간 정점이 하위 집합에 없는 모든 정점 쌍 사이의 최단 경로를 결정한다.이$$ 단계에서는 평면 그래프 ${\displaystyle {G\mathrm{}}_{}}$ 0 ${\$을(를) 3보다 큰 정점이 $없는$ G ${\displaystyle G}$로 변환해야 한다.오일러 공식의 한 줄기에서 결과 그래프의 정점 수는 $n{\displaystyle }$≤ ${\displaystyle 6}$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$- ${\displaystyle 12}$ ${\displaystyle$ n$\leq 6n_{0}-12}$이며$,$ 여기서 ${\displaystyle {n\mathrm{}}_{}}$ 0 ${\$은 $G{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$의 정점 수입니다$.$또한 이 단계는 적합한 $r{\displaystyle }$ ${\displaystyle r}$ -division의$$ 다음과 같은 속성을 보장한다.평면 그래프의 적절한 $r{\displaystyle }$ ${\displaystyle r}$ 분할은$$ $다음$과 같은 r$$ ${\displaystyle$ r$} 분할$이다.
   • 각 경계 꼭지점은 최대 3개 영역에 포함되며,
   • 연결되지 않은 모든 영역은 연결된 구성요소로 구성되며, 모든 영역은 하나 또는 두 개의 연결된 영역의 정확히 동일한 집합으로 경계 정점을 공유한다.
2. 검색 단계:
   • 주추력:소스에서 부분 집합의 각 꼭지점까지의 최단 거리를 찾는다.부분 집합의$$ $꼭지점{\displaystyle }$ v ${\displaystyle v}$이(가) 닫히면 $v{\displaystyle }$ ${\displaystyle v}$에서 $w{\displaystyle }$ ${\displaystyle w}$까지의 경로가 존재하는 하위 집합의$$ $모든{\displaystyle }$ 정점에 대해 임시 거리 $d{\displaystyle (w}$ ${\displaystyle )}$ ${\displaystyle$ $d(w)}$을(가) 업데이트해야 한다$$$.$
   • 소탕: 남아있는 모든 꼭지점까지의 최단 거리를 결정하라.

헨징어 외비음극 에지 길이용 평면 그래프의 단일 소스 최단 경로 알고리즘에 대한 프레드릭슨의 $r{\displaystyle }$ ${\displaystyle r}$ -division$$ 기법을 확장하고 선형 시간 알고리즘을 제안했다.^[30]Their method generalizes Frederickson's notion of graph-divisions such that now an ${\displaystyle (r,s)}$-division of an ${\displaystyle n}$-node graph is a division into ${\displaystyle O(n/r)}$ regions, each containing ${\displaystyle r^{O(1)}}$ nodes, each having at most ${$$\displaystyle s}$ 경계$$ 노드.(${\displaystyle r}$, ${\displaystyle s}$) ${\displaystyle (r,s)}$ -division을$$ 작은 영역으로 반복적으로 분할하는 경우, 이를 재귀적 분할이라고 한다.이 알고리즘은 대략 ${\displaystyle {\mathrm{로그}}^{}}$ ${\displaystyle {}^{}n}$ ${\displaystyle \log ^{*n}$ 수준의$$ 눈금을 사용하며, 여기서 ${\displaystyle {\mathrm{로그}}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$은 반복 로그 함수를 나타낸다.재귀분할은 $잎$이 G ${\displaystyle G}$의 구별되는 가장자리에 의해 라벨이 붙여진 뿌리나무에 의해 표현된다$.$ 나무의 $뿌리는{\displaystyle }$ G$${\$displaystyle$G}의 모든 부분으로 구성된 영역을 나타내고$,$ 뿌리의 아이들은 그 지역이 분할되는 등의 하위 영역을 나타낸다.각 잎(원자 영역)은 정확히 하나의 가장자리를 포함하는 영역을 나타낸다.

내포된 해부는 유한요소법에서 발생하는 것과 같은 평면 그래프 구조로 선형 방정식의 희박한 대칭 시스템을 해결하기 위한 가우스 소거의 분리와 정복 변동에 기초한 분리기법이다.여기에는 방정식의 체계를 설명하는 그래프의 구분자를 찾아내고, 구분자에 의해 서로 분리된 두 하위 문제에서 변수를 반복적으로 제거한 다음 구분자에서 변수를 제거하는 작업이 포함된다.^[31]이 방법의 채우기(행렬의 Cholesky 분해 결과의 0이 아닌 계수 수)는 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle }$ n$){\displaystyle O(n\log n)}$이므로$$^[32]이 방법은 동일한 문제에 대해 반복적인 방법으로 경쟁력을 가질 수 있다.^[31]

클라인, 모제스 및 웨이먼은^[33] $O{\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle O(n\log ^{2}n)}$ -시간$$, 선형 공간 알고리즘을 제공하여 음의 주기가 없는 양과 음의 호 길이가 있는 방향 평면 그래프의 경우 소스 꼭지점$s{\displaystyle }$ {\$displaysty s}$에서 다른 모든 정점까지의 최단 경로 거리를 찾아냈다.Their algorithm uses planar graph separators to find a Jordan curve ${\displaystyle C}$ that passes through ${\displaystyle O({\sqrt {n}})}$ nodes (and no arcs) such that between ${\displaystyle n/3}$ and ${\displaystyle 2n/3}$ nodes are enclosed by ${\displaystyle C}$. Nodes through$C{\displaystyle }$ ${\displaystyle C}$이(가) 통과하는 경계 노드.원본 그래프 $G{\displaystyle }$ ${\displaystyle G}$은(는$)$ $C{\displaystyle }$ ${\displaystyle C}$을(를) 따라 평면 내장하고 경계$$ 노드를 복제하여 G 0$$ {\$displaystyle G_{0}$과 ${\displaystyle {G\mathrm{}}_{}}$ 1 ${\$두 개의 하위 그래프로 분리된다$$.각 그래프 ${\displaystyle {Gi}_{}}$ ${\$의 경계 노드는 단일 면 ${\displaystyle F_{}}$ i ${\$의 경계 위에 놓여 있다$$$.$

이들의 접근방식에 대한 개요는 다음과 같다.

• 재귀 호출:첫 번째 단계는 각 그래프 ${\displaystyle {Gi}_{}}$ ${\$ 내에서$$ $r{\displaystyle }$ ${\displaystyle r}$로부터의 거리를 반복적으로 계산한다$.$
• 부품 내 경계-간격차내 경계-간격:각 그래프 ${\displaystyle {Gi}_{}}$ ${\$에 대해 경계 노드 사이의$$ 모든 ${\displaystyle {거리}_{}}$를 Gi$${\$displaystyle$G_${i$}로 계산한다$$.이 작업은 $O{\displaystyle (n}$ ${\displaystyle \log \mathrm{logn}}$) ${\displaystyle O(n\log$ n$)}$시간이$$ 소요된다.
• 단일 소스 간 경계 거리:$G{\displaystyle }$ ${\displaystyle G}$의 최단 경로는 $G{\displaystyle {}_{}}$ 0 ${\$과 $G{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$사이를 왕복하여$$$$ $r{\displaystyle }$ ${\displaystyle r}$에서 모든 경계 노드에 이르는$$ $G{\displaystyle }$ ${\displaystyle G}$의 거리를 계산한다.교대 반복은 G ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 및$$ G ${\displaystyle {1\mathrm{}}_{}}$ ${\$}의 모든 경계-간격을 사용한다$.$반복 횟수는 $O{\displaystyle (n}$) ${\displaystyle O({\sqrt{n$이고, 이 단계의 전체 $시간$은 O${\displaystyle (n}$ ${\displaystyle \alpha )(n}$ ${\displaystyle )}$ ${\displaystyle$ O$(n\alpha(n)}$이며, 여기서$$ $\alpha {\displaystyle (n}$ ${\displaystyle )}$ ${\displaysty \alpha(n)$는 역 Ackermann 함수다.
• 단일 소스 간 거리:$이전{\displaystyle }$ 단계에서 계산된 거리는 각 G의_i 수정된 버전 내에서 Dijkstra 계산과 함께 r ${\displaystyle r}$에서 모든 노드까지의$$ $G{\displaystyle }$ ${\displaystyle G}$의 거리를 계산하기 위해 사용된다.이 단계는 $O{\displaystyle (n}$ ${\displaystyle \log \mathrm{logn}}$) ${\displaystyle O(n\log$ n$)}$시간이 소요된다$$.
• 단일 소스 거리 재라우팅:$G{\displaystyle }$ ${\displaystyle G}$의 $r{\displaystyle }$ ${\displaystyle r}$로부터의 거리는 음이 아닌 길이로 변환되며$$, 다시 Dijkstra의 알고리즘을 사용하여 $s{\displaystyle }$ ${\displaystyle s}$로부터의 거리를 계산한다$.$이 단계에는 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n\log$ n$)}$시간이$$ 필요하다.

이 알고리즘의 중요한 부분은 가격 함수와 길이를 줄이는 것이다.호 길이 $\ell {\displaystyle (u}$ v${\displaystyle }$) ${\displaystyle \ell(uv)}$이(가) 있는 방향 그래프$G{\displaystyle }$ {\$displaystyle$ G$}$의 경우$,$ 가격 $함수$는 G {\$displaystyle G}$의 노드에서 실제 숫자에 이르는$$ 함수 $\phi {\displaystyle }$ ${\displaysty \varphi$}이다.For an arc ${\displaystyle uv}$, the reduced length with respect to ${\displaystyle \varphi }$ is ${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$. A feasible price function is a price function that induces nonnegative reduced lengths on all arcs of $$${\displaystyle G}$ ${\displaystyle G}$양수와 음의 길이를 포함하는 최단 경로 문제를 음의 길이만 포함하는 문제로 변환하는 데 유용하며, 이 문제는 Dijkstra의 알고리즘을 사용하여 해결할 수 있다.

분리자 기반 분할 및 정복 패러다임은 동적 그래프 알고리즘과^[34] 포인트 위치,^[35] 다각형 삼각측량 알고리즘,^[20] 최단 경로 ^[36]및 가장 가까운 인접 그래프의 구성,^[37] 평면 그래프의 최대 독립 집합에 대한 근사 알고리즘을 설계하는 데도 사용되었다.^[35]

NP-하드 최적화 문제의 정확한 해결

$나무{\displaystyle \sqrt{}}$ 분해 또는 평면 그래프의 분기 배치에 동적 프로그래밍을 사용하여 n ${\$ $또는$ n ${\displaystyle \log }$ ${\displaystyle n}$ ${\displaystyle {\sqrt{n}\logn}$에서 시간 지수적으로 많은 NP-hard 최적화 문제를 해결할 수 있다$.$ 예를 들어, 이 형식의 한계는 최대 독립 집합을 찾는 데 알려져 있다., Steiner trees, Hamiltonian cycles, 그리고 평면 그래프로 여행하는 세일즈맨 문제를 해결하기 위해.^[38]기하학적 그래프를 위한 구분자 이론과 관련된 유사한 방법들이 유클리드 여행 판매원 문제와 스타이너 트리 건설 문제를 같은 형태의 시간 범위로 해결하기 위해 사용될 수 있다.^[39]

평면성을 보존하고 입력 매개 변수의 크기 선형인 커널로 입력 그래프를 줄이는 매개 변수화된 문제의 경우, 이 접근법을 사용하여 입력 그래프 크기에 다항식으로 의존하고 $k{\displaystyle \sqrt{}}$ ${\$}에 기하급수적으로 의존하는 고정 매개변수 추적 가능한 알고리즘을 설계할 수 있다.$ystyle {\sqrt {k$ 여기서 $k{\displaystyle }$ ${\displaystyle$ k}은$($는) 알고리즘의 매개 변수다$$.예를 들어, 이 형식의 시간 범위는 정점 커버를 찾고 k $크기{\displaystyle }$ 집합$(\displaystyle k})$을 지배하는 것으로 알려져 있다$.$^[40]

근사 알고리즘

립톤과 타르잔(1980년)은 분리기 정리를 사용하여 최대 독립 집합을 찾는 것과 같은 평면 그래프에서 NP-하드 최적화 문제에 대한 다항 시간 근사 체계를 얻을 수 있다고 보았다.특히, 분리자 계층을 적절한 수준에서 잘라냄으로써, Fo에 의해 $크기$가 O${\displaystyle }$(${\displaystyle n}$/ ${\displaystyle \sqrt{\log }}$ $){\displaystyle O(n/{\sqrt{\\$$displaystyle$ c$\logn})$인 분리자를 찾을 수 있으며, 이 분리기의 제거는 일정한 c $로그{\displaystyle }$${\displaystyle \log }$ ${\displaystyle n}$ ${\displaysty$ c$\}$에 대해 그래프를 최대 크기의 하위 그래프로 분할한다$.$ur-color 정리, 최소 $n{\displaystyle }$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle n/4$ 크기의 독립된 세트가 존재하므로 제거된 노드는 최대 독립된 세트의 무시할 수 있는 부분을 형성하며, 나머지 하위 그래프에서 최대 독립된 세트는 그 크기에서 시간 지수적으로 독립적으로 찾을 수 있다.분리기 계층 construction[20]에 나중에 linear-time 방법과 테이블 조회와 함께 동형 subgraphs 사이에 독립 집합의 계산을 공유하기 위해서 이 접근법을 접목함으로써, 1− 1/로그⁡ n{\displaystyle 1-1/{\sqrt{\log n}에}크기의 독립적인 세트를 건설하기 위해}최적의 만들어질 수 있다. lin귀로 듣는 시간그러나 이 요인보다 한 개 가까운 근사 비율에 대해 베이커(1994)의 후기 접근법(1994)은 시간 대 근사 품질의 트레이드오프를 더 잘 제공한다.

유사한 분리기 기반 근사 체계는 정점 커버와 같은 다른 어려운 문제에 근사하게 사용되어 왔다.^[41]Arora 외 연구진(1998)은 가중 평면 그래프의 최단 경로 메트릭에 대해 이동 중인 세일즈맨 문제를 근사하기 위해 다른 방법으로 구분자를 사용한다. 그 알고리즘은 구분자 계층의 각 수준에서 구분자를 경계한 횟수만큼 교차하는 최단 투어를 찾기 위해 동적 프로그래밍을 사용한다. 그리고 교차점으로서 표시된다.sing bound 증가는 이러한 방식으로 구성된 투어의 길이를 최적 투어에 가깝게 한다.

그래프 압축

분리기들은 적은 수의 비트를 사용하여 평면 그래프와 기타 분리 가능한 그래프를 나타내기 위한 데이터 압축 알고리즘의 일부로 사용되어 왔다.이러한 알고리즘의 기본 원리는 숫자 $k{\displaystyle }$ ${\displaystyle k$${\displaystyle \}}$을(를) 선택하고$$ 분리기를 사용하여 지정된 평면 그래프를 $최대{\displaystyle }$ k ${\displaystyle k$에서 $크기$의${\displaystyle }$O${\displaystyle (n}$/$)$ {\$displaystyle O(n/{sqrt {k})$ 정점$$(정점)으로 반복적으로 세분화하는 것이다.s. $적절한{\displaystyle }$ k ${\displaystyle k}($$n{\displaystyle }$ ${\displaystyle n$의 로그에 최대 비례)를 선택할 경우 비등형 $k{\displaystyle }$ ${\displaystyle k}$ -vertex$$ 평면 하위 그래프의 수가 분해에 있는 하위 그래프의 수보다 유의하게 적으므로, 모든 th의 표를 구성하여 그래프를 압축할 수 있다.e 가능한 비이형적 서브그래프 및 분리기 내 각 서브그래프를 표로 해당 인덱스에 의해 분해한다.분리기 정점에 의해 형성된 그래프의 나머지 부분은 명시적으로 또는 동일한 데이터 구조의 반복 버전을 사용하여 나타낼 수 있다.이 방법을 사용하면 평면 ${\displaystyle {그래프}_{}}$와 더 제한적인 그래프 패밀리는 이론적으로 최적의 정보를 사용하여 인코딩할 수 있다. $Pn{\displaystyle {}_{}}$ ${\$${\displaystyle }$}n ${\displaystyle n}$ -vertex$$ 그래프가 표시되는 경우 패밀리의 개별 그래프를 나타낼 수 있다.ed only (${\displaystyle 1}$+ ${\displaystyle \mathrm{o}}$ ${\displaystyle (}$ 1${\displaystyle }$) ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle P_{}}$ ${\displaystyle {}_{}}$ ${\$$\log _{2}P_{n}$비트$$.^[42]또한 쿼리에 대한 대답을 나타내는 추가 표 정보로 서브그래프 표를 증가시킴으로써 정점 사이의 인접성을 시험하고 정점의 정도를 결정하며 정점의 인접성을 쿼리당 일정한 시간으로 나열할 수 있는 이러한 유형의 표현을 구성할 수도 있다.^[43]

범용 그래프

그래프의$$ $F{\displaystyle \mathcal{}}$ ${\$ 계열에 대한 범용 그래프는 F ${\$ {$F}$의 모든 멤버를 하위 그래프로$$ 포함하는 그래프입니다.구분 기호를 사용하여 $n{\displaystyle }$ ${\displaystyle$ n$}$ -vertex$$ 평면 그래프가 n ${\displaystyle n}$ 정점과$$ $O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$ )${\displaystyle O(n^{3/2})$ 에지를 갖는$$ 범용 그래프를 표시할 수 있다.^[44]

구조는 분리기 정점의 세 부분 집합의 크기가 그래프 구조에 의존하지 않는 강화된 형태의 분리기 정리를 포함한다: 숫자 $c{\displaystyle }$ ${\displaystyle c}$이(가) 존재하며$,$ 크기는 최대 일정 시간 $n{\displaystyle \sqrt{}}$ ${\$즉 전야의 정점들이 있다.ry ${\displaystyle n}$-vertex planar graph can be separated into subsets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$, with no edges from ${\displaystyle A}$ to ${\displaystyle B}$, with ${\displaystyle S =c}$, and with ${\displaystyle A=B=(n-c)/}$${\displaystyle 2}$ ${\displaystyle A$= B$=(n-c)/2$ 파티션의 모든 구성 $요소$가${\displaystyle }$n / $(\displaystyle n/2$} 정점 이하의 두 하위 집합으로 배열될 수 있을 때까지 그래프를 분할하기 위해 통상적인 형태의 분리기 정리를 사용한 다음 필요에 따라 이러한 하위 집합에서 정점을 분리기로 이동하면 알 수 있다.주어진 크기를 가질 때까지 ry.

일단 이 유형의 분리자 정리가 표시되면, $다시{\displaystyle }$ 그래프 구조에 의존하지 않는 n ${\displaystyle$ n$}$ -vertex$$ 평면 그래프의 분리자 계층을 생성하는 데 사용될 수 있다: 이 계층 구조에서 형성된 트리 구조는 폭 $O{\displaystyle }$( n$){\displaystyle$ O$({\sqrt{n}})$를 가지며, 모든 평면$$ 그래프에 사용할 수 있다.$이{\displaystyle }$ 트리-defocation의 공통 노드에 속하는 이 트리-deposition의 모든$$정점 쌍 $집합$은 $모든$ n ${\displaystyle$ n} -vertex 평면 그래프를 하위 그래프로 포함하는 $(n$ $/2) 정점$이 있는 사소한 완벽 그래프를 형성한다.유사한 구조는 경계 도 평면 그래프가 $O{\displaystyle (n}$ ${\displaystyle \log }$ $){\displaystyle O(n\log$ n$)}$ 에지를$$ 갖는 범용 그래프를 가지고 있다는 것을 보여준다. 여기서 O 표기법에서 숨겨진 상수는 도 경계 도에 따라 달라진다.평면 그래프의 모든 범용 그래프(또는 한도가 없는 나무의 경우에도)에는 $\Omega {\displaystyle \mathrm{}(n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle \Oomega(n\log$ n$)}$개의$$ 가장자리가 있어야 한다.^[44]

에스페레트, 조레트앤모린(2020)은 분리기를 이용한 $O{\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$/ $){\displaystyle O(n^{3/2})$ 공법을$$ ${\displaystyle {n\mathrm{}}^{}}$ 1${\displaystyle {}^{}}$+ ${\displaystyle {\mathrm{o}}^{}}$ ${\displaystyle {(}^{}}$ 1${\displaystyle {}^{}}$) ${\$(1$)$로 개선할 수 있다고 발표했다$.$

참고 항목

• 정점 분리기
• 기하분리기

메모들

참조