[이산수학]그래프 개념과 용어 정리(루프, 경로, 회로, 인접)/예제포함

 

그래프는 시작적 도구로써 복잡한 작업의 과정이나 구조를 표현하는 방법입니다. 현실 세계의 요소를 점의 집합과 그 점들 간의 선으로 표현합니다. 그래서 주요 도시를 연결하는 도로, 도시의 지하철 지도가 대표적인 예입니다. 

 

Photo by osé Martín Ramírez Carrasco on Unplash

 

■ 그래프(Graph)

그래프는 원소를 꼭짓점으로, 원소들 간의 관계를 변으로 표현합니다. 즉, 그래프는 꼭짓점과 변으로 구성되므로 꼭짓점의 집합과 변의 집합으로 표현할 수 있습니다. G - (V, E)는 "그래프 G는 꼭짓점 집합 V와 변의 집합 E로 구성된다"는 것을 의미합니다. 

 

■ 인접(adjacent)과 근접(incident)

그래프 G = (V, E)에서 꼭짓점 u, v를 연결한 변 e가 있을 때 꼭짓점 u,v는 서로 인접하고, 변 e는 꼭짓점 u,v에 근접합니다.

그래프에서는 꼭짓점과 꼭짓점, 꼭짓점과 변의 관계를 '인접하다'와 '근접하다'로 표현합니다. 

 

■ 루프(Loop)

근접하는 점이 같은 점인 변 e

 

■ 경로(Path)

같은 변을 두 번 이상 포한하지 않는 길

 

■ 회로(Circuit) 또는 순환(Cycle)

경로의 시작점과 끝점이 같은 길

 

■ 길이(Length)

경로 또는 순환을 구성하는 변의 수

 

 

---

예제

 

(1) a에서 f의 경로를 모두 찾아라.

(2) a에서 시작하는 길이가 5인 경로를 2개 찾아라.

(3) a에서 시작하는 회로를 모두 찾아라.

(4) a에서 시작하는 b로 끝나는 경로 중 길이가 가장 짧은 경로는 무엇인가?

 

풀이

더 보기 클릭하세요. 

예제풀이

(1)

a - c - d - f

a - e - c - d - f

a - c - d - b - f

a - e - c - d - b - f

 

(2) 

a - e - c - d - b - f

a - e - c - d - f - b

 

(3) 

a - c - e - a

a - e - c - a

 

(4)

a - c - d - b (길이: 3)

a - c - d - f - b (길이: 4)

a - e - c - d - b (길이: 4)

a - e - c - d - f - b (길이: 5)

∴  길이가 3인 경로가 가장 짧으므로, a - c - d - b

 

 

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

이산수학 총정리

목록 보러가기 

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