평면 그래프 검사기

평면 그래프 검사기 정보

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

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

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

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

Kuratowski의 정리 — 검사기의 핵심

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

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

금지된 그래프

Euler의 공식과 빠른 필요 조건

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

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

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

세분화 검색 작동 방식

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

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

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

이 계산기 사용 방법

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

더 읽어보기

• 평면 그래프(Planar graph) — Wikipedia
• Kuratowski의 정리 — Wikipedia
• 오일러 표수(Euler characteristic) — Wikipedia
• 피터슨 그래프(Petersen graph) — Wikipedia
• 바그너의 정리(Wagner's theorem, 마이너 버전) — Wikipedia