평면 그래프

그래프 예시
평면	평면이 아닌
나비 그래프	완전한 그래프 K5
완전한 그래프 K4	유틸리티 그래프 K3,3

그래프 이론에서 평면 그래프는 평면에 포함될 수 있는 그래프이다. 즉, 평면의 가장자리가 끝점에서만 교차하도록 평면에 그릴 수 있다.즉, 모서리가 ^[1][2]서로 교차하지 않도록 그릴 수 있습니다.이러한 도면을 평면 그래프 또는 그래프의 평면 매립이라고 합니다.평면 그래프는 각 곡선의 극점이 그 끝 노드로부터 매핑되고 그 극점을 제외한 모든 곡선이 분리되도록 평면상의 모든 노드에서 평면상의 점으로 매핑되는 평면 그래프로 정의할 수 있다.

평면상에 그릴 수 있는 모든 그래프는 입체 투영을 통해 구면에 그릴 수도 있고 반대로 그릴 수도 있습니다.

평면 그래프는 조합 지도 또는 회전 시스템으로 인코딩할 수 있습니다.

일반적으로 동공이 존재하지 않는 것과 같은 추가 가정을 수반하는 구상의 위상적으로 동등한 도면의 등가 클래스를 평면도라고 합니다.평면 그래프에는 외부 면 또는 경계 없는 면이 있지만 평면 맵의 면에는 특정 상태가 없습니다.

평면 그래프는 주어진 속 표면에 그릴 수 있는 그래프로 일반화한다.이 용어에서 평면 그래프(및 구)는 0속 표면이기 때문에 평면 그래프는 0속이다.기타 관련 항목은 "그래프 삽입"을 참조하십시오.

평면성 기준

쿠라토프스키와 바그너의 이론

폴란드의 수학자 카지미에츠 쿠라토프스키(Kazimierz Kuratowski)는 현재 쿠라토프스키의 정리로 알려진 금지된 그래프에 대한 평면 그래프의 특성화를 제공했다.

유한 그래프는 완전한 그래프₅ K 또는 완전한 초당 그래프_3,3 K(유틸리티 그래프)의 하위 분할인 서브 그래프가 없는 경우에만 평면적이다.

그래프의 하위 분할은 모서리에 정점을 삽입하는 경우(예를 들어 모서리 변경 등)를 0회 이상 반복하여 발생합니다.

세분화를 고려하는 대신 바그너의 정리는 미성년자를 다룬다.

유한 그래프는 마이너로서 K_3,3 또는 K가 없는₅ 경우에만 평면 그래프입니다.

그래프의 마이너는 서브그래프를 가져다가 모서리를 정점으로 반복적으로 수축시켜 원래 엔드버티스의 각 네이버가 새로운 정점의 네이버가 되는 것으로부터 비롯된다.

클라우스 바그너는 보다 일반적으로 "금지된 미성년자"의 유한 집합에 의해 마이너 클로즈드된 그래프 클래스가 결정되는지 물었다.지금은 로버트슨 가족입니다시모어 정리, 일련의 긴 논문에서 증명되었죠.이 정리의 언어에서, K와_3,3 K는 유한₅ 평면 그래프의 클래스에 대해 금지된 마이너이다.

기타 기준

실제로, 주어진 그래프가 평면인지 여부를 신속하게 결정하기 위해 쿠라토스키의 기준을 사용하는 것은 어렵다.단, 이 문제에는 고속 알고리즘이 존재합니다.정점이 n개인 그래프의 경우 그래프가 평면인지 아닌지를 시간 O(n)(선형 시간)로 판단할 수 있습니다(평면성 테스트 참조).

v 꼭지점과 e 모서리 및 f 면이 있는 단순하고 연결된 평면 그래프의 경우 다음과 같은 간단한 조건은 v † 3에 대해 유지됩니다.

• 정리 1. e 3 3v – 6;
• 정리 2길이가 3인 사이클이 없는 경우 e v 2v – 4입니다.
• 정리 3. f 2 2v – 4

