평면 그래프 검사기

쿠라토프스키 정리를 사용하여 그래프가 평면 그래프(간선 교차 없이 그릴 수 있는지)인지 확인합니다. K5 및 K3,3 세분화를 탐지하고, 오일러 부등식 m ≤ 3n − 6을 검증하며, 그래프가 비평면인 경우 금지된 마이너를 시각적으로 표시합니다.

평면 그래프 검사기

Embed 평면 그래프 검사기 Widget

평면 그래프 검사기 정보

평면 그래프 검사기는 단순 무방향 그래프가 평면인지(어떤 두 간선도 교차하지 않고 평면에 그릴 수 있는지) 판별하며, 테스트에 실패할 경우 Kuratowski 증거(K₅ 또는 K₃,₃의 세분화)를 찾아 시각화합니다. 이 도구는 교육, 알고리즘 문제 해결 연습 및 소형 그래프 구조의 무결성 확인을 위해 제작되었습니다.

"평면(Planar)"이란 무엇인가요?

그래프 G = (V, E)가 평면이라는 것은 간선이 공유된 끝점에서만 만나도록 평면에 임베딩할 수 있음을 의미합니다. 마찬가지로, G를 구의 표면에 교차 없이 그릴 수 있는 경우에도 평면입니다. 평면성은 순수한 위상적 속성입니다. 그래프를 그리는 방식에 관계없이 어떤 교차 없는 그림이 존재하는지 여부에 달려 있습니다.

평면 그래프는 도로 및 공공시설 네트워크, 인쇄 회로 기판(PCB) 라우팅, 플라톤 다면체의 간선 그래프, 다면체의 면 구조 등 어디에서나 나타납니다. 하지만 많은 "자연스러운" 그래프는 완고하게 비평면입니다. 3개의 집에 3개의 설비를 교차 없이 연결하려고 할 때마다 K₃,₃ 장벽에 부딪히게 됩니다.

Kuratowski의 정리 — 검사기의 핵심

1930년 Kazimierz Kuratowski는 평면성에 순수한 조합적 특징이 있음을 입증했습니다.

유한 그래프가 평면이다 ⇔ K₅의 세분화와 K₃,₃의 세분화를 모두 포함하지 않는다.

그래프 H의 세분화(subdivision)는 H의 일부 간선을 내부 정점이 모두 새로운 차수 2 정점인 더 긴 경로로 교체하여 얻습니다. 따라서 Kuratowski의 정리에 따르면 K₅와 K₃,₃이 평면성을 가로막는 유일한 장애물이며, 모든 비평면 그래프는 "늘어난" 형태의 이들 중 하나를 포함하고 있습니다.

금지된 그래프

그래프	정점	간선	구조	평면 여부
K₅	5	10	모든 정점 쌍이 간선으로 연결됨 (완전 그래프).	아니요
K₃,₃	6	9	두 트리플 A와 B; 모든 a ∈ A가 모든 b ∈ B에 연결됨.	아니요
K₄	4	6	4개 정점의 완전 그래프.	예
K₂,₃	5	6	완전 이분 그래프 2 × 3.	예

Euler의 공식과 빠른 필요 조건

비교적 비용이 많이 드는 세분화 검색을 실행하기 전에, 검사기는 Euler의 공식에서 도출된 두 가지 빠른 필요 조건을 적용합니다. V개의 정점, E개의 간선, F개의 면(외부 면 포함)을 가진 평면 연결 그래프의 경우 다음이 성립합니다.

V − E + F = 2 (연결된 평면 그래프에 대한 Euler의 공식) V − E + F = 1 + c (c개의 연결 성분을 가진 평면 그래프의 경우)

단순 평면 그래프의 모든 면은 경계에 최소 3개의 간선을 가진다는 관찰과 결합하면 다음과 같은 간선의 상한선을 얻을 수 있습니다.

m ≤ 3n − 6 (단순 평면, n ≥ 3) m ≤ 2n − 4 (이분 단순 평면, n ≥ 3)

이 부등식을 위반하는 그래프는 세분화 검색 없이 즉시 비평면으로 간주됩니다. K₅는 m = 10, n = 5 ⇒ 3n − 6 = 9이므로 10 > 9로 경계를 위반합니다. K₃,₃는 m = 9, n = 6 ⇒ 2n − 4 = 8이므로 9 > 8로 이분 경계를 위반합니다.

세분화 검색 작동 방식

