AI를 위한 필수 수학

399

Chapter 9 -

그래프 모델

9.14.1

스패닝 트리와 최소 스패닝 트리

이 주제는 매우 중요하며 네트워크 라우팅 프로토콜, 최단 경로 알고리즘 및 검색 알고리즘에

사용된다. 그래프의 스패닝 트리는 그래프의 모든 노드를 포함하는 트리인 하위 그래프다. 여

기서 노드를 포함한다는 것은 두 노드를 하나의 고유 경로로 연결할 수 있다는 것을 의미한다.

즉, 스패닝 트리는 그래프의 노드를 함께 유지하게 된다. 동일한 그래프에 여러 개의 스패닝 트

리가 있을 수 있다.

9.14.2

단절점과 단절선

우리는 연결된 그래프에서 엣지를 잘라내거나 때로는 노드를 제거함으로써 그래프를 분리하여

연결을 끊을 수 있다. 통신망, 전력망, 교통망 등 주어진 그래프에서 이러한 단절점

cut

set

을 찾

을 수 있다면 연결이 끊어진 부분 사이의 모든 연결 고리를 끊을 수 있다. 일반적으로 최소한

의 엣지 또는 노드를 제거하여 그래프의 연결을 끊는 작업을 수행하는 최소 단절점

minimum

cut

set

과 최소 단절선

minimum

cut

vertice

이 유명한 주제다. 이는 네트워크에서 가장 약한 링크를 식별하

는 데도 도움이 된다. 스패닝 트리와 달리 단절은 모든 노드를 함께 유지하는 것이 아니라 노드

를 분리하는 것이다. 따라서 우리는 스패닝 트리와 단절점 사이에 밀접한 관계가 있을 것으로

당연히 예상할 수 있다. 또한 그래프가 유체, 교통, 전기, 정보와 같은 어떤 종류의 원천 소스와

각 엣지가 일정량만 통과할 수 있는 싱크

sink

가 있는 네트워크를 ...