에이펙스 그래프

Apex graph
꼭지점 그래프.적색 꼭지점을 제거하여 형성된 하위 그래프는 평면이다.

수학의 한 분야인 그래프 이론에서, 꼭지점 그래프는 하나의 꼭지점을 제거하여 평면도를 만들 수 있는 그래프다.삭제된 정점을 그래프의 정점이라고 한다.꼭지점 그래프가 둘 이상의 꼭지점을 가질 수 있기 때문에 꼭지점이 아니라 꼭지점이다. 예를 들어 최소 비계획 그래프 K 또는5 K에서3,3 모든 꼭지점은 꼭지점이다.꼭지점 그래프에는 그 자체로 평면적인 그래프가 포함되는데, 이 경우 다시 모든 꼭지점이 꼭지점이 된다.null 그래프는 제거할 정점이 없음에도 정점 그래프로 계산된다.

에이펙스 그래프는 미성년자를 대상으로 하는 수술에 따라 폐쇄되며, 링크 없는 임베딩,[1] 하드와이거의 추측,[2] ΔY 축소 가능한 그래프,[3] 나무 폭과 그래프 직경 사이의 관계 등 그래프 부설 이론의 몇 가지 다른 측면에서도 역할을 한다.[4]

특성화 및 인식

정점 그래프는 미성년자를 대상으로 하는 작업 하에서 닫힌다. 즉, 어떤 모서리를 수축시키거나 어떤 정점이나 정점을 제거하면 다른 정점 그래프가 나타난다.G가 꼭지점 v가 있는 정점 그래프인 경우, v와 관련되지 않은 수축 또는 제거는 나머지 그래프의 평면성을 보존한다. v에 대한 에지 인시던트가 수축되는 경우, 나머지 그래프에 대한 효과는 에지의 다른 끝점을 제거하는 것과 동일하다.그리고 v자체가 제거되면 다른 정점을 정점으로 선택할 수 있다.[5]

By the Robertson-시모어 정리, 그들이 마이너 클로즈드 그래프 집단을 형성하기 때문에, 꼭지점 그래프는 금지된 그래프 특성을 가지고 있다.정점 그래프도 아니고 정점 그래프도 아닌 그래프도 부차적으로 또 다른 정점 그래프가 없는 그래프만 아주 많다.이 그래프들은 꼭지점 그래프라는 특성 때문에 금지된 미성년자들이다.다른 그래프 G는 금지된 미성년자 중 어느 누구도 G의 미성년자가 아닌 경우에만 정점 그래프다.이러한 금지된 미성년자에는 피터슨 가의 일곱 개의 그래프, K와5 K의3,3 두 개의 분리된 결합으로 형성된 세 개의 분리된 그래프, 그리고 다른 많은 그래프들이 포함된다.하지만, 이들에 대한 완전한 설명은 여전히 알려지지 않았다.[5][6]

금지된 미성년자들의 완전한 집합이 알려지지 않았음에도 불구하고, 주어진 그래프가 꼭지점 그래프인지 여부를 테스트할 수 있고, 그렇다면 그래프의 꼭지점을 찾기 위해 선형적인 시간 내에 그래프를 찾을 수 있다.보다 일반적으로 고정 상수 k의 경우, 대부분의 k 정점에서 신중하게 선택한 일부 세트의 제거가 평면 그래프로 이어지는 그래프인 k-에이펙스 그래프를 선형 시간 내에 인식할 수 있다.[7]그러나 k가 가변적일 경우 문제는 NP-완전이다.[8]

색수

모든 꼭지점 그래프에는 최대 5개의 색수가 있는데, 기본 평면 그래프는 4가지 색 정리에 의해 최대 4가지 색상이 필요하고, 나머지 정점은 최대 1개의 추가 색상이 필요하다.로버트슨, 시모어&토마스(1993a)그 사건 k의 교정쇄로 6Hadwiger 추측 이 성명이 모든6-chromatic 그래프가는 가벼운 것으로 완전 그래프 미국의 타선:그들은 추측에 대한 최소한의 반례가 되는 삼각형의 그래프인데, 없6-chromatic 정점 그래프 같은 수를 가지고 있는 것으로 나타났다 이 사실을 이용했어.erex풍부함은 존재할 수 없다.

수학의 미해결 문제:

매 6-Vertex 연결 6 -minor-free 그래프는 꼭지점 그래프인가?

(수학에서 더 풀리지 않은 문제)

Jörgensen(1994)은 K를6 마이너로서 가지고 있지 않은 모든 6-Vertex 연결 그래프는 꼭꼭지 그래프여야 한다고 추측했다.이것이 증명된다면, 로버트슨-시모어-하드와이거의 추측에 대한 토마스의 결과는 즉각적인 결과가 될 것이다.[2]요르겐센의 추측은 아직 입증되지 않았다.[9]그러나, 만약 거짓이라면, 그것은 단지 아주 많은 백배수만을 가지고 있을 뿐이다.[10]

로컬 트리 너비