이러한 의미에서 평면 그래프는 최대 O(v²)보다 점근적으로 작은 O(v) 에지만을 가지고 있다는 점에서 희박한 그래프이다.예를 들어 그래프_3,3 K에는 6개의 꼭지점과 9개의 모서리가 있으며 길이가 3인 주기가 없습니다.그러므로, 정리 2에 의해, 그것은 평면이 될 수 없다.이러한 정리는 충분한 조건이 아닌 평면에 필요한 조건을 제공하므로 그래프가 평면이 아닌 것을 증명하는 데만 사용할 수 있다.정리 1과 2가 모두 실패하면 다른 방법을 사용할 수 있다.

• 휘트니의 평면성 기준은 대수적 이중의 존재에 기초한 특성화를 제공한다.
• 맥 레인의 평면성 기준은 주기 공간을 통해 유한 평면 그래프의 대수적 특성을 제공한다.
• Fraysseix-Rosenstiehl 평탄성 기준은 깊이 우선 탐색 나무의 코트리 가장자리의 초당적 존재에 기초한 특성화를 제공한다.이는 좌우 평탄도 테스트 알고리즘의 중심이다.
• 슈나이더의 정리는 부분 순서 차원에 관한 평면성의 특성을 제공한다.
• Colin de Verdiér의 평면성 기준은 그래프에 의해 정의된 특정 슈뢰딩거 연산자의 두 번째 고유값의 최대 다중성에 기초한 특성을 부여한다.
• 하나니족Tutte 정리는 그래프가 각각의 독립적인 모서리 쌍이 짝수 횟수로 교차하는 도면을 가지고 있는 경우에만 평면이라고 말한다. 그래프는 방정식 모듈로 2의 시스템을 통해 평면 그래프를 특징짓는 데 사용될 수 있다.

특성.

오일러 공식

오일러의 공식은 만약 유한하고 연결된 평면 그래프가 모서리 교차점 없이 평면에 그려지고, v는 정점의 수이고, e는 모서리의 수이고 f는 면의 수이다.

${\displaystyle v-e+f=2.}$

위의 나비 그래프에서 예시로 v = 5, e = 6, f = 3입니다.일반적으로 f면의 모든 평면 그래프에 대해 특성이 유지된다면, 그래프를 평면 상태로 유지하면서 추가 면을 생성하는 그래프의 변경은 v – e + f를 불변으로 유지할 것이다.속성은 f = 2인 모든 그래프에 적용되므로 수학적 귀납에 의해 모든 경우에 적용된다.오일러의 공식은 또한 다음과 같이 증명될 수 있다: 그래프가 나무가 아니라면, 순환을 완성하는 가장자리를 제거하라.그러면 e와 f가 모두 1개씩 낮아지고 v – e + f는 일정하게 유지됩니다.나머지 그래프가 나무일 때까지 반복한다. 나무는 v = e + 1과 f = 1을 가지며 v – e + f = 2를 산출한다. 즉, 오일러 특성은 2이다.

유한하고, 연결된 단순 평면 그래프에서, 모든 면(외부 면 제외)은 적어도 세 개의 모서리에 의해 경계되며, 모든 면은 최대 두 개의 면에 닿는다. 오일러의 공식을 사용하면, 이러한 그래프가 v ≤ 3일 경우, 다음과 같은 점에서 희박하다는 것을 보여줄 수 있다.

$(\displaystyle e\leq 3v-6)$

오일러의 공식은 볼록 다면체에도 유효하다.이것은 우연이 아닙니다. 모든 볼록한 다면체는 다면체의 슐레겔 도표를 사용하여 연결된 단순 평면 그래프로 변할 수 있습니다. 다면체의 원근 투시 투영을 다면체 면의 중심 부근에서 선택한 원근 투시 투영입니다.모든 평면 그래프가 볼록 다면체에 대응하는 것은 아닙니다.예를 들어 나무는 그렇지 않습니다.슈타이니츠의 정리는 볼록 다면체로 형성된 다면체 그래프가 정확히 유한 3연결 단순 평면 그래프라고 말한다.보다 일반적으로, 오일러의 공식은 볼록성과 상관없이, 면이 구와 위상적으로 동등한 표면을 형성하는 단순한 다면체인 모든 다면체에 적용된다.

