위키득계정 ↗
과학

평면 그래프

평면 그래프과학
영문명
Planar graph
조건
평면에 간선 교차 없이 표현 가능
교차 허용 위치
간선들이 공유하는 끝점
비교
평면 매장은 실제로 그린 표현
평면 그래프는 간선들이 끝점 이외의 곳에서 서로 교차하지 않도록 평면에 그릴 수 있는 그래프이다. 지금 그려진 그림에 교차가 있는지보다 교차 없이 그리는 방법이 존재하는지가 기준이다.

다르게 그릴 수 있는가

네 정점의 완전 그래프 K₄를 사각형과 두 대각선으로 그리면 교차가 보인다. 하지만 한 정점을 삼각형 안에 두어 다시 그리면 교차를 없앨 수 있다. 따라서 처음 그림의 교차만으로 비평면이라고 할 수 없다.

곡선도 사용할 수 있다

그래프를 표현할 때 간선을 반드시 처음 그린 직선 모양으로 고정하지 않는다. 정점 사이의 연결을 유지하며 선의 경로를 바꿀 수 있다. 대신 간선을 지우거나 새로운 정점을 넣어 다른 그래프로 바꾸는 것은 원래 그래프의 평면성을 증명하는 일이 아니다.

면의 구분

교차 없이 그린 그래프는 평면을 여러 영역으로 나눈다. 이때 바깥쪽의 무한한 영역도 하나의 면으로 센다. 면은 추상적인 그래프의 연결 정보와 그 평면 표현을 함께 놓고 다룬다.

연결성과 별개의 조건

그래프가 연결되어 있다고 언제나 평면인 것은 아니며 분리된 여러 부분으로 이루어져도 각각을 교차 없이 그릴 수 있다. 연결성은 경로 존재를, 평면성은 교차 없는 표현 가능성을 묻는다.

관련 문서

완전 그래프 / 연결 그래프 / 간선 (그래프 이론) / 정점 (그래프 이론) / 오일러 공식 (그래프 이론) / 단순 그래프