[이산수학]오일러 그래프 정의와 정리(예제포함)

 

오일러 그래프 정의와 정리(예제포함)

 

수학자 오일러는 어떤 그래프 G = (V, E)가 있을 때, 그래프 안에서 경로나 순환을 찾는 방법을 연구했습니다. 오일러는 그래프를 구성하는 모든 변을 지나는 경로를 찾는 방법을 연구했습니다. 

 

---

< 오일러의 정의 >

■ 오일러 경로(Eulerian Path)

그래프 G = (V, E)의 모든 변을 꼭 한 번씩 지나는 경로

 

■ 오일러 회로 / 순환( Eulerian Circuit /Eulerian Cycle)

그래프 G = (V, E)의 꼭짓점 v에서 시작해 모든 변을 꼭 한 번씩 지나 v로 돌아오는 회로

 

■ 오일러 그래프(Eulerian Graph)

오일러 회로를 포함하는 그래프 G = (V, E)

 

예제

다음 그래프에서 a에서 시작하는 오일러 그래프를 찾아라. 

풀이

더 보기를 클릭하세요.

예제풀이

(1)

a - c - b - d - a 또는 a - d - b - c - a

오일러 회로가 존재한다. 

∴ 오일러 그래프다. 

 

(2)

a - c - e - b - c - d - b - a - d

a - c - b - e - c - d - b - a - d

a - c - e - b - a - d - c - b - d

a - c - b - a - d - b - e - c - d

다양한 오일러 경로가 존재한다. 그러나 오일러 회로는 존재하지 않는다. 

∴ 오일러 그래프가 아니다.

 

---

< 오일러 그래프에 대한 정리 >

(1) 연결 그래프 G = (V, E)의 모든 꼭짓점의 차수가 짝수일 때, 오일러 그래프의 필요충분조건이 된다.

(2) 연결 그래프 G = (V, E)가 오일러 경로를 갖기 위한 필요충분조건은 그래프 G를 구성하는 꼭짓점 중 차수가 홀수인 꼭짓점의 수가 0 또는 2개인 것이다. 

 

 

 

수학으로 이해하는 디지털 논리 이산수학 322p 참고

 

 

 

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

이산수학 총정리

목록 보러가기 

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