[이산수학]다중그래프, 방향그래프, 가중치그래프란?(예제포함)

 

■ 다중 그래프(multi-graph)

그래프 G = (V, E) 중 서로 다른 두 꼭짓점 사이에 두 개 이상의 변을 허용하는 그래프

 

 

다중 그래프 변 집합에는 같은 순서쌍이 여러 개 존재할 수 있다. 꼭짓점에 근접하는 변을 두 이상 허용하기 때문입니다. 예를 들어 두 꼭짓점 a와 b에 근접하는 변이 세 개인 경우 변의 집합은 {(a, b), (a, b), (a, b)}를 부분집합으로 갖습니다.

 

■ 방향 그래프(Directed Graph)

변에 방향이 있는 그래프

 

뱡향 그래프를 순서쌍으로 표기할 때는 화살표가 시작하는 꼬짓점을 앞에, 화살표가 끝나는 꼭짓점을 뒤에 씁니다. 그러므로 꼭짓점에 근접하는 화살표가 둘 이상인 경우 화살표 방향에 따라 순서쌍의 꼭짓점 순서가 달라집니다. 즉 <A, B>와 <B, A>는 다릅니다. 

 

■ 가중치 그래프(Weighted Graph)

그래프 G = (V, E)에서 각 변에 가중치가 정의되어 있는 그래프 

 

가중치 그래프는 도로망이나 네트워크를 설계할 때, 교통량이나 통신량을 균등하게 분배하는 데 유용하게 쓰입니다. 특히 가중치 그래프가 방향 그래프에 존재할 때 W[u, v] 앞에 오는 꼭짓점 u를 화살표가 시작하는 꼭짓점, 뒤에 오는 꼭짓점 v를 화살표가 도착하는 꼭짓점으로 하여 가중치를 표시합니다. 

 

예제 

다음 그래프를 보고 각 변의 가중치를 표기하라.

 

풀이

더 보기를 클릭하세요

예제풀이

W[a, b] = 3

W[b, a] = 6

W[b, c] = 8

W[a, e] = 5

예제 출처: 수학으로 이해하는 디지털 논리 이상수학(한빛미디어) 101p, 예제8-5 

 

 

 

 

 

 

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

이산수학 총정리

목록 보러가기 

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