thisisuser's study

서론 그래프(Graph)는 여러 개의 점과 선분으로 구성된 도형으로, 실생활의 여러 상황을 모델링하는 데 사용한다. 내비게이션에서 경로를 찾을 때 도시를 그래프로 모델링하는 경우도 존재하고, 여러 컴퓨터 간의 연결 관계를 나타나는 데에도 사용한다. 이 중 도시의 교통량을 최대한 분산시키거나, 시스템 간의 연결 관계가 주어졌을 때 데이터를 최대한 빠르게 전송시키는 경우를 구해야 할 때가 있다. 이를 일반화하면 그래프에서 간선의 용량이 주어질 때, 한 정점에서 다른 정점으로 최대한의 유량을 보내는 것이다. 이를 네트워크 유량 (Network Flow) 문제라 부른다. 본 탐구에서는 이를 편리하게 분석할 수 있도록 네트워크 유량 알고리즘이 포함된 그래프 시뮬레이터를 제작하였다. 사용 알고리즘 본 탐구에서는 에..

마지막으로, UI를 개선하고 데이터 저장 및 불러오기 기능을 제작하였다. 먼저 UI 개선이다. 기존에 제작한 프로그램에서는 유량이 어느 방향으로 흐르는 지 알 수 없었다. 따라서 방향을 표시해주어 이를 알 수 있도록 제작하였다. 화살표는 밑변 16, 높이 14의 이등변삼각형으로 구성해 주었다. 이때, 유량이 흐르는 방향을 판별하여 이를 향하게 해주어야 하므로 삼각비를 응용하였다. 기본적으로 다음과 같이 설정을 해줄 수 있다. 꼭짓점에서 20만큼 뺀 이유는 정점의 반지름이 20으로 표현되기 때문에 이렇게 설정하였다. 각도는 기울기로 구현하였고, 이 과정에서 고려해야 할 사항이 2가지 존재한다. 1. 기울기가 x축에 수직일 때 두 정점을 지나는 직선의 기울기는 $\frac{y_{to} - y_{from}}{..

이번에는 생성한 그래프에서 두 정점 간의 최대 유량을 계산하는 알고리즘을 구현하였다. 최대 유량 문제란, 용량이 주어진 간선에 대해 최대 유량을 구하는 문제를 의미한다. 다음과 같이 그래프가 주어진 상황을 가정하면, 1 → 3 → 4 → 2로 1의 유량을 흘려주고, 1 → 4 → 2로 2의 유량을 흘려주고, 1 → 3 → 2로 2의 유량을 흘려주면 총 5의 유량을 보낼 수 있다. 최대 유량 알고리즘으로는 에드몬드-카프 (Edmonds-Karp) 알고리즘을 사용하였다. 시간복잡도는 $O(VE^{2})$으로, 돌아가기에는 충분한 알고리즘이기에 이를 활용하였다. 두 지점을 연결하는 어떠한 경로에 대해 유량을 흘려줄 수 있다면, 항상 흘려주는 것이 더 이득이다. 즉, 그리디하게 문제를 해결할 수 있다. 만약 이..

이번 시간에는 그래프를 생성 및 수정할 수 있는 프로그램을 제작하기로 했다. 먼저 다음과 같이, 그래프를 다룰 수 있는 변수들을 설정했다. //network flow int [][]capacity = new int[101][101]; int [][]flow = new int[101][101]; int []parent = new int[101]; //graph simulation float []x = new float[101]; float []y = new float[101]; boolean []exist = new boolean[101]; 먼저 capacity와 flow는 각각 해당 간선의 용량과 현재 흐르고 있는 유량을 의미한다. 네트워크 플로우 알고리즘을 사용할 것이기 때문에 이렇게 2개의 데이터를 ..

문제 인식 그래프(Graph)는 여러 개의 점과 선분으로 구성된 도형으로, 실생활의 여러 상황을 모델링하는 데 사용한다. 예를 들어 내비게이션에서 경로를 찾을 때 도시를 그래프로 모델링하는 경우도 존재하고, 여러 컴퓨터 간의 연결 관계를 나타나는 데에도 사용한다. 이 중 도시의 교통량을 최대한 분산시키거나, 시스템 간의 연결 관계가 주어졌을 때 데이터를 최대한 빠르게 전송시키는 경우를 구해야 할 때가 있다. 이를 일반화하면 그래프에서 간선의 용량이 주어질 때, 한 정점에서 다른 정점으로 최대한의 유량을 보내는 것이다. 이를 네트워크 유량 (Network Flow) 문제라 부른다. 본 탐구에서는 이를 편리하게 분석할 수 있는 프로그램을 제작할 계획이다. 관련 조사 시행 및 문제 해결 방안 먼저 기본적인 네..