평균도

둘 이상의 모서리를 가진 연결된 평면 그래프는 각 면에는 최소 3개의 면 모서리 발생이 있고 각 모서리는 정확히 2개의 발생을 기여하기 때문에 2e 3 3f를 따른다.따라서 오일러의 공식 v – e + f = 2와 같은 부등식의 대수적 변환을 통해 유한 평면 그래프에 대한 평균 차수는 엄밀하게 6보다 작다. 평균 차수가 높은 그래프는 평면적일 수 없다.

코인 그래프

평면상에 그려진 두 개의 원이 정확히 한 점에서 교차할 때마다 키스(또는 오스코스)한다고 합니다."코인 그래프"는 각 원에 대해 정점을 만들고 키스하는 각 원에 대해 모서리를 만들어 겹치는 내부가 없는 원의 집합으로 구성된 그래프입니다.1936년 Paul Koebe에 의해 처음 증명된 원 채우기 정리는 그래프가 동전 그래프일 경우에만 평면이라고 말한다.

이 결과는 모든 단순한 평면 그래프가 서로 교차하지 않는 직선 세그먼트가 되도록 평면에 삽입될 수 있다는 파리의 정리를 쉽게 증명합니다.코인 그래프 표현에서 그래프의 각 정점을 대응하는 원의 중심에 배치하면 키스 원의 중심 사이의 선분은 다른 가장자리 중 어느 쪽에도 교차하지 않는다.

평면 그래프 밀도

평면 그래프 또는 네트워크의 망사 계수 또는 밀도 D는 v 정점이 있는 그래프에 대해 가능한 최대값 2v – 5에 의한 (맥 레인 평탄도 기준에 의한 그래프의 회로 순위와 동일) 경계 면의 수 f – 1의 비율이다.

${\displaystyle D=black {f-1}{2v-5}}$

농도는 0 ≤ D 1 1에 따르며, 완전 희박한 평면 그래프(^[3]트리)의 경우 D = 0, 완전 조밀한 평면 그래프(수평)의 경우 D = 1이다.

이중 그래프

모서리 교차점이 없는 평면에 연결된 그래프의 내장 G가 주어지면, 우리는 다음과 같이 이중 그래프 G*를 구성한다: 우리는 G의 각 면(외부 면 포함)에서 하나의 정점을 선택하고, G의 각 모서리에 대해 G*의 두 정점에 대응하는 G*의 두 정점을 연결하는 새로운 에지를 도입한다.또한 이 에지는 e와 정확히 한 번 교차하고 G 또는 G*의 다른 에지는 교차하지 않도록 그려집니다.그리고 G*는 다시 (꼭 간단하지는 않은) 평면 그래프의 삽입입니다. G는 면 수만큼, G는 면 수만큼, 그리고 G는 정점 수만큼 모서리를 가집니다.용어 "deturn"은 G** = G라는 사실로 정당화된다. 여기서 등식은 구에 내장되는 것의 등가성이다.G가 볼록 다면체에 대응하는 평면 그래프라면 G*는 이중 다면체에 대응하는 평면 그래프이다.

듀얼은 듀얼 그래프의 많은 속성이 원래 그래프의 속성과 간단한 방식으로 관련되므로 듀얼 그래프를 검토하여 그래프에 대한 결과를 증명할 수 있으므로 유용합니다.

특정 임베딩에 대해 구성된 이중은 고유하지만(이형까지), 그래프는 다른(즉, 동형적이지 않은) 임베딩에서 얻은 서로 다른(즉, 동형적이지 않은) 이중을 가질 수 있다.

평면 그래프 패밀리

최대 평면 그래프

