최대 유량 문제 (Maximum Flow Problem) > 논문집

본문 바로가기
사이트 내 전체검색


회원로그인

최대 유량 문제 (Maximum Flow Problem)

페이지 정보

작성자 정보영재교육원 작성일10-03-26 00:00 조회4,943회 댓글0건
  • 목록

본문

최대 유량 문제 (Maximum Flow Problem) 


 

김정은1, 정순기2 

1관천중학교 3학년, 2경북대학교 부설 정보영재교육원 


 

요약 어떤 가중치가 있는 그래프 G와 두 꼭지점(vertex) s, t가 주어졌을 때, 각 파이프의 최대 용량을 고려하여 s에서 t로 흘려보낼 수 있는 최대 유량을 구하는 문제를 최대 유량 문제(Maximum flow problem)라고 부른다. 이 문제를 해결하는 가장 쉬운 방법은 포드-풀커슨 증가 경로 알고리즘(Ford-Fulkerson augmenting path algorithm)이다. 요약하자면, 각 간선(edge)에 대해 현재 그 간선을 통과하는 흐름과 남아있는 용량을 계속 추적하여 s로부터 t까지의 경로 중 총 흐름의 양을 증가시키는 것을 찾고, 그 경로를 총량에 추가시킨 후 이러한 증가 경로가 더 이상 없으면 작업을 끝내는 순으로 진행된다.

 

댓글목록

등록된 댓글이 없습니다.

  • 목록

그누보드5
모바일 버전으로 보기