📂그래프이론

악수 딜레마 증명

정리 ¹

임의의 유향 그래프에서, 입력 차수의 합과 출력 차수의 합은 같다.

설명

악수 딜레마는 유향 그래프에서의 악수 렘마라고 할 수 있다.

증명

유향 그래프에서 출력 차수의 합은 아크의 수와 같다. 아크는 하나의 버텍스에서 나오고 하나의 버텍스로 들어가므로, 출력 차수와 입력 차수의 합은 같다.

■