[이산수학]그래프에서 차수란?(외차수, 내차수 구하는 예제 포함)

 

■ 차수(Degree)

꼭짓점 v에 근접하는 변의 수

홀수점(Odd Vertex): 차수가 홀수인 꼭짓점

짝수점(Even Vertex): 차수가 짝수인 꼭짓점

 

예제

 

 

풀이

더 보기를 클릭하세요

예제풀이

d(a) = 2

d(b) = 2

d(c) = 4

 

 

■ 외차수(Out-degree) / 내차수 (In-degree) 

방향 그래프에서 

-  외차수: 꼭짓점 v를 시작으로 하는 화살표의 수 [out - d(v)]

-  내차수: 꼭짓점 v를 끝으로 하는 화살표의 수 [in -  d(v)]

 

예제

 

풀이

더 보기를 클릭하세요

예제풀이

out - d(a) = 1

in - d(a) = 0

out - d(b) = 2

in - d(b) = 0

out - d(c) = 0

in - d(c) = 2

out - d(d) = 1 //루트

in - d(d) = 1

 

■ 그래프와 차수의 관계

차수는 꼭짓점에 근접하는 변의 수를 의미하므로, 꼭짓점의 차수를 알면 그래프를 구성하는 변의 수를 예상할 수 있습니다. 

 

 

그래프는 차수가 홀수인 꼭짓점의 수가 짝수 개 있어야만 성립합니다. 그래서 아래 그래프의 각 꼭짓점 차수는 2이므로 즉, 차수가 홀수인 꼭짓점은 0개이므로 짝수 개입니다. 

 

차수에 대한 정리

(1) 그래프 G = (V, E)에서 모든 꼭지섬의 차수의 합은 변 수의 두 배다. 

(2) 그래프 G = (V, E)에서 차수가 홀수인 꼭짓점의 수는 짝수다. 

 

 

 

 

 

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

이산수학 총정리

목록 보러가기 

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