2010년부터 · 매월 200만 회 이상의 도구 사용을 지원합니다
2010년부터
Chrome에 추가

내 도구함

자동 모드

저장된 도구가 없습니다.

프리미엄 버전으로 업그레이드하기
관련 도구
해밀턴 경로 검사기 (Hamiltonian Path Checker)리포그램 체커직각도 검사기 (3-4-5 법칙)중국식 성별 예측기상표 분류 찾기
홈페이지 > 수학 관련 도구 > 고급 수학 연산 도구
 

평면 그래프 검사기

쿠라토프스키 정리를 이용해 그래프가 평면적, 즉 선 교차 없이 그릴 수 있는지 확인합니다. K5와 K3,3의 세분을 감지하고 오일러 부등식을 검증하며, 비평면 그래프일 경우 금지 마이너를 표시합니다.

무료로 사용가입 필요 없음즉시 결과 확인
평면 그래프 검사기지금 무료로 사용하기 ▼
빠른 예시:
K₄ (평면) 정육면체 Q₃ (평면) K₅ (비평면) K₃,₃ (비평면) Petersen (비평면) 인접 리스트 (K₄)
A-B, A B, A,B 형식을 지원하며, 인접 리스트의 경우 A: B, C 형식을 지원합니다. 간선은 무방향으로 처리됩니다. 정점 레이블은 문자, 숫자 또는 언더바를 사용할 수 있습니다. 제한: 정점 16개 및 간선 60개.

평면 그래프 검사기 위젯 삽입

평면 그래프 검사기 정보

평면 그래프 검사기는 단순 무방향 그래프가 평면인지(어떤 두 간선도 교차하지 않고 평면에 그릴 수 있는지) 판별하며, 테스트에 실패할 경우 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₅510모든 정점 쌍이 간선으로 연결됨 (완전 그래프).아니요
K₃,₃69두 트리플 A와 B; 모든 a ∈ A가 모든 b ∈ B에 연결됨.아니요
K₄464개 정점의 완전 그래프.예
K₂,₃56완전 이분 그래프 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 확인 후, 검사기는 세분화를 직접 검색합니다.

  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년대의 기하학을 실감나게 보여줍니다.

평면성의 응용

자주 묻는 질문

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

그래프가 평면이라는 것은 공유된 정점 이외의 어떤 두 간선도 서로 교차하지 않도록 평면에 그릴 수 있음을 의미합니다. 마찬가지로, 교차 없이 구의 표면에 그릴 수 있는 경우에만 그래프는 평면입니다. 트리, 사이클, 정육면체 그래프 및 플라톤의 다면체는 모두 평면이며, 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₃,₃ 토폴로지를 시각적으로 추적할 수 있습니다. 세분화의 일부가 아닌 정점과 간선은 흐리게 표시됩니다.

더 읽어보기

이 콘텐츠, 페이지 또는 도구를 다음과 같이 인용하세요:

"평면 그래프 검사기" - https://MiniWebtool.com/ko/평면-그래프-검사기/에서 MiniWebtool 인용, https://MiniWebtool.com/

miniwebtool 팀 제작. 업데이트: 2026년 4월 22일

개발자 API 사용 가능: 이 도구를 앱, 자동화, 에이전트에서 한 번의 JSON HTTP 요청으로 실행할 수 있습니다. API 문서 보기

또한 저희의 AI 수학 해결사 GPT를 사용하여 자연어 질문과 답변으로 수학 문제를 해결할 수 있습니다.

고급 수학 연산 도구:

인기·최신 도구:

Open Graph 검사기그래프 채색 계산기그래프 차수열 검증기모두 보기 →
홈페이지 > 수학 관련 도구 > 고급 수학 연산 도구 > 평면 그래프 검사기