핸드셰이킹 이론을 정도 정리(Sum of Degree 정리) 또는 핸드셰이킹 보조정리(Handshaking Lemma)라고 부를 수도 있습니다. 핸드셰이킹 이론에 따르면 그래프의 모든 정점의 차수의 합은 해당 그래프에 포함된 가장자리 수의 두 배가 됩니다. 핸드셰이킹 이론의 상징적 표현은 다음과 같이 설명됩니다.
여기,
'd'는 정점의 정도를 나타내는 데 사용됩니다.
'v'는 꼭지점을 나타내는 데 사용됩니다.
'e'는 모서리를 나타내는 데 사용됩니다.
핸드쉐이킹 정리:
핸드셰이킹 정리에는 다음과 같이 도출되어야 하는 몇 가지 결론이 있습니다.
모든 그래프에서:
- 모든 정점의 차수의 합은 짝수여야 합니다.
- 모든 정점의 차수가 홀수이면 이러한 정점의 차수의 합은 항상 짝수로 유지되어야 합니다.
- 홀수 차수를 갖는 정점이 있는 경우 이러한 정점의 개수는 짝수입니다.
핸드셰이킹 이론의 예
핸드셰이킹 이론에는 다양한 예가 있으며, 그 중 일부 예는 다음과 같습니다.
예시 1: 여기에 각 꼭지점의 각도가 4개 및 24개 모서리인 그래프가 있습니다. 이제 이 그래프의 정점 수를 알아 보겠습니다.
해결책: 위의 그래프를 통해 다음과 같은 세부 정보를 얻었습니다.
각 정점의 차수 = 24
모서리 수 = 24
이제 정점 수 = n이라고 가정하겠습니다.
Handshaking 정리를 사용하면 다음과 같은 내용을 얻을 수 있습니다.
모든 정점의 차수 합 = 2 * 가장자리 수
이제 위의 핸드셰이킹 공식에 주어진 값을 입력하겠습니다.
메이븐 저장소
n*4 = 2*24
n = 2*6
n = 12
따라서 그래프 G에서 꼭지점 수 = 12입니다.
예시 2: 여기에는 21개의 모서리, 4차 꼭짓점 3개, 2차 꼭짓점의 다른 모든 꼭짓점이 있는 그래프가 있습니다. 이제 이 그래프의 총 꼭짓점 수를 알아 보겠습니다.
해결책: 위의 그래프를 통해 다음과 같은 세부 정보를 얻었습니다.
4차 정점 수 = 3
모서리 수 = 21
다른 모든 꼭짓점은 2차를 갖습니다.
이제 정점 수 = n이라고 가정하겠습니다.
Handshaking 정리를 사용하면 다음과 같은 내용을 얻을 수 있습니다.
모든 정점의 차수 합 = 2 * 가장자리 수
이제 위의 핸드셰이킹 공식에 주어진 값을 입력하겠습니다.
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
따라서 그래프 G에서 총 정점 수 = 18입니다.
예시 3: 여기에 35개의 모서리, 5차 꼭짓점 4개, 4차 꼭짓점 5개, 3차 꼭짓점 4개가 있는 그래프가 있습니다. 이제 이 그래프에서 2차 꼭짓점의 수를 알아 보겠습니다.
해결책: 위의 그래프를 통해 다음과 같은 세부 정보를 얻었습니다.
모서리 수 = 35
5차 꼭지점 수 = 4
4차 정점 수 = 5
3차 정점 수 = 4
이제 2차 꼭짓점의 수 = n이라고 가정하겠습니다.
Handshaking 정리를 사용하면 다음과 같은 내용을 얻을 수 있습니다.
모든 정점의 차수 합 = 2 * 가장자리 수
이제 위의 핸드셰이킹 공식에 주어진 값을 입력하겠습니다.
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
따라서 그래프 G에서 2차 정점의 수 = 9입니다.
예시 4: 여기에 24개의 모서리가 있는 그래프가 있고 각 꼭지점의 차수는 k입니다. 이제 주어진 옵션에서 가능한 정점 수를 알아 보겠습니다.
- 열 다섯
- 이십
- 8
- 10
해결책: 위의 그래프를 통해 다음과 같은 세부 정보를 얻었습니다.
모서리 수 = 24
각 정점의 차수 = k
이제 정점 수 = n이라고 가정하겠습니다.
Handshaking 정리를 사용하면 다음과 같은 내용을 얻을 수 있습니다.
모든 정점의 차수 합 = 2 * 가장자리 수
이제 위의 핸드셰이킹 공식에 주어진 값을 입력하겠습니다.
N*k = 2*24
K = 48/약
모든 정점의 차수에는 정수가 포함되어야 합니다.
따라서 위의 방정식에서는 전체 k 값을 제공하는 n 값 유형만 사용할 수 있습니다.
이제 위에서 주어진 옵션을 다음과 같이 n 자리에 하나씩 배치하여 확인하겠습니다.
- n = 15인 경우 k = 3.2가 되며 이는 정수가 아닙니다.
- n = 20인 경우 k = 2.4를 얻게 되며 이는 정수가 아닙니다.
- n = 8인 경우 k = 6(정수)을 얻게 되며 이는 허용됩니다.
- n = 10인 경우 k = 4.8이 되며 이는 정수가 아닙니다.
따라서 올바른 옵션은 옵션 C입니다.