[이산수학]꼭짓점, 변, 면과의 관계는? (오일러 공식에 대한 정리, v-e+s=2)

오일러 공식에 대한 정리

 

연결된 평면 그래프 G에서 꼭짓점 수를 v, 변의 수를 e, 면의 수를 s라고 할 때 다음 오일러 공식이 성립합니다. 

v - e + s = 2

 

증명

위의 공식을 증명하기 위해서는 변이 하나인 그래프와 둘 이상인 그래프를 나누어 고려해야 한다. 

 

(1) 변이 하나인 그래프는 다음과 같이 두 종류이다.

 

1) v = 1, e = 1. s = 2 로 v - e + s = 1 - 1 + 2 = 2

∴ 오일러 공식이 성립한다. 

 

2) v = 2, e = 1. s = 1 로 v - e + s = 2 - 1 + 1 = 2

∴ 오일러 공식이 성립한다. 

 

(2) 둘 이상의 변으로 구성된 그래프는 수학적 귀납법을 이용해 증명한다.

 

e = 1일 때, v - e + s = 2 - 1 + 1 = 2므로 오일러 공식이 성립한다.  e = k일 때, v - k + s = 2로 오일러 공식이 성립한다고 가정하고, e = k +1 일 때 오일러 공식이 성립하는지 증명한다. e = k인 그래프에서 변을 추가해서 ( e = k +1 ) 얻는 평면 그래프는 다음과 같이 두 가지 경우가 있다. 

 

(v + 1) - (k + 1) + s = v + 1 - k - 1 + s = v - k + s = 2 (∵ 귀납 가정이 성립)

∴ 오일러 공식이 성립한다. 

 

v - (k +1) + (s + 1) = v - k - 1 + s +1

v - k + s = 2 (∵ 귀납 가정이 성립)

∴ 오일러 공식이 성립한다. 

수학으로 이해하는 디지털 논리 이산수학 312p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------