[이산수학]해밀턴 그래프란?(예제포함)

 

해밀턴 그래프의 정의/예제포함

 

수학자 해밀턴은 그래프 이론을 이용해 어떤 길(변)을 지나든지 상관없이 모든 지역(꼭짓점)을 반드시 한 번씩만 지나도록 하는 방법을 연구했습니다.

 

■ 해밀턴 경로(Hamiltonian Path)

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

 

■ 해밀턴 회로 / 순환( Hamiltonian Circuit /Hamiltonian Cycle)

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

 

■ 해밀턴 그래프(Hamiltonian Graph)

해밀턴 회로를 포함하는 그래프 G = (V, E)

 

예제

다음 그래프에서 해밀턴 경로나 해밀턴 회로가 있는지 밝혀라. 

 

풀이

더 보기를 클릭하세요.

예제보기

(1)

해밀턴 경로의 예: a - b - c - f - d - c

해밀턴 회로의 예: a - f - d - c - e - b - a

∴ 해밀턴 경로와 해밀턴 회로 모두 존재한다. 

 

(2)

해밀턴 경로의 예: C - F - G - B - C - A - H - E

해밀턴 회로의 경우, B 또는 D를 두 번씩 지나야 하기 때문에 존재할 수 없다.

∴ 해밀턴 경로만 존재한다. 

 

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

 

 

 

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

이산수학 총정리

목록 보러가기 

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