헤이븐 (그래프 이론)

그래프 이론에서, 안식처는 방향되지 않은 그래프에서 정점 집합에 있는 특정 유형의 함수를 의미한다.안식처가 존재하는 경우, 게임의 각 단계에서 기능을 컨설팅하여 이동할 안전한 정점 세트를 결정함으로써, 탈출자가 그래프의 추격-탈취 게임을 이기는 데 사용할 수 있다.헤이븐스는 시모어&토머스(1993)가 그래프의 트리 너비를 특징짓는 도구로 처음 도입했다.^[1]그들의 다른 응용 프로그램으로는 마이너 클로즈드 그래프 패밀리에 대한 작은 분리자의 존재를 증명하고,^[2] 끝의 특징과 무한 그래프의 미성년자 집단을 포함한다.^[3][4]

정의

G가 비방향 그래프이고 X가 정점 집합이라면 X-플랩은 X를 삭제하여 형성된 G의 서브그래프에서 비어 있지 않은 연결 성분이다.G에서 순서 k의 haven은 k 정점 이하의 모든 세트 X에 X-플랩 β(X)를 할당하는 함수 β이다.이 함수는 또한 다른 저자에 의해 다르게 주어지는 추가적인 제약조건을 만족시켜야 한다.숫자 k는 안식처의 순서라고 한다.^[5]

세이모어와 토마스의 원래 정의에서 ^[1]안식처는 두 개의 플랩 β(X)와 β(Y)가 서로 접촉해야 하는 특성을 만족시켜야 한다. 즉, 그들은 공통 정점을 공유하거나 각 플랩에 하나의 끝점이 있는 가장자리가 있다.나중에 알론, 세이모어, 토마스에 의해 사용된 정의에서,^[2] 안식처는 오히려 더 약한 단조로움 특성을 만족시키기 위해 필요하다: X ⊆ Y, 그리고 X와 Y 둘 다 k 정점 이하인 경우, 그 다음 β(Y) β(X)이다.감동적인 성질은 단조로운 성질을 내포하지만, 반드시 그 반대의 성질을 내포하고 있다.그러나 시모어와 토마스의^[1] 결과에 따르면 유한 그래프에서 단조로운 성질을 가진 안식처가 존재한다면 같은 질서와 감동적인 성질을 가진 안식처도 존재한다.

감동적인 정의를 가진 안식처들은 모두 서로를 만지는 주어진 그래프의 연결된 하위그래프의 가족인 브램블과 밀접하게 관련되어 있다.브램블의 순서는 패밀리의 모든 하위 그래프를 치는 정점 집합에 필요한 정점의 최소 수입니다.(터치 정의와 함께) 순서 k의 안식처에 대한 플랩 β(X) 집합은 k 정점 이하의 어떤 집합 Y가 서브그래프 β(Y)를 치지 못하기 때문에 적어도 k의 순서 bramble을 형성한다.반대로, 어떤 순서 k의 브레이블에서든, β(X) (X의 각 선택에 대해)를 X와 분리된 브레이블의 모든 하위 그래프를 포함하는 X-플랩으로 정의함으로써 동일한 순서의 안식처를 구성할 수 있다.브래블의 서브그래프가 모두 서로 접촉해야 하는 요건은 이 X-플랩이 존재하고, 이러한 방식으로 선택한 모든 플랩 β(X)가 서로 접촉한다는 것을 보여주는 데 사용될 수 있다.따라서 그래프에는 순서 k의 안식처가 있는 경우에만 순서 k의괄호가 있다.

예

예를 들어 G를 9-Vertex 격자 그래프로 하자.3개 이하의 정점 X를 X-플랩 β(X)에 매핑하여 G에서 순서 4의 안식처를 정의하십시오.

• 다른 어떤 X-플랩보다 큰 고유한 X-플랩이 있는 경우 β(X)를 그처럼 큰 X-플랩으로 한다.
• 그렇지 않으면 임의로 β(X)를 선택하여 X-플랩으로 한다.