단순한 그래프는 평면인 경우 최대 평면이라고 불리지만 주어진 정점 집합에 모서리를 더하면 해당 특성이 파괴됩니다.그런 다음 모든 면(외부 면 포함)이 세 개의 모서리에 의해 경계되어 대체 항 평면 삼각 측량을 설명합니다."삼각형 그래프"^[4] 또는 "삼각형 그래프"^[5]라는 대체 이름도 사용되었지만, 일반적으로 완전한 그래프의 선 그래프와 화음 그래프를 각각 지칭하기 때문에 모호합니다.모든 최대 평면 그래프는 최소 3개의 연결 그래프입니다.

최대 평면 그래프에 v > 2의 정점이 있는 경우, 정확히 3v – 6개의 모서리와 2v – 4개의 면이 있습니다.

아폴로 네트워크는 삼각형 면을 작은 삼각형의 3배로 반복적으로 분할하여 형성된 최대 평면 그래프입니다.마찬가지로, 그것들은 평면 3 트리입니다.

교살 그래프는 모든 주변 사이클이 삼각형인 그래프입니다.최대 평면 그래프(또는 더 일반적으로 다면체 그래프)에서 주변 사이클은 면이므로 최대 평면 그래프는 교살된다.교살된 그래프에는 화음 그래프도 포함되며, 완전한 그래프와 최대 평면 ^[6]그래프의 (가장자리를 삭제하지 않고) clique-sum으로 형성될 수 있는 그래프입니다.

외평면 그래프

외부 평면 그래프는 평면에 모든 정점이 포함의 무한 면에 속하도록 포함된 그래프입니다.모든 외부 평면 그래프는 평면이지만, 그 반대는 사실이 아니다: K는₄ 평면이지만 외부 평면은 아니다.쿠라토프스키의 이론과 유사한 정리는 유한 그래프가 K 또는₄ K의_2,3 하위분할을 포함하지 않는 경우에만 외평면이라고 말한다.위는 그래프 G가 다른 모든 정점과 연결되는 가장자리가 있는 새로운 정점을 추가함으로써 G에서 형성된 그래프가 평면 ^[7]그래프일 경우 그래프 G가 외부 평면이라는 사실에 대한 직접적인 결과이다.

그래프의 1-외측 평면 매립은 외측 평면 매립과 동일하다.k > 1의 경우, 외부 표면의 정점을 제거하면 (k – 1)-외측 평면 매립이 되는 경우 평면 매립은 k-외측 평면 매립이다.그래프가 k-outerplanar 내장되어 있는 경우 그래프는 k-outerplanar입니다.

할린 그래프

할린 그래프는 무방향 평면 트리(도 2노드 없음)에서 트리의 평면 매립에 의해 주어진 순서로 잎을 사이클로 접속함으로써 형성되는 그래프이다.마찬가지로, 한 면이 다른 면과 인접해 있는 다면체 그래프입니다.모든 할린 그래프는 평면이다.외평면 그래프와 마찬가지로 할린 그래프는 트리 폭이 낮기 때문에 무제한 ^[8]평면 그래프보다 많은 알고리즘 문제를 더 쉽게 해결할 수 있습니다.

위쪽 평면 그래프

상향 평면 그래프는 평면에 가장자리가 위쪽 방향으로 일관되게 교차하지 않는 곡선으로 그려질 수 있는 방향 비순환 그래프입니다.모든 평면 지향 비순환 그래프가 상향 평면인 것은 아니며, 주어진 그래프가 상향 평면인지 여부를 테스트하는 것은 NP-완전입니다.

볼록 평면 그래프

평면 그래프는 모든 면(외면 포함)이 볼록 다각형일 경우 볼록하다고 한다.모든 평면 그래프가 볼록 내장(예: 완전한 초당 그래프_2,4 K>)을 가지는 것은 아니다.그래프가 볼록하게 그려질 수 있는 충분한 조건은 3-vertex 연결 평면 그래프의 세분화이다.Tutte의 스프링 정리는 심지어 단순한 3-vertex 연결 평면 그래프의 경우 내부 정점의 위치가 이웃들의 평균이 되도록 선택될 수 있다고 말한다.

