무연계 임베딩

수학적 분야인 위상학적 그래프 이론에서 비방향 그래프의 연결 없는 내장이란 그래프의 두 사이클이 연계되지 않는 방식으로 그래프를 3차원 유클리드 공간에 내장하는 것이다.플랫 임베딩은 모든 사이클이 그래프에서 내부가 분리되는 위상 원반의 경계라는 속성을 내장한 것이다.무연동 임베디드 그래프는 무연동 또는 플랫 임베딩이 있는 그래프인데, 이 그래프는 평면 그래프의 3차원 아날로그를 형성한다.^[1]보완적으로, 본질적으로 연결된 그래프는 무연계 내장형 그래프다.

평평한 임베딩은 자동으로 연결되지 않지만, 그 반대의 경우도 아니다.^[2]전체 그래프 K₆, 피터슨 그래프, 그리고 피터슨 계열의 다른 5개의 그래프에는 링크 없는 임베딩이 없다.^[1]Y-Δ 변환에 의해 무연동 임베디드 그래프에서 도달할 수 있는 모든 그래프처럼,^[3] 무연고 임베디드 그래프의 모든 그래프 부분 역시 다시 무연고 임베디드 가능하다.^[2]연결성이 없는 내장형 그래프는 피터슨 계열 그래프를 금지된 미성년자로 하고 ^[4]평면 그래프와 꼭지점 그래프를 포함한다.^[2]이러한 구성 요소는 인식될 수 있으며, $이들$을 위해 평면 임베딩이 구성될 수 있으며, O${\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2$^[5]

정의들

주입 함수( 원의 서로 다른 두 점을 동일한 공간의 점에 매핑하지 않는 연속 함수)에 의해 원이 3차원 유클리드 공간에 매핑될 때, 그 이미지는 닫힌 곡선이다.둘 다 같은 평면에 놓여 있는 두 개의 분리형 닫힌 곡선은 서로 연결되지 않으며, 더 일반적으로 한 쌍의 분리형 닫힌 곡선은 다른 평면을 통과하거나 스스로 통과하지 않고 둘 다 같은 평면으로 이동하는 공간의 연속적인 변형이 있을 때 연결되지 않는다고 한다.이러한 연속 동작이 없을 경우 두 곡선이 연결되어 있다고 한다.예를 들어, Hopf 링크는 각각 다른 하나에 의해 확장된 디스크를 통과하는 두 개의 원에 의해 형성된다.그것은 한 쌍의 연결된 곡선의 가장 간단한 예를 형성하지만, 곡선이 다른 더 복잡한 방법으로 연결될 수 있다.두 곡선이 연결되지 않으면 첫 번째 곡선을 경계로 하고 두 번째 곡선에서 분리하여 우주에서 위상학적 원반을 찾을 수 있다.반대로 그러한 디스크가 있으면 곡선은 반드시 연결되지 않는다.

3차원 공간에서 두 개의 닫힌 곡선의 연결 수는 곡선의 위상학적 불변수로서, 곡선을 서로 통과하지 않고 계속 이동해도 변하지 않는 여러 가지 동등한 방법으로 곡선에서 정의된다.그래프의 무연계 임베딩 정의에 사용되는 연결 번호 버전은 평면상에 임베딩을 투영하고 첫 번째 곡선이 두 번째 모듈로 2를 통과하는 예상 임베딩의 교차 횟수를 계산함으로써 찾을 수 있다.^[2]투영은 "정규적"이어야 하며, 즉 두 정점이 동일한 점으로 투영되지 않아야 하며, 정점이 가장자리의 내부에 투영되지 않아야 하며, 두 가장자리의 투영이 교차적으로 교차하는 투영 지점에서는 두 개의 투영이 동일한 연결 번호로 연결되어야 한다.언링크의 연결번호는 0이므로, 한 쌍의 곡선이 0이 아닌 연결번호를 갖는 경우 두 개의 곡선을 연결해야 한다.단, 연결되었지만 연결 번호가 0인 곡선의 예(예: Whitehead 링크)가 있다.

그래프를 3차원 공간에 내장하는 것은 그래프의 꼭지점에서 공간의 점까지, 그리고 그래프의 가장자리에서 공간의 곡선으로 매핑하여 각 가장자리의 각 끝점이 해당 곡선의 끝점에 매핑되며, 두 개의 서로 다른 가장자리의 곡선이 쉼표를 제외하고 교차하지 않도록 구성된다.가장자리 끝에서어떤 유한 그래프라도 구별되는 단순한 주기의 수가 유한하며(아마도 지수일 것이다) 3차원 공간에 그래프가 내장되어 있다면 이러한 주기는 각각 단순한 닫힌 곡선을 형성한다.이러한 방식으로 형성된 각 쌍의 곡선의 연결 수를 계산할 수 있다. 모든 쌍의 사이클이 0의 연결 수를 갖는 경우 내장은 연결되지 않는다고 한다.^[6]

어떤 경우에는 그래프의 각 사이클에 대해 그래프의 다른 특징을 교차하지 않는 사이클에 의해 경계된 디스크를 찾을 수 있는 방법으로 그래프를 공간에 삽입할 수 있다.이 경우 사이클은 그래프에서 분리되는 다른 모든 사이클에서 연결 해제되어야 한다.임베딩은 모든 사이클이 이러한 방식으로 디스크를 제한하면 평평하다고 한다.^[7]플랫 임베딩은 반드시 링크가 없지만 플랫이 아닌 링크가 없는 임베딩이 존재할 수 있다. 예를 들어, G가 두 개의 디스조인트 사이클에 의해 형성된 그래프이고 화이트헤드 링크를 형성하기 위해 내장되어 있다면 임베딩은 링크가 없지만 플랫은 아니다.

그래프는 어떻게 내장되든 임베딩이 항상 연결되면 본질적으로 연계된다고 한다.링크리스와 플랫 임베딩은 동일하지 않지만 링크리스 임베딩이 있는 그래프는 플랫 임베딩이 있는 그래프와 동일하다.^[8]

예제 및 counterexample

삭스(1983)가 보여주듯이 피터슨 계열의 일곱 개의 그래프는 본질적으로 각각 연결되어 있는데, 이들 그래프가 어떻게 우주에 내장되어 있든 간에 서로 연결된 두 개의 사이클을 가지고 있다.이 그래프에는 전체 그래프₆ K, 피터슨 그래프, 전체 양분 그래프 K에서_4,4 가장자리를 제거하여 형성된 그래프, 전체 3분위 그래프 K가_3,3,1 포함된다.

모든 평면 그래프는 평평하고 연결성이 없는 내장형이다. 즉, 그래프를 평면에 내장하고 평면을 우주에 내장하는 것이다.만약 그래프가 평면이라면, 이것은 그것을 평평하고 연결 없이 우주에 심는 유일한 방법이다: 모든 평평한 임베딩은 평면에 눕도록 연속적으로 변형될 수 있다.반대로, 모든 비플래너 링크 없는 그래프에는 여러 개의 링크 없는 임베딩이 있다.^[2]

평면 그래프에 하나의 꼭지점을 추가함으로써 형성된 정점 그래프도 평면상에 그래프의 평면 부분을 내장하고 평면 위에 정점을 배치하며 정점에서 선 세그먼트로 이웃으로 가장자리를 그리는 등 평면적이고 연결성이 없는 임베딩이 있다.평면 내의 닫힌 곡선은 다른 그래프 형상을 통과하지 않는 평면 아래의 디스크를 경계로 하고, 다른 그래프 형상을 통과하지 않는 평면 위의 디스크를 정점을 통과하는 닫힌 곡선을 경계로 한다.^[2]

그래프에 링크가 없거나 평평한 임베딩이 있는 경우, 가장자리를 세분화 또는 해제하고, 동일한 점 쌍 사이에 여러 개의 가장자리를 추가 또는 제거하고, 세 개의 이웃을 연결하는 삼각형으로 도 3 정점을 대체하는 Y-Δ 변환을 수행하여 그래프를 수정한다.^[2]특히 큐빅 평면 그래프(정확히 모든 정점들이 큐브와 같이 세 개의 이웃을 가지고 있는 그래프)에서는 Y-Δ 변환을 수행하고, 결과 삼각형 가장자리의 여러 복사본을 추가한 다음, 역 Δ-Y 변환을 수행함으로써 정점 집합의 어떤 독립된 정점 집합의 중복을 만들 수 있다.

특성화 및 인식

그래프 G에 링크가 없거나 평평한 임베딩이 있는 경우 G의 모든 부분(가장자리의 수축과 가장자리와 정점의 삭제로 형성된 그래프)에도 링크가 없거나 평평한 임베딩이 있다.삭제는 임베딩의 평탄성을 파괴할 수 없으며, 수축은 수축된 가장자리의 한 끝점을 제자리에 두고 수축된 가장자리의 경로를 따라 다른 끝점으로 입사된 모든 가장자리를 다시 전달함으로써 수행될 수 있다.그러므로 로버트슨-에 의해시모어 정리, 연결성이 없는 내장형 그래프는 한정된 세트의 미성년자를 포함하지 않는 그래프로서 금지된 그래프 특성을 가지고 있다.^[3]

연결성이 없는 내장형 그래프의 금지된 미성년자 집합은 삭스(1983)에 의해 확인되었다. 피터슨 계열의 7개 그래프는 모두 본질적으로 연결된 마이너 미니 그래프들이다.그러나 삭스는 이것들만이 최소한의 연관 그래프라는 것을 증명할 수 없었고, 이것은 마침내 로버트슨, 세이모어 & 토마스(1995)에 의해 달성되었다.

링크 없는 그래프의 금지된 사소한 특성화는 다항 시간 알고리즘을 인식하도록 유도하지만, 실제로 임베딩을 구성하기 위한 것은 아니다.카와라바야시, 크뢰처 & 모하르(2010)는 그래프가 무연계 임베디드 가능한지 여부를 테스트하는 선형 시간 알고리즘을 설명했으며, 그렇다면 그래프의 평면 임베디딩을 구성한다.이들의 알고리즘은 주어진 그래프에서 큰 평면 하위 그래프를 찾아 연결되지 않은 내장이 존재하는 경우 하위 그래프의 평면 내장을 존중해야 한다.그러한 서브그래프가 발견될 때마다 그래프를 반복적으로 단순화함으로써, 그들은 문제를 남은 그래프가 경계 트리 너비를 가진 그래프로 축소하고, 그 시점에서 동적 프로그래밍으로 해결할 수 있다.

주어진 임베딩이 평평한지 또는 연결되지 않은지 여부를 효율적으로 테스트하는 문제는 로버트슨, 세이모어 & 토마스(1993a)에 의해 제기되었다.그것은 미해결 상태로 남아있고, 우주에서 하나의 곡선이 꼬이지 않는지를 시험하는 문제인, 꼬이지 않는 문제와도 같은 복잡성을 지닌다.^[5]비코트성(따라서 임베딩의 연결성 테스트)은 NP에 있는 것으로 알려져 있지만 NP-완전한 것으로 알려져 있지 않다.^[9]

관련 그래프 패밀리

콜린 드 베르디에르 그래프 불변성은 대수 그래프 이론을 사용하여 모든 그래프에 대해 정의된 정수다.콜린 드 베르디에르 그래프가 최대 μ에 불변성을 갖는 그래프는 고정된 상수 μ에 대해 마이너 폐쇄 패밀리를 형성하며, 이 중 처음 몇 개는 잘 알려져 있다: μ μ 1을 갖는 그래프는 선형 숲(경로의 분리 결합), μ μ μ 2를 갖는 그래프는 외측 평면 그래프, μ μ 3을 갖는 그래프는 평면 그래프다.로버트슨, 세이모어&토머스(1993a) 추측과 로바스 & 슈리히버(1998)가 증명했듯이 μ μ 4의 그래프는 정확히 연결성이 없는 내장형 그래프다.

평면 그래프와 꼭지점 그래프는 이 그래프에서 Y-Δ 변환에 의해 얻은 그래프와 같이 연결 없이 내장할 수 있다.^[2]YΔY 환원 가능한 그래프는 Y-Δ 변환, 격리된 정점과 도 1 정점의 제거, 도 2 정점의 압축에 의해 단일 정점으로 축소될 수 있는 그래프로서, 또한 경미하게 닫히고 모든 평면 그래프를 포함한다.단, ΔY를 환원할 수 없는 그래프가 존재하는데, 예를 들어, 정점을 롬방 도데면체의 모든 3도 정점에 연결함으로써 형성된 정점 그래프와 같다.^[10]또한 Y-Δ 변환에 의해 꼭지점 그래프로 변환할 수 없는 링크 없는 그래프, 고립된 꼭지점과 도 1 꼭지점 제거, 도 2 꼭지점 압축 등이 존재한다. 예를 들어 10Vex 크라운 그래프는 링크가 없는 내장형이지만 이러한 방식으로 꼭지점 그래프로 변환할 수 없다.^[2]

무연계 임베딩의 개념과 관련된 것은 매듭 없는 임베딩의 개념으로, 그래프의 단순한 사이클 중 어느 것도 비연계 매듭을 형성하지 않는 방식으로 그래프를 임베딩하는 것이다.매듭 없는 임베딩(즉, 본질적으로 매듭이 지어짐)이 없는 그래프에는 K와₇ K가_3,3,1,1 포함된다.^[11]그러나 본질적으로 연결된 그래프에 하나의 꼭지점을 추가함으로써 형성되지 않는 매듭 없는 내장(이 두 그래프처럼)에 대해 최소한의 금지된 미성년자도 존재한다.^[12]

또한 더욱 복잡한 매듭과 링크가 임베딩에 있거나 유클리드 공간 이외의 3차원 다지관에 무연계 임베딩하여 그래프 패밀리를 정의할 수 있다.^[13][14]플라판, 나이미 & 폼머스하임(2001)은 세 사이클 중 어느 누구도 다른 두 사이클에서 분리할 수 없는 경우 그래프 임베딩이 삼중으로 연결되도록 정의하고 있다. 이들 사이클은 K가₉ 본질적으로 삼중으로 연결되지 않음을 보여주지만 K는 그렇다₁₀.^[15]보다 일반적으로, 위상학적으로 분리된 두 부분으로 분리될 수 없는 n-구성 요소 링크를 포함하는 내장이 n-연계 내장이 되도록 n-연계 내장을 정의할 수 있다. 본질적으로 n-연계된 소소형 그래프는 모든 n에 대한 n-연계 내장을 정의할 수 있다.^[16]

역사

K가₆ 무연계 임베딩이나 평면 임베딩이 있느냐는 문제는 1970년대 초 보테(1973년)에 의해 토폴로지 연구 공동체 내에서 제기되었다.링크리스 임베딩은 무연계 임베딩과 평면 임베딩으로 그래프의 금지된 그래프 특성화를 찾는 문제를 포함한 몇 가지 관련 문제를 제기했던 호르스트 삭스(1983)에 의해 그래프 이론 공동체의 주목을 받았다. 삭스는 피터슨 계열(K₆ 포함)의 7개 그래프에는 그러한 임베딩이 없다는 것을 보여주었다.네셰틸&토머스(1985)가 관찰한 바와 같이, 연결 없이 내장할 수 있는 그래프는 마이너 그래프에 따라 폐쇄되며, 이 그래프는 로버트슨에 의해 추적된다.금지된 그래프 특성화가 존재한다는 시모어 정리.한정된 일련의 방해 그래프가 존재한다는 증거는 이 금지된 미성년자 집합에 대한 명시적인 설명으로 이어지지 않지만, 피터슨 계열의 7개의 그래프가 집합에 속한다는 삭스의 결과에 따른 것이다.이러한 문제들은 마침내 로버트슨, 시모어 & 토마스(1995)에 의해 해결되었는데,^[17] 그는 피터슨 가문의 7개 그래프가 이러한 그래프에 대해 유일하게 금지된 최소의 미성년자라는 것을 보여주었다.따라서 링크 없이 임베디드 가능한 그래프와 플랫 임베디드 가능한 그래프는 모두 동일한 그래프 집합이며, 둘 다 피터슨 계열 부전위가 없는 그래프와 동일하다.

삭스(1983)도 에지 수와 무연계 임베디드 그래프의 색도 수에 대한 한계를 요구했다.n-vertex 링크가 없는 그래프의 에지 수는 최대 4n - 10이다: n > 4의 최대 정점 그래프에는 정확히 이 많은 에지가 있으며,^[1] 마더(1968)는 K-minor-free₆ 그래프의 일반 등급에서 일치하는 상한을 증명했다.네셰틸&토머스(1985)는 색수에 대한 삭스의 질문이 어떤 색채 그래프가든 사소한 k-Vertex 완성 그래프를 가지고 있다는 하드와이거의 추측에 대한 증거에 의해 해결될 것이라고 관측했다.하드와이거 추측의 사례 k = 6의 로버트슨, 세이모어 & 토마스(1993c)의 증거는 삭스의 질문을 해결하기에 충분하다: 어떤 6색 그래프도 K₆ 단위를 포함하고 있고 무연계가 아니며, 5색을 요구하는 K와₅ 같은 무연계 그래프가 존재하기 때문에 무연계 그래프는 최대 5가지 색상으로 채색될 수 있다.스나크 정리는 연결성이 없는 모든 입방체 그래프는 3-엣지 색상이 가능하다는 것을 암시한다.

링크리스 임베딩은 1980년대 후반 펠로우즈 & 랭스턴(1988년)과 모트와니, 라후나단 & 사란(1988년)의 작품을 통해 알고리즘 연구 공동체 내에서 연구되기 시작했다.알고리즘적으로, 금지된 부차적 특성화가 입증된 후에 무연계 및 플랫 임베디블 그래프를 인식하는 문제는 해결되었다: 주어진 그래프에 금지된 7개 미성년자 중 어느 한 명이 포함되어 있는지 다항 시간 내에 테스트하는 데 로버트슨 & 세이모어(1995)의 알고리즘을 사용할 수 있다.^[18]이 방법은 임베딩이 존재할 때 링크가 없거나 평평한 임베딩이 구성되지 않지만, 임베딩을 구성하는 알고리즘은 반 데어 홀스트(2009)에 의해 개발되었고, 보다 효율적인 선형 시간 알고리즘은 카와라바야시, 크뢰처 & 모하르(2010)에 의해 발견되었다.

링크리스 그래프에 대한 파리의 정리의 아날로그 가능성에 대한 삭스(1983)의 마지막 질문은 답하지 않은 것으로 보인다: 곡면 또는 조각처럼 선형의 가장자리를 가진 링크리스 또는 플랫 임베딩의 존재는 언제 가장자리가 직선 세그먼트인 링크리스 또는 플랫 임베딩의 존재를 암시하는가?

참고 항목

• 노트와 그래프

메모들

참조

추가 읽기