사례분석을 통해 이 함수 β가 안식처의 필요한 단조로움 특성을 만족하는지 쉽게 검증할 수 있다.X ⊆ Y와 X가 두 개의 정점 이하를 가지거나 X가 그리드의 모서리 꼭지점의 두 이웃이 아닌 정점 2개를 가지면 X-플랩이 하나뿐이고 모든 Y-플랩을 포함한다.나머지 경우에 X는 모서리 꼭지점의 두 이웃으로 구성되며, X-플랩 2개가 있다. 하나는 그 모서리 꼭지점으로 구성되고 다른 하나는 나머지 6개의 꼭지점으로 구성되는 β(X)로 구성된다.Y를 형성하기 위해 X에 어떤 정점을 더하든, 적어도 4개의 정점을 가진 Y-플랩이 있을 것인데, Y에 없는 정점의 절반 이상을 포함하고 있기 때문에 독특하게 가장 큰 플랩이어야 한다.이 큰 Y-플랩은 β(Y)로 선택되며 β(X)의 하위 집합이 될 것이다.따라서 각각의 경우에서 단조로운 것은 유지된다.

추월-에피션

Havense는 추격-탈취 게임에서 탈취자를 위한 특정 종류의 전략을 모델링하는데, 추격자와 탈취자는 둘 다 주어진 비방향 그래프의 정점에 제한되며, 추격자와 탈취자의 위치는 두 선수 모두에게 알려져 있다.게임의 각 움직임에서, 새로운 추적자가 그래프의 임의 정점에 추가되거나(언제나 그래프에 k 추적자가 배치되는 한), 이미 추가된 추적자 중 한 명이 그래프에서 제거될 수 있다.그러나, 새로운 추적자가 추가되기 전에, 탈출자는 새로운 위치를 먼저 알게 되고, 비어있는 정점으로 그래프 가장자리를 따라 움직일 수 있다.이동하는 동안 탈주자는 추격자 중 이미 어느 누구도 차지하고 있는 정점을 통과하지 못할 수도 있다.

만약 k-헤이븐(단조성 속성이 있는)이 존재한다면, 탈출자는 무한정 포획되는 것을 피할 수 있고, 언제나 X는 이동의 끝에서 추적자가 점유할 정점 집합인 β(X)의 정점으로 이동함으로써 게임에서 이길 수 있다.안식처의 단조로움 특성은 새로운 추적자가 그래프의 정점에 추가되었을 때, β(X)의 정점이 항상 회피자의 현재 위치에서 도달할 수 있음을 보장한다.^[1]

예를 들어, 탈출자는 3 × 3 그리드에서 이 전략을 따르며 3 × 3 그리드의 추격자 3명을 상대로 이 게임을 이길 수 있다.그러나, 같은 그래프에서 네 명의 추적자는 항상 탈출자를 포착할 수 있는데, 먼저 그리드를 두 개의 세 개의 세 개의 버텍스 경로로 분할한 정점 위로 이동한 다음, 탈출자를 포함하는 경로의 중앙으로 이동하여 탈출자를 코너 정점 중 하나로 강제하고, 마지막으로 이 코너에 인접하지 않은 추적자 중 한 명을 제거한다.탈주범 위에 올려놨어따라서 3 × 3 그리드는 순서 5의 안식처가 있을 수 없다.

감동적인 속성을 가진 안식처는 탈주자가 한 세트의 정점에서 다른 한 세트로 동시에 점프할 수 있는 더 강력한 추격자들을 상대로 경기에서 이길 수 있게 해준다.^[1]

트리 너비, 구분 기호 및 마이너 연결

Havense는 그래프의 나무 너비를 특징짓는 데 사용될 수 있다: 그래프는 적어도 k - 1. 나무 너비가 있는 경우에만 순서 k의 안식처가 있다. 나무 분해는 동일한 추적-피싱 게임에서 추적자의 승리 전략을 설명하기 위해 사용될 수 있다. 따라서 탈출자가 최상으로 승리하는 경우에만 그래프가 순서 k의 안식처가 있는 것도 사실이다.추적자보다 적은 사람과 겨루다탈주자가 이긴 게임에서는 안식처가 묘사한 형태의 최적 전략이 항상 있고, 추격자가 이긴 게임에서는 나무 분해에 의해 묘사한 형태의 최적 전략이 항상 존재한다.^[1]예를 들어, 3 × 3 그리드는 순서 4의 안식처가 있지만 순서 5의 안식처가 없기 때문에 트리 너비가 정확히 3이어야 한다.같은 최소-최대 정리는 유한한 트리 너비의 무한 그래프에 일반화할 수 있으며, 그 아래 트리가 광이 없어야 하는 트리 너비의 정의(즉, 끝이 없다)가 있다.^[1]

