[알고리즘2] Max Flow and Min Cut

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Contents

• Max Flow
• Ford-Fulkerson 알고리즘
• Min cut
• Maxflow-mincut - baseball elimination

 

▶Max Flow

<입력>

Edge-weighted Digraph

간선의 weight : (거리 아닌) flow 흐를 수 있는 최대량 capacity를 나타낸다. (>= 0)

 

flow의 출발지 s, 도착지 t

 

Max Flow는 출발지에서 도착지로 흐를 수 있는 flow의 최대량

 

꼭 지켜야 하는 물리적 법칙

1. flow는 간선 방향 따라서 흐른다.

2. 0 <= flow <= capacity

3. Local equilibrium 조건 : 출발지와 도착지를 제외한 모든 정점에서 inflow의 합 = outflow의 합

728x90

▶Ford-Fulkerson 알고리즘

더는 더할 수 없을 때까지 flow를 조금씩 더해가는 방법을 사용한다.

이를 위해 출발지에서 도착지까지 flow를 더할 수 있는 경로를 찾아 flow를 더한다.

이런 경로를 augmenting path라고 한다.

출발지에서 도착지까지 연속된 간선의 집합

forward 간선(s -> t 방향) : flow 더할 수 있으면 선정 (현재 배정된 flow < capacity)

backward 간선(s <- t 방향) : flow 뺄 수 있으면 선정 (현재 배정된 flow > 0)

 

augmenting path의 마지막 간선이 backward간선으로 선택된다면 문제가 없을까?

출발지에서는 나가는 간선만, 도착지에서는 들어오는 간선만 고려한다.

따라서 augmenting path에서 backward간선들 후에는 반드시 forward 간선이 선택되며 도착지에 연결된다.

 

augmenting path(p) 탐색해서 존재한다면

 

p의 minflow 찾기 (p를 통해서 추가로 흘려보낼 수 있는 최대량)

min(forward 간선에 더할 수 있는 flow 최대량, backward 간선에서 뺄 수 있는 flow 최대량)

 

p의 각 간선에 minflow만큼 더 흘려보내기

forward 간선에는 minflow만큼 flow 더하고, backward 간선에는 minflow만큼 flow 뺀다.

 

 

Ford-Fulkerson 알고리즘의 worst-case 성능

s-t augmenting path 찾는데 dfs나 bfs를 사용한다면 ~V+E 시간 소요된다. (V<<E -> ~E)

모든 간선의 capacity가 >=0인 정수이고, max flow = U라면

한 augmenting path마다 최소 +1씩 flow 추가되므로 최대 U회 iteration 후에 max flow에 도달한다.

	비용	Iteration 횟수	총 비용
Augmenting path P 찾기	V+E	U	(V+E) * U E >> V라면 -> EU
P의 minflow 찾기	V
P에 속한 간선에 minflow만큼 더하기(빼기)	V

# Perform BFS to find vertices reachable from s along with shortest paths to them
def hasAugmentingPath(self):
	self.edgeTo = [None for _ in range(self.g.V)]
	self.visited = [False for _ in range(self.g.V)]

	q = Queue()
	q.put(self.s)
	self.visited[self.s] = True
	while not q.empty():
		v = q.get()
		for e in self.g.adj[v]:
			w = e.other(v)
			if e.remainingCapacityTo(w) > 0 and not self.visited[w]:
				self.edgeTo[w] = e
				self.visited[w] = True
				q.put(w)

	return self.visited[self.t] # Is t reachable from s with current flow assignment?

임의의 path를 사용하는 DFS기반의 방식보다,

최소 간선수 path를 사용하는 BFS기반 혹은 minflow가 가장 큰 path를 사용하는 것이 빠르다.

class FordFulkerson:
	def __init__(self, g, s, t):
		self.flow = 0.0
		while self.hasAugmentingPath(): # augmenting path 존재하는 경우 아래 반복
			# 찾은 augmenting path의 minflow 구하기
			minflow = float('inf')
			v = t
			while v != s: 
				minflow = min(minflow, self.edgeTo[v].remainingCapacityTo(v))
				v = self.edgeTo[v].other(v)

			# 구한 minflow를 augmenting path 각 간선에 더함
			v = t
			while v != s:
				self.edgeTo[v].addRemainingFlowTo(v, minflow)
				v = self.edgeTo[v].other(v)

			# Increase the amoung of flow
			self.flow += minflow

▶Min Cut

Cut(partition) : G의 정점을 2개의 partition으로 분할한 것이다.

G의 정점을 출발지가 속한 cut과 도착지가 속한 cut으로 분할하는 경우만 고려한다.

 

Cut의 capacity : crossing edge 중 출발지 -> 도착지 방향의 간선의 capacity의 합이다.

즉 forward 간선의 capacity의 합이다.

 

Min cut : capacity가 최소인 cut이다.

 

전체 flow를 구했다고 가정하면,

min cut은 남은 flow를 가지고, 출발지에서 갈수있는지없는지를 확인하면 된다.

# Perform BFS to find vertices reachable from s along with shortest paths to them
def hasAugmentingPath(self):
	self.edgeTo = [None for _ in range(self.g.V)]
	self.visited = [False for _ in range(self.g.V)]
	
	q = Queue()
	q.put(self.s)
	self.visited[self.s] = True
	while not q.empty():
		v = q.get()
		for e in self.g.adj[v]:
			w = e.other(v)
			if e.remainingCapacityTo(w) > 0 and not self.visited[w]:
				self.edgeTo[w] = e
				self.visited[w] = True
				q.put(w)

	return self.visited[self.t] # Is t reachable from s with current flow assignment?

class FordFulkerson: 47
	def __init__(self, g, s, t): 
		# Ford Fulkerson 알고리즘으로 s->t max flow 구해 저장
		# while loop 내부에서 hasAugmentingPath() 호출해 augmenting path 찾으며 진행
		# 더는 augmenting path 찾을 수 없다면 max flow 구한 것으로 보고 종료

	def hasAugmentingPath(self): 
		# BFS 수행해 augmenting path 찾음

	def inCut(self, vertex): 
		# 정점 vertex가 출발지 쪽 cut에 포함되었다면 True 반환
		return self.visited[vertex]