그래프1 차수에 관해 생각해보기

동기

cf) 동일한 개념에 대해 강의안에만 있거나 교재에만 있는 내용(깊이)이 존재함. U - (A ∩ B) 가 있는 a∈A 혹은 b∈B 가 존재

아래 내용은 그 중 하나 

 

이산수학 강의안 제 9장 그래프(1) p19 노란박스에  

 

참고: 그래프에서 '차수가 홀수인 꼭지점의 수'는 짝수이다. 가  잘 안 와닿아서 나름 생각해봄.

 

 

 

기본개념

G = (V,E) v는 V의 원소 

차수(degree) = [deg(v)] = v에 인접한 변의 개수 

총차수(total degree) = [deg(G)] = G에 속한 모든 꼭지점의 차수의 합 

deg(v) = 2|E|

 

 

 

 

생각해보기 

그래프를 차수가 홀수인지 짝수인지로 구분했을 때, 3경우 나뉨 

 

1) 차수가 모두 짝수인 꼭지점만 있는 그래프

2)차수가 모두 홀수인 꼭지점만 있는 그래프 

3) 차수가 홀수와 짝수가 섞여있는 그래프 

 

아래문장은 위 3경우에 모두 해당됨. 

 

그래프에서 '차수가 홀수인 꼭지점의 수'는 짝수있다. 

 

변 하나에 꼭지점 두 개가 발생되는 한, 그래프 전체의 차수는 항상 짝수만 나올 수 밖에 없고, 공식 deg(v)= 2|E| 가 가능해짐. 

(꼭지점 하나에 루프가 하나 있을 경우, 그 그래프는 변 하나에 꼭지점이 두 개가 발생하진 않지만, 꼭짓점 입장에선 차수가 2n개씩 추가되는 것임.  

 

 

 

 

 

 

 

이렇게 공식? 을 일리있게 풀어 써봐도 막상 공식을 사용할 때는 맹목적으로 원리를 생각하지 않고 사용하게 되는게 문제임. 

논리적으로 정리가 안돼서 직관적으로 이해하지 못하는 것 같기도 함. 

 

 

 

 

 

참고: 방송통신대학교 이산수학과 이산수학 강의안