단어를 나타내는 평면 그래프

단어 표현 가능한 평면 그래프에는 삼각형 없는 평면 그래프와 더 일반적으로 3색 평면 ^[9]그래프뿐만 아니라 삼각 그리드 ^[10]그래프의 특정 면 분할 및 그리드 덮인 실린더 ^[11]그래프의 특정 삼각 측량도 포함된다.

정리

평면 그래프 열거

어디γ ≈ 27.22687{\displaystyle \gamma 27.22687 \approx}과 입수 ≈ 0.43× 10− 5{\displaystyle g\approx 0.43\times 10^{-5}}그(라벨)평면 그래프의 n{n\displaystyle}vertices에 그 번호를 점근은g⋅ n− 7/2⋅ γ n⋅ n!{\displaystyleg\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!},다 12.]

거의 모든 평면 그래프는 기하급수적인 ^[13]수의 자기동형을 가지고 있다.

n개의$$\$displaystyle$n개의$$ $정점$에 라벨이 부착되지 않은(비동형) 평면 그래프의 수는 27$\$${\displaystyle {27}^{}}$이다.$2^{n}$ 및$$ $.$30.06$^{n$^[14]

기타 결과

4색 정리는 모든 평면 그래프가 4색(즉, 4분할)임을 나타냅니다.

Farry의 정리는 모든 단순한 평면 그래프는 평면 직선 그래프로 표현될 수 있다고 말한다.유니버설 포인트 세트는 정점이 n개인 모든 평면 그래프가 점 세트 내의 모든 정점과 같은 삽입을 갖는 점 세트입니다.정수 격자의 직사각형 서브셋을 취함으로써 형성된 2차 크기의 유니버설 포인트 세트가 존재합니다.모든 단순한 외측 평면 그래프는 모든 정점이 고정된 원 위에 있고 모든 가장자리가 디스크 내부에 있고 교차하지 않는 직선 세그먼트이므로 n-vertex 정규 폴리곤은 외측 평면 그래프에 범용적입니다.

샤이너만의 추측(현재의 정리)은 모든 평면 그래프가 평면상의 선분들의 교차 그래프로 표현될 수 있다고 말한다.

평면 분리기 정리에 따르면 모든 n-vertex 평면 그래프는 O()n) 정점의 제거에 의해 최대 2n/3 크기의 두 개의 서브 그래프로 분할될 수 있습니다.그 결과 평면 그래프는 트리폭과 분기폭 O(θn)도 가진다.

평면 곱 구조 정리는 모든 평면 그래프는 최대 8의 나무 너비와 ^[15]경로의 그래프에 대한 강한 그래프 곱의 하위 그래프라고 말한다.이 결과는 평면 그래프에 경계 큐 번호, 경계 비반복 색수 및 근선형 크기의 범용 그래프가 있음을 보여주는 데 사용되었다.또한 평면 그래프의 정점^[16] 순위와 p-중심^[17] 색채에 적용된다.

정점이 v개인 두 개의 평면 그래프의 경우, 시간 O(v)에서 그것들이 동형인지 아닌지를 결정할 수 있다(그래프 동형성 ^[18]문제 참조).

일반화

정점 그래프는 하나의 정점을 제거함으로써 평면으로 만들 수 있는 그래프이고, k-apex 그래프는 최대 k개의 정점을 제거함으로써 평면으로 만들 수 있는 그래프입니다.

1-평면 그래프는 모서리당 최대 1개의 단순 교차가 있는 평면에 그릴 수 있는 그래프이고, k-평면 그래프는 모서리당 최대 k개의 단순 교차를 사용하여 그릴 수 있는 그래프입니다.

지도 그래프는 적어도 하나의 경계점을 공유할 때 2개의 영역을 접속함으로써 평면 내에서 최종적으로 다수의 단순접속된 내부접속영역 집합에서 형성되는 그래프이다.최대 3개의 영역이 한 점에서 만나면 평면 그래프가 되지만 4개 이상의 영역이 한 점에서 만나면 평면이 아닐 수 있습니다.

