[알고리즘] Week 5: 네트워크 플로우 알고리즘 - 개념과 최대 유량 문제

Day 1: 네트워크 플로우의 개념

• 강의 내용:
  • 네트워크 플로우의 정의
    • 네트워크 플로우란 무엇인가?
    • 유량 네트워크와 그 구성 요소 (소스, 싱크, 용량 등)
  • 네트워크 플로우의 기본 용어
    • 유량, 잔여 용량, 경로, 컷
  • 네트워크 플로우의 응용 사례
    • 물류 및 교통 네트워크
    • 데이터 네트워크
    • 작업 할당 문제
• 실습:
  • 간단한 네트워크 플로우 예제 그래프 그리기

# 간단한 네트워크 플로우 예제
class Graph:
    def __init__(self, vertices):
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
        self.V = vertices

    def add_edge(self, u, v, w):
        self.graph[u][v] = w

# 예제 그래프 생성
g = Graph(4)
g.add_edge(0, 1, 20)
g.add_edge(1, 2, 10)
g.add_edge(0, 2, 30)
g.add_edge(2, 3, 10)
g.add_edge(1, 3, 20)

print("네트워크 플로우 그래프:")
for row in g.graph:
    print(row)

 

Day 2: 최대 유량 문제 소개

• 강의 내용:
  • 최대 유량 문제란?
    • 주어진 유량 네트워크에서 소스에서 싱크로의 최대 유량을 찾는 문제
  • 최대 유량 문제의 중요성
    • 다양한 실생활 문제에 응용 가능 (예: 물류 최적화, 네트워크 데이터 전송 등)
  • 최대 유량 문제의 기본 원리
    • 유량 보존 법칙 및 용량 제한 법칙
• 실습:
  • 간단한 최대 유량 문제 설정 및 설명

# 간단한 최대 유량 문제 설정
# 그래프는 이미 Day 1에서 설정된 그래프를 사용
print("최대 유량 문제 그래프:")
for row in g.graph:
    print(row)

 

Day 3: 포드-풀커슨 알고리즘 (Ford-Fulkerson Algorithm)

• 강의 내용:
  • 포드-풀커슨 알고리즘의 개념
    • 증강 경로(augmenting path)와 잔여 용량(residual capacity)
    • 반복적으로 증강 경로를 찾아 유량을 증가시키는 방식
  • 포드-풀커슨 알고리즘의 구현
    • BFS 또는 DFS를 사용한 증강 경로 찾기
  • 시간 복잡도 분석
    • 시간 복잡도: O(E * max_flow)
• 실습:
  • 파이썬을 사용한 포드-풀커슨 알고리즘 구현 및 예제

# 포드-풀커슨 알고리즘 구현
from collections import deque

def bfs(graph, s, t, parent):
    visited = [False] * len(graph)
    queue = deque([s])
    visited[s] = True
    while queue:
        u = queue.popleft()
        for ind, val in enumerate(graph[u]):
            if not visited[ind] and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u
    return visited[t]

def ford_fulkerson(graph, source, sink):
    parent = [-1] * len(graph)
    max_flow = 0
    while bfs(graph, source, sink, parent):
        path_flow = float('Inf')
        s = sink
        while s != source:
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = parent[v]
        max_flow += path_flow
    return max_flow

# 예제 실행
graph = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0]
]
source = 0
sink = 5
print("포드-풀커슨 알고리즘에 의한 최대 유량:", ford_fulkerson(graph, source, sink))  # 23

 

Day 4: 에드몬드-카프 알고리즘 (Edmonds-Karp Algorithm)

• 강의 내용:
  • 에드몬드-카프 알고리즘의 개념
    • 포드-풀커슨 알고리즘의 특수한 경우로 BFS를 사용하여 증강 경로 찾기
  • 에드몬드-카프 알고리즘의 구현
    • BFS를 사용한 증강 경로 찾기
  • 시간 복잡도 분석
    • 시간 복잡도: O(VE^2)