Euler 확인 후, 검사기는 세분화를 직접 검색합니다.

빠른 감지 — K₅ 또는 K₃,₃을 리터럴 부분 그래프로 감지. 5개의 정점이 쌍으로 인접하면 바로 K₅입니다. 6개의 정점이 3+3으로 나뉘어 9개의 교차 간선이 모두 존재하면 K₃,₃입니다.
K₅ 세분화 검색. G에서 차수가 4 이상인 5개의 "분기" 정점 후보 집합 각각에 대해, 분기 쌍당 하나씩 총 10개의 경로를 찾습니다. 이 경로들은 내부적으로 정점 불연속(분기가 아닌 정점이 두 개 이상의 경로에 나타나지 않음)이어야 하며 다른 분기를 내부 정점으로 사용하지 않아야 합니다. 발견되면 비평면성이 입증됩니다.
K₃,₃ 세분화 검색. 6개의 분기(차수 3 이상)와 3+3 이분 구조를 선택합니다. 동일한 내부 불연속 요구 사항을 가진 9개의 교차 쌍 경로를 검색합니다.
증거 없음 ⇒ 평면. 크기 제한 내에서 세분화가 발견되지 않으면 Kuratowski의 정리에 따라 그래프는 평면임이 보장됩니다.

정점 불연속 경로를 찾는 것은 일반적으로 NP-어려운 문제이므로, 검사기는 제한된 무작위 그리디 검색을 사용합니다. 각 반복마다 필요한 쌍을 난이도 순으로 정렬하고, 무작위 BFS를 사용하여 가장 어려운 쌍의 경로를 먼저 선택한 후 해당 내부 정점을 제거하고 계속합니다. 특정 순서가 실패하면 셔플된 순서로 다시 시도합니다(분기 구성당 최대 40회 시도). 테스트된 모든 소형 그래프(최대 16개 정점)에서 이는 증거가 존재할 때마다 이를 찾아내기에 충분합니다.

이 계산기 사용 방법

상단의 탭을 사용하여 입력 형식(간선 리스트 또는 인접 리스트)을 선택합니다. 두 형식 모두 동일한 그래프를 인코딩합니다.
그래프를 입력합니다. 그래프는 무방향으로 처리되므로 A-B와 B-A는 동일한 간선입니다.
평면성 확인을 클릭합니다. 도구가 판정 결과를 보고하고, 단계별 추론(Euler, 이분성, Kuratowski)을 보여주며 그래프를 렌더링합니다.
비평면 그래프의 경우 시각화에 K₅ 또는 K₃,₃ 세분화가 색상으로 표시되고 10개(또는 9개)의 정점 불연속 경로가 나열됩니다. 경로 행을 클릭하여 강조 표시할 수 있습니다.
평면 그래프의 경우 그래프 구조와 함께 면 수 F = m − n + 1 + c가 보고됩니다.

실행 예시 1 — K₄는 평면입니다

K₄는 n = 4, m = 6입니다. 정점 4개 이하의 모든 그래프는 평면이며, 실제로 K₄는 세 모서리에 모두 연결된 하나의 내부 정점이 있는 삼각형으로 임베딩됩니다. Euler 공식에 따르면 면은 F = 6 − 4 + 2 = 4개(세 개의 삼각형 내부 면과 외부 면 하나)입니다.

실행 예시 2 — K₃,₃은 비평면입니다

K₃,₃은 n = 6, m = 9입니다. 이분 그래프이므로 이분 경계가 적용됩니다: m = 9 > 2n − 4 = 8. 이것만으로도 비평면성이 입증됩니다. 증거는 명확합니다 — K₃,₃ 자체가 금지된 부분 그래프입니다. 도구는 3+3 분할과 9개의 직접 간선을 강조 표시합니다.

실행 예시 3 — Petersen 그래프

Petersen 그래프는 n = 10, m = 15이므로 m ≤ 3n − 6 = 24가 되어 Euler 확인을 통과합니다. 하지만 이 그래프는 비평면으로 매우 유명합니다. 검사기는 K₃,₃ 세분화를 찾아냅니다. 외부 오각형과 내부 오각형에서 6개의 정점을 선택하여 모든 교차 쌍이 나머지 4개의 정점을 통해 정점 불연속 경로로 라우팅될 수 있도록 합니다. 도구는 이 증거를 그려 1930년대의 기하학을 실감나게 보여줍니다.

평면성의 응용

