네트워크 플로우를 활용한 그래프 시뮬레이터 제작 계획

문제 인식

그래프(Graph)는 여러 개의 점과 선분으로 구성된 도형으로, 실생활의 여러 상황을 모델링하는 데 사용한다.

예를 들어 내비게이션에서 경로를 찾을 때 도시를 그래프로 모델링하는 경우도 존재하고,

여러 컴퓨터 간의 연결 관계를 나타나는 데에도 사용한다.

 

이 중 도시의 교통량을 최대한 분산시키거나,
시스템 간의 연결 관계가 주어졌을 때 데이터를 최대한 빠르게 전송시키는 경우를 구해야 할 때가 있다.

 

이를 일반화하면 그래프에서 간선의 용량이 주어질 때, 한 정점에서 다른 정점으로 최대한의 유량을 보내는 것이다.

이를 네트워크 유량 (Network Flow) 문제라 부른다.

 

본 탐구에서는 이를 편리하게 분석할 수 있는 프로그램을 제작할 계획이다.

 

 

관련 조사 시행 및 문제 해결 방안

먼저 기본적인 네트워크 플로우 알고리즘으로 에드몬드-카프 알고리즘이 있다.

https://gazelle-and-cs.tistory.com/82

에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm)

 

또한, 현실의 경우 용량 이외에도 그래프를 이용할 때 가중치를 고려해 주어야 하는 경우가 있다.

이는 MCMF (Minimum Cost Maximum Flow) 문제로 잘 알려져 있다.

https://anz1217.tistory.com/54

Minimum Cost Maximum Flow

 

그래프를 인접 리스트로 저장할 시 간선의 수정이 꽤나 어렵다.

따라서 인접행렬을 사용하여 구성해줄 것이다.

 

이외에도 그래프 처리 시스템을 구성할 예정이다.

이는 닮음변환의 원리를 활용하여 구현할 계획이다.

 

 

추가 탐구 계획

에드몬드-카프 알고리즘에서 발전된 디닉 알고리즘이 존재한다.

https://www.crocus.co.kr/1088

디닉 알고리즘(Dinic's Algorithm)

더 많은 데이터를 처리해야 할 경우가 생긴다면 해당 알고리즘을 활용할 것이다.

 

 

기대 효과

실생활의 여러 상황을 그래프로 모델링해야 하는 상황이 발생했을 때, 해당 프로그램을 사용하면 편리할 것으로 예측된다.

또한 이를 바탕으로 다양한 해결 방안을 모색하여 많은 일을 해결할 수 있을 것으로 기대된다.