흐름 (2) 썸네일형 리스트형 서큘레이션 (Circulation) 최대 흐름 문제(maximum flow problem)는 어떤 방향 그래프(directed graph)와 간선 위의 용량(capacity)으로 정의되는 흐름 네트워크(flow network)에서 시점(source)부터 종점(sink)까지 최대한 많은 양의 물을 흘리는 방법을 찾는 문제입니다. 이 문제는 이론적으로는 물론 산업적으로도 깊이 연구된 매우 중요한 조합론적 최적화 문제입니다. 제 블로그에서도 현재까지 다섯 개의 글을 적었을 만큼 매우 비중 있게 다룬 주제입니다. 이번 포스트에서는 이 문제를 보다 확장을 시켜 보고자 합니다. 원래 문제에서는 각 간선에 이 이상은 흘릴 수 없다는 제약을 주는 용량만 있었습니다. 하지만 경우에 따라서는 각 간선마다 적어도 이 정도는 흐르고 있어야 한다는 일종의 필요량.. 최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem) 저번 글에서는 최대 흐름 문제(maximum flow problem)가 무엇인지 알아 보고 최대 흐름이 만족하는 성질들도 함께 확인해 보았습니다. 최대 흐름 문제가 무엇인지 잘 모르신다면 이전 포스트를 참조하시기 바랍니다. 2020/08/29 - [기초 강좌/Algorithm analysis] - 최대 흐름 문제 이해하기 (Maximum Flow Problem) 최대 흐름 문제 이해하기 (Maximum Flow Problem) 여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결 gazelle-and-cs.tistory.com 결론부터 말씀드리면 최대 흐름의 잔여 네트워크(r.. 이전 1 다음