VLSI 및 PCB 라우팅. 단일 레이어 회로는 연결 그래프가 평면인 경우에만 가능합니다. 비평면 네트워크는 비아(via) 또는 추가 레이어를 강제합니다.
그래프 그리기 및 시각화. 평면 그래프는 교차 없는 명확한 레이아웃을 허용하여 지하철 노선도, 호출 그래프 및 도식도에 유용합니다.
알고리즘 설계. 많은 NP-어려운 문제(최대 컷, 정점 커버, 그래프 동형성)가 평면 그래프로 제한될 때 다항식 시간 내에 해결 가능해집니다.
그래프 채색. 4색 정리는 모든 평면 그래프가 4가지 색으로 채색 가능함을 보장합니다. 이는 평면성에 기초한 고전적인 결과입니다.
조합 최적화. 평면 최단 경로, 최대 유량 및 최소 컷은 모두 특화된 빠른 알고리즘을 가집니다.
분자 화학. 벤젠 고리 방향족 탄화수소 그래프는 평면입니다. 특정 케이지 분자는 그렇지 않습니다.

자주 묻는 질문

그래프에서 평면이란 무엇을 의미하나요?

그래프가 평면이라는 것은 공유된 정점 이외의 어떤 두 간선도 서로 교차하지 않도록 평면에 그릴 수 있음을 의미합니다. 마찬가지로, 교차 없이 구의 표면에 그릴 수 있는 경우에만 그래프는 평면입니다. 트리, 사이클, 정육면체 그래프 및 플라톤의 다면체는 모두 평면이며, K₅와 K₃,₃은 대표적인 비평면 예시입니다.

Kuratowski의 정리란 무엇인가요?

Kuratowski의 정리에 따르면, 유한 그래프가 평면일 조건은 K₅ 또는 K₃,₃의 세분화인 부분 그래프를 포함하지 않는 것입니다. 세분화는 일부 간선을 더 긴 경로로 교체하여 얻으며, 각각은 새로운 차수 2 정점을 통과합니다. 이는 비평면성에 대한 구체적인 조합적 증명을 제공합니다.

K5와 K3,3의 차이점은 무엇인가요?

K₅는 5개의 정점을 가지며, 모든 정점 쌍이 간선으로 연결되어 총 10개의 간선을 가집니다. K₃,₃은 6개의 정점이 3개씩 두 그룹으로 나뉘어 있으며, 한 그룹의 모든 정점이 다른 그룹의 모든 정점과 연결되어 총 9개의 간선을 가집니다. 둘 다 해당 종류 중 가장 작은 비평면 그래프이며, 함께 평면성을 가로막는 금지된 마이너를 형성합니다.

Euler의 부등식이 어떻게 도움이 되나요?

평면 연결 그래프에 대한 Euler의 공식 V − E + F = 2와 단순 평면 그래프의 모든 면이 최소 3개의 간선을 가진다는 사실을 결합하면 m ≤ 3n − 6이 도출됩니다. 이 경계를 위반하는 모든 단순 그래프는 즉시 비평면입니다. 이분 평면 그래프의 경우 모든 면이 최소 4개의 간선을 가져 더 엄격한 경계인 m ≤ 2n − 4가 적용됩니다. 검사기는 이 두 가지를 빠른 거부 규칙으로 적용합니다.

크기 제한은 어떻게 되나요?

이 검사기는 최대 16개의 정점과 60개의 간선을 처리할 수 있습니다. 이는 Petersen 그래프, Möbius-Kantor 그래프, 소형 하이퍼큐브 및 완전 그래프 K₇을 포함한 일반적인 교육 및 대회용 그래프를 다룹니다. 더 큰 그래프는 Hopcroft-Tarjan 또는 left-right 평면성 테스트와 같은 선형 시간 전용 평면성 테스트가 필요합니다.

증거 세분화는 어떻게 그려지나요?

그래프가 비평면인 경우, 발견된 K₅의 5개 분기 정점 또는 두 개의 트리플 A와 B로 나뉜 K₃,₃의 6개 분기 정점이 내부 링에 강조되어 표시됩니다. 필요한 10개(또는 9개)의 내부 정점 불연속 경로는 각각 고유한 색상으로 그려져 K₅ 또는 K₃,₃ 토폴로지를 시각적으로 추적할 수 있습니다. 세분화의 일부가 아닌 정점과 간선은 흐리게 표시됩니다.