• 실습:
  • 파이썬을 사용한 에드몬드-카프 알고리즘 구현 및 예제

# 에드몬드-카프 알고리즘 구현
def bfs_edmonds_karp(graph, s, t, parent):
    visited = [False] * len(graph)
    queue = deque([s])
    visited[s] = True
    while queue:
        u = queue.popleft()
        for ind, val in enumerate(graph[u]):
            if not visited[ind] and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u
    return visited[t]

def edmonds_karp(graph, source, sink):
    parent = [-1] * len(graph)
    max_flow = 0
    while bfs_edmonds_karp(graph, source, sink, parent):
        path_flow = float('Inf')
        s = sink
        while s != source:
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = parent[v]
        max_flow += path_flow
    return max_flow

# 예제 실행
graph = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0]
]
source = 0
sink = 5
print("에드몬드-카프 알고리즘에 의한 최대 유량:", edmonds_karp(graph, source, sink))  # 23

 

Day 5: 최대 유량 문제의 응용

• 강의 내용:
  • 최대 유량 문제의 실생활 응용
    • 물류 및 교통 네트워크 최적화
    • 데이터 네트워크 대역폭 관리
    • 작업 할당 및 자원 분배 문제
  • 응용 예제: 작업 할당 문제
    • 문제 정의 및 그리디 접근 방법
  • 시간 복잡도 분석
    • 문제의 복잡도와 최적화 방법
• 실습:
  • 파이썬을 사용한 작업 할당 문제 구현 및 예제

# 작업 할당 문제 예제: 최대 매칭 문제로 해결
class BipartiteGraph:
    def __init__(self, u, v):
        self.U = u
        self.V = v
        self.graph = [[0 for _ in range(v)] for _ in range(u)]

    def add_edge(self, u, v):
        self.graph[u][v] = 1

    def bpm(self, u, match_r, seen):
        for v in range(self.V):
            if self.graph[u][v] and not seen[v]:
                seen[v] = True
                if match_r[v] == -1 or self.bpm(match_r[v], match_r, seen):
                    match_r[v] = u
                    return True
        return False

    def max_bpm(self):
        match_r = [-1] * self.V
        result = 0
        for i in range(self.U):
            seen = [False] * self.V
            if self.bpm(i, match_r, seen):
                result += 1
        return result

# 예제 실행
g = BipartiteGraph(4, 4)
g.add_edge(0, 2)
g.add_edge(0, 3)
g.add_edge(1, 0)
g.add_edge(1, 2)
g.add_edge(2, 1)
g.add_edge(2, 3)
g.add_edge(3, 0)

print("최대 작업 할당:", g.max_bpm())  # 4

 

Day 6: 고급 네트워크 플로우 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 포드-풀커슨, 에드몬드-카프 알고리즘을 활용한 종합 문제
  • 네트워크 플로우 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 유량 네트워크에서 포드-풀커슨 알고리즘을 사용하여 최대 유량을 구하세요.
2. 주어진 유량 네트워크에서 에드몬드-카프 알고리즘을 사용하여 최대 유량을 구하세요.
3. 주어진 작업 할당 문제에서 최대 매칭을 구하세요.

 

Day 7: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 네트워크 플로우 최적화 시스템 개발
2. 실시간 데이터 네트워크 대역폭 관리 시스템

### 프로젝트 요구사항 예시
1. 대규모 네트워크 플로우 최적화 시스템:
   - 대규모 네트워크 데이터 입력 및 저장
   - 네트워크 플로우 알고리즘을 통한 최적화
   - 최적화된 데이터 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 네트워크 플로우 알고리즘 구현 (포드-풀커슨, 에드몬드-카프 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 네트워크 플로우 알고리즘, 특히 최대 유량 문제를 중심으로 포드-풀커슨 알고리즘과 에드몬드-카프 알고리즘의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!