트로이덜 그래프는 토러스 위에 교차하지 않고 삽입할 수 있는 그래프입니다.보다 일반적으로 그래프의 속은 그래프를 포함할 수 있는 2차원 표면의 최소 속이다. 평면 그래프는 0속, 비평면 트로이덜 그래프는 1속이다.

어떠한 그래프도 교차하지 않고 3차원 공간에 삽입할 수 있다.그러나 평면 그래프의 3차원 아날로그는 링크 없는 매립형 그래프에 의해 제공되며, 그래프는 2개의 사이클이 위상적으로 서로 연결되어 있지 않은 방법으로 3차원 공간에 내장될 수 있다.Kuratowski와 Wagner가 평면 그래프를 마이너로서 K 또는_3,3 K를 포함하지₅ 않는 그래프로 특성화한 것과 유사하게, 링크 없는 임베디드 가능 그래프는 Petersen 계열의 7개 그래프 중 마이너로서 포함하지 않는 그래프로 특성화할 수 있다.외부 평면 그래프와 평면 그래프의 특성화와 유사하게, 최대 2개 또는 3개의 Colin de Verdiér 그래프 불변인 그래프로서 링크 없는 임베디드 그래프는 최대 4개의 Colin de Verdiér 불변인 그래프이다.

「 」를 참조해 주세요.

• 조합 맵 평면 그래프를 인코딩할 수 있는 조합 개체
• 평면화, 각 교차점을 새 정점으로 대체하여 교차점이 있는 도면에서 형성된 평면 그래프
• 두께(그래프 이론), 주어진 그래프의 가장자리를 분할할 수 있는 최소 평면 그래프 수
• 평면도를 평면에 삽입하는 것이 목적인 퍼즐 컴퓨터 게임인 Planarnity
• 새싹(게임)은 게임 플레이의 일부로 일정한 제약이 있는 평면 그래프를 구성하는 연필과 종이 게임입니다.
• 세 가지 유틸리티 문제, 인기 있는 퍼즐

메모들

레퍼런스

• 를 클릭합니다Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fundamenta Mathematicae (in French), 15: 271–283, doi:10.4064/fm-15-1-271-283.
• 를 클릭합니다Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen (in German), 114: 570–590, doi:10.1007/BF01594196, S2CID 123534907.
• 를 클릭합니다Boyer, John M.; Myrvold, Wendy J. (2005), "On the cutting edge: Simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10.7155/jgaa.00091.
• 를 클릭합니다McKay, Brendan; Brinkmann, Gunnar, A useful planar graph generator.
• . 그래프 그리기 특집호de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1029, arXiv:math/0610935, doi:10.1142/S0129054106004248, S2CID 40107560.
• 검사 베이더와 S.Sreshta, 평탄도 테스트를 위한 새로운 병렬 알고리즘, UNM-ECE Technical Report 03-002, 2003년 10월 1일.
• 를 클릭합니다Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X.

외부 링크

• Edge Addition Planarity Algorithm Source Code, version 1.0 : Boyer-Myrvold Planarity Algorithm 참조 구현용 프리 C 소스 코드.이 소스코드는 조합형 평면 임베더와 Kuratowski 서브그래프 아이솔레이터를 모두 제공합니다.무료 라이선스가 있는 오픈소스 프로젝트는 Edge Addition Planarity Algorithms, 현재 버전을 제공합니다.
• 그래프 알고리즘 라이브러리 및 에디터의 퍼블릭 실장 - 평탄도 테스트, 평탄도 임베더 및 Kuratowski 서브그래프 전시를 포함한 GPL 그래프 알고리즘 라이브러리.
• 선형 시간 평탄도 테스트, 임베딩, Kuratowski 하위 그래프 분리 및 직선 드로잉을 포함한 평면 그래프용 부스트 그래프 라이브러리 도구.
• 3 유틸리티 퍼즐과 평면 그래프
• NetLogo Planarity 모델 - NetLogo 버전의 John Tantalo 게임