또한 안식처는 모든 X-플랩이 최대 2n/3 정점을 가질 수 있도록 n-vertex 그래프에 정점 X의 작은 집합인 분리기의 존재와도 밀접하게 관련되어 있다.그래프 G에 k-vertex 구분 기호가 없는 경우, 대부분의 k 정점의 모든 집합 X에는 2n/3 정점 이상의 (유일한) X-플랩이 있다.이 경우 G는 순서 k + 1의 안식처를 가지는데, 여기서 β(X)는 이 독특한 큰 X-플랩으로 정의된다.즉, 모든 그래프에는 작은 분리막이나 높은 질서의 안식처가 있다.^[2]

그래프 G가 일부 정수 h에 대해 k ≥ hn을^3/21/2 갖는 순서 k의 안식처를 갖는 경우, G는 또한 완전한 그래프_h K를 마이너로서 가져야 한다.즉, 순서 k의 안식처가 있는 n-베르텍스 그래프의 하드와이거 번호는 적어도 kn이다^2/3−1/3.그 결과 K-minor-free_h 그래프는 tree width가 hn^3/21/2 미만이고 size가 hn^3/21/2 미만인 구분자를 가진다.보다 일반적으로 트리 너비와 분리기 크기에 대한 O(수평자)는 금지된 미성년자가 특징지을 수 있는 모든 비독점적 그래프 계열에 대해 유지된다. 그러한 가족에는_h K가 포함되지 않을 정도로 일정한 h가 있기 때문이다.^[2]

무한 그래프에서

그래프 G에 시작 꼭지점이 없지만 끝 꼭지점이 없는 반무한 단순 경로인 레이가 포함된 경우, ℵ₀ 순서의 안식처, 즉 정점의 각 유한 집합 X를 X-플랩에 매핑하는 함수 β가 있어 안식처에 대한 일관성 조건을 만족한다.즉, β(X)를 광선의 정점을 무한히 많이 포함하는 고유한 X-플랩으로 정의한다.따라서 무한 그래프의 경우, 나무 너비와 안식처 사이의 연결이 파괴된다. 한 개의 광선은 나무임에도 불구하고 모든 유한한 질서의 안식처와 심지어 더 강력하게 질서의 안식처를 가지고 있다₀.무한 그래프의 두 개의 광선은 한 개의 광선의 정점을 다른 광선의 정점으로부터 무한히 많은 정점을 구분하는 한정된 정점 집합이 없는 경우 등가로 간주된다. 이것은 동등성 관계이며, 그 동등성 등급을 그래프의 끝이라고 한다.

어떤 그래프의 끝도 그 안식처인 질서의 ℵ과₀ 일대일 일치한다.왜냐하면, 모든 광선은 안식처를 결정하고, 두 개의 등가선마다 같은 안식처를 결정한다.^[3]반대로 모든 안식처는 다음과 같은 사례 분석에서 알 수 있듯이 이러한 방식으로 광선에 의해 결정된다.

• If the haven has the property that the intersection ${\displaystyle S=\bigcap _{X}\left(\beta (X)\cup X\right)}$ ( where the intersection ranges over all finite sets X) is itself an infinite set S, then every finite simple path that ends in a vertex of S can be extended to reach an additional vertex of S, and r이 연장 과정을 반복하면 무한히 많은 S 정점을 통과하는 광선이 발생한다.이 광선이 주어진 안식처를 결정한다.
• 한편, S가 유한하면, (하위그래프 G \ S에서 작업함으로써) 비어 있는 것으로 가정할 수 있다.만약 강도는 회피 전략은 피난처에 의해 결정된 이 경우, 각 플레이어와 한정되어 자이 vertices의 설정을 유한 집합 자이+1속성을 X나는 + 1∪β(X나는 1+){\displaystyle X_{i+1}\cup \beta(X_{i+1})에서 자이는 지리멸렬하게 하다}를 품고 있습니다. 경찰은 전략의 특정한 배열로, 그 경로를 주어집니다.follo강도와 결혼하여 안식처를 결정하는 광선을 형성한다.^[4]

따라서 광선의 모든 등가 등급은 고유한 안식처를 정의하며, 모든 안식처는 광선의 등가 등급에 의해 정의된다.

기수 $\kappa {\displaystyle {1\mathrm{}}_{}}$ 1 ${\$}에 대해 무한 그래프 G는 클라이크 마이너 순서 κ가 있는 경우에만 order 순서의 안식처가 있다$.$즉, 헤아릴 수 없는 추기경들의 경우 G에서 가장 큰 안식처 순서는 G의 하드와이거 수이다.^[3]

참조