위키득계정 ↗
과학

오일러 공식 (그래프 이론)

오일러 공식 (그래프 이론)과학
식
V−E+F=2
기본 조건
유한, 연결, 평면 표현
V와 E
정점 수와 간선 수
F
바깥 영역을 포함한 면 수
그래프 이론의 오일러 공식은 유한한 연결 평면 그래프를 교차 없이 그렸을 때 정점 수 V, 간선 수 E, 면 수 F가 V−E+F=2를 만족한다는 관계이다. 면에는 바깥 영역도 포함한다.

삼각형의 계산

삼각형은 정점 3개, 간선 3개를 갖는다. 안쪽 영역과 바깥 영역을 더하면 면은 2개이므로 3−3+2=2이다. 안쪽만 세면 공식과 맞지 않는다.

트리의 경우

정점이 n개인 유한 트리는 간선이 n−1개이고 평면에 그리면 면이 바깥 영역 하나다. 따라서 n−(n−1)+1=2가 된다. 닫힌 고리가 없다고 면을 0개로 세지 않는다.

연결 조건을 확인한다

연결 성분이 여러 개인 그래프에는 같은 형태의 연결 공식 2를 그대로 쓰지 않는다. 평면에 그린 그래프의 성분 수가 c이면 V−E+F=1+c라는 일반화로 다룰 수 있다. 무엇을 하나의 면으로 세는지도 일관되게 유지해야 한다.

다른 오일러 공식과 구별한다

복소 지수함수의 e^(ix)=cos x+i sin x와는 다른 관계다. 여기서는 그래프의 평면 표현에서 정점과 간선, 면의 개수를 다룬다. 이름이 같아도 사용 대상과 조건을 구별한다.

관련 문서

평면 그래프 / 트리 (그래프 이론) / 연결 성분 / 연결 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론) / 순환 그래프