그래프 계열 F는 F의 그래프가 지름과 트리 너비 사이의 함수 관계를 준수하는 경우 로컬 트리 너비를 경계했다. F의 지름-d 그래프의 트리 너비가 최대 ((d)인 함수 ƒ이 존재한다.꼭지점 그래프에는 국부적인 나무 너비가 없다: 꼭지점을 n × n 격자 그래프의 모든 꼭지점에 연결함으로써 형성된 꼭지점 그래프에는 나무 너비 n과 지름 2가 있으므로, 나무 너비는 이러한 그래프에 대한 지름 함수에 의해 제한되지 않는다.그러나 꼭지점 그래프는 경계 로컬 트리 너비와 밀접하게 연결되어 있다. 즉, 로컬 트리 너비를 경계한 마이너 클로즈드 그래프 패밀리 F는 정확히 금지된 미성년자 중 한 명으로 꼭지점 그래프를 가진 패밀리들이다.[4]금지된 미성년자 중 하나로 정점 그래프를 가진 마이너 클로즈드 그래프 집단은 정점 미만으로 알려져 있다.이 용어를 사용하여, 정점-최소-자유 그래프 패밀리가 로컬 트리 너비 경계가 있는 마이너 폐쇄 그래프 패밀리와 동일하다는 사실로 정점 그래프와 로컬 트리 너비 사이의 연결을 다시 작성할 수 있다.

경계가 있는 국부 트리 너비의 개념은 치환성 이론의 기초를 형성하며, 정점-소수자 없는 그래프의 많은 알고리즘 문제를 다항 시간 알고리즘이나 고정 매개변수 추적 가능 알고리즘에 의해 정확히 해결하거나 다항 시간 근사 체계를 사용하여 근사치를 구할 수 있다.[11]에이펙스-미너 그래프 패밀리는 그래프 구조 정리의 강화된 버전을 준수하여 그래프 색칠을 위한 추가적인 근사 알고리즘과 여행 중인 세일즈맨 문제를 야기한다.[12]그러나 이러한 결과 중 일부는 정점 없는 그래프와 관련된 구조 정리를 통해 임의의 마이너-폐쇄 그래프 패밀리로 확장될 수도 있다.[13]

임베딩스

G가 꼭지점 v가 있는 꼭지점 그래프이고, τ이 G\{v}의 평면 내장에서 v의 모든 이웃을 덮는 데 필요한 최소 면수라면, G는 1 - 1의 2차원 표면에 삽입될 수 있다: 단순히 그 개수의 브리지를 평면 내장에 추가하여 v가 연결되어야 하는 모든 면들을 연결하면 된다.예를 들어 외부 평면 그래프( ( = 1)에 꼭지점 하나를 추가하면 평면 그래프가 생성된다.G\{v}가 3개 연결되었을 때, 그의 바운드는 최적 상수 계수 내에 있다. G의 모든 표면 내장에는 적어도 τ/160의 속성이 필요하다.단, 정점 그래프의 표면 내장 최적 속도를 결정하는 것은 NP-힘들다.[14]

SPQR 트리를 사용하여 꼭지점 그래프의 평면 부분의 가능한 임베딩을 인코딩함으로써, 유일한 교차점이 꼭지점을 포함하는 평면에서 그래프의 도면을 계산하여, 총 교차 횟수를 다항식 시간으로 최소화할 수 있다.[15]그러나 임의의 교차가 허용되면 평면 그래프에 단일 에지를 추가하여 형성된 정점 그래프의 특수한 경우에도 교차를 최소화하는 것이 NP-hard가 된다.[16]

꼭지점 그래프도 3차원 공간에 무연계 내장할 수 있다. 그래프의 각 사이클이 그래프의 다른 특징에 의해 교차되지 않는 디스크의 경계인 방식으로 내장될 수 있다.[17]이 형식의 도면은 그래프의 평면 부분을 평면에 그리고 정점을 평면 위에 배치하고 정점을 직선 가장자리에 의한 정점을 각각의 이웃에 연결함으로써 얻을 수 있다.연결성이 없는 내장형 그래프는 피터슨 계열의 7개 그래프를 최소 금지된 미성년자로 하여 마이너 클로즈드 패밀리를 형성하므로,[1] 이러한 그래프는 꼭지점 그래프의 미성년자로서도 금지된다.그러나 꼭지점 그래프가 아닌 연결성 없이 내장 가능한 그래프가 존재한다.

ΔY-축소성

비 ΔY 축소 가능한 에이펙스 그래프에 대한 로버트슨의 예.

연결된 그래프는 스텝 순서에 의해 하나의 꼭지점으로 축소될 수 있는 경우 YΔY-Y 또는 Y-Δ 변환, 자기 루프 또는 다중 인접의 제거, 하나의 이웃과의 정점 제거, 2도 및 그 두 인접 가장자리의 교체가 하나의 가장자리로 가능하다.[3]

꼭지점 그래프와 링크 없는 내장형 그래프처럼 YΔY 축소 가능한 그래프는 그래프 미성년자 아래에서 닫힌다.그리고, 무연계 임베디드 그래프와 마찬가지로, YΔY 축소 가능한 그래프는 피터슨 계열의 7개의 그래프를 금지된 미성년자로 가지고 있어, 이들 그래프가 유일한 금지된 미성년자인지, YΔY 축소 가능한 그래프가 무연고 임베디드 그래프와 동일한지에 대한 의문을 불러일으켰다.그러나 닐 로버트슨은 ΔY가 감소할 수 없는 정점 그래프의 예를 제공했다.모든 정점 그래프는 무연계 임베디드 가능하기 때문에, 이것은 무연계 임베디드 가능하지만 YΔY 축소 가능하지 않은 그래프가 있음을 보여주고, 따라서 YΔY 축소 가능 그래프에는 추가적인 금지된 미성년자가 있음을 보여준다.[3]

로버트슨의 정점 그래프가 그림에 나와 있다.정점 정점을 Rhombic dodecheadron의 세 꼭지점에 각각 연결하거나, 4차원 하이퍼큐브 그래프의 정점 두 개를 직경 반대되는 정점들을 합쳐서 얻을 수 있다.Rhombic dodecheadron의 그래프는 평면이기 때문에, Robertson의 그래프는 꼭지점 그래프다.최소 도 4를 갖는 삼각 자유 그래프여서 어떤 ΔY 감소로도 변경할 수 없다.[3]

거의 평면 그래프

거의 평면 그래프의 예인 16Verex Möbius 사다리를 말한다.

그래프가 꼭지점 그래프라면 꼭 고유한 꼭지점이 있는 것은 아니다.예를 들어, 소수점 이하 비평면 그래프5 K와3,3 K에서는 정점 중 하나를 정점으로 선택할 수 있다.바그너(1967년, 1970년)는 거의 평면 그래프를 모든 정점이 그래프의 정점이 될 수 있는 속성을 가진 비 평면적 정점 그래프로 정의했다. 따라서 K와5 K는3,3 거의 평면적이다.그는 이러한 그래프를 네 개의 하위 집합으로 분류했는데, 그 중 하나는 스트립의 단일 가장자리가 그래프의 해밀턴 사이클과 일치하도록 뫼비우스 스트립에 삽입할 수 있는 그래프로 구성된다.그는 4가지 색 정리의 입증에 앞서 허브 정점을 5가지 색상이 필요한 인접 정점 2개로 교체함으로써 홀수 외부 사이클을 가진 휠 그래프에서 형성된 그래프를 제외하고 거의 모든 평면 그래프는 최대 4가지 색상으로 색칠할 수 있음을 증명했다.또한 그는 거의 모든 평면 그래프가 투사 평면에 내장되어 있다는 것을 단 하나의 예외(입방체의 8-Vertex 보완 그래프)로 증명했다.

하지만, 그 구절"거의 평면 그래프"고도로:이것도 역시 apex graphs,[18]그래프가 평면 graph,[19]와 그래프가 평면을 삽입하는 그래프에서 경계 pathwidth,[20]의"대개"뿐만 아니라그램의 다른 더precisely-defined 세트에 의해 얼굴 모양이 한정적 번호를 대체함으로써 형성될 하나의 가장자리를 첨가하여 형성될 참조하는 데 사용되어 왔다 애매한 것이다.aphs.

관련 그래프 클래스

추상 그래프는 정점을 n개 이하로 삭제하여 평면도를 만들 수 있다면 n-에이펙스라고 한다.1 에이펙스 그래프도 정점이라고 한다.

Lipton 등 (2016) 에 따르면: 없음: Pierce2016 ( 그래프를 평면적으로 만들기 위해 삭제할 수 있는 그래프에 에지가 있으면 그래프가 에지 에이펙스다.그래프를 평면형으로 만들기 위해 수축할 수 있는 그래프에 모서리 부분이 있으면 그래프는 수축-정점이다.

참고 항목

메모들

  1. ^ a b 로버트슨, 시모어&토머스(1993b).
  2. ^ a b 로버트슨, 시모어 & 토마스(1993a).
  3. ^ a b c d 트루엠퍼(1992년).
  4. ^ a b 엡스타인(2000);Demaine & Hajiaghayi(2004년).
  5. ^ a b 굽타&임팔리아초(1991년).
  6. ^ 피어스(2014).
  7. ^ 카와라바야시(2009년).
  8. ^ 루이스 & 얀나카키스(1980).
  9. ^ "Jorgensen's Conjecture", Open Problem Garden, retrieved 2016-11-13.
  10. ^ 카와라바야시 외(2012).
  11. ^ 엡스타인(2000);Frick & Grohe(2001);데메인&하지아헤이(2005년).
  12. ^ 데메인, 하지아헤이 & 카와라바야시(2009년).
  13. ^ 그로헤(2003년).
  14. ^ 모하르(2001년).
  15. ^ 치마니 외 (2009).
  16. ^ 카벨로 & 모하르(2010년).
  17. ^ 로버트슨, 시모어&토머스(1993c).
  18. ^ 로버트슨, 세이모어&토머스(1993c), 엡스타인(2000).
  19. ^ 아치디콘 & 보닝턴(2004년).
  20. ^ 아브라함 & 가보유(2006년).

참조