평면그래프, 필수예제 40

[원보이]

(1) 연결, 단순, 평면 그래프일때 오일러공식 v-e+f=2 가성립하는데 K5같은 평면그래프가아닌 그래프에서 면의 개수를 정의할수있을가요?

(2) 평면그래프가 아님을 보이는문제는 오일러공식이나 e≤3v-6 , 쿠라토프스키 정리 등을 사용하여 보이는데 그래프가 평면그래프임을 보이는 방법이 따로있을가요?

(3) 필수예제 40번에서 변의값의 합이 최소인 생성수형도를 구하는방법은 나와있는데  같은 그래프에서 점A에서 시작하여 점L을끝으로하는 경로의 변의값이 최소가 되게하는 경로를 찾는방법도 있을가요? 

[박정환]

1. 평면그래프에서 면을 정의합니다.
2. 쿠라토프스키 정리 대우로 생각해줄 수도 있겠지만, 딱히 좋은 방법이라고 생각은 안 들구요.
제가 아는 선에선 정의 만족하는지 변이 교차하지 않도록 평면에 그려주시면 됩니다.
3. 특별한 방법이 있는지는 저도 잘 모르겠습니다. 결국 경우의 수를 다 따져줘야 하지 않을까요.