이분 그래프와 관련 알고리즘

이분 그래프는 노드를 두 그룹으로 나눌 수 있으며, 같은 그룹 내의 노드끼리는 간선이 연결되지 않는 그래프다.

 

 

 

 

 

 

 

 

이분 그래프와 알고리즘

이분 그래프는 정점 집합을 두 개의 그룹(U, V)으로 나눌 수 있으며, 모든 간선이 서로 다른 그룹에 속한 정점들 사이에만 존재하는 그래프이다. 이분 그래프의 성질과 관련 알고리즘은 그래프 이론과 네트워크 문제에서 중요한 도구로 사용된다.

이분 그래프의 정의와 특징

• 두 정점 집합(U, V) 사이에만 간선이 존재하며, 같은 집합 내에는 간선이 없다.
• 모든 사이클은 짝수 길이를 가진다.
• 이분 그래프는 2-색칠 가능하다. 즉, 두 가지 색으로 모든 정점을 색칠할 때, 서로 연결된 정점이 다른 색을 가지도록 할 수 있다.

이분 그래프 관련 알고리즘

1. 이분 그래프 판별 알고리즘

그래프가 이분 그래프인지 확인하려면, BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 사용하여 그래프를 2-색칠 가능 여부를 판단한다.

이분 그래프 판별 과정

Step 1: 초기 그래프

처음에는 모든 노드가 미방문 상태(흰색)입니다.

Step 2: 시작 노드 색칠

시작 노드(1번)를 빨간색으로 색칠합니다.

Step 3: 인접 노드 색칠

시작 노드의 인접 노드들을 파란색으로 색칠합니다.

Step 4: 다음 레벨 노드 색칠

파란색 노드의 인접 노드를 빨간색으로 색칠합니다.

Step 5: 최종 확인

모든 노드가 색칠되었고, 인접한 노드끼리 다른 색상을 가지므로 이분 그래프입니다.

결론

이 그래프는 이분 그래프입니다. 모든 노드를 두 그룹(빨간색과 파란색)으로 나눌 수 있으며, 같은 그룹 내의 노드들은 서로 연결되어 있지 않고, 다른 그룹의 노드들과만 연결되어 있습니다.

 

---

1. BFS를 이용한 이분 그래프 판별

설명

이 코드는 BFS를 사용하여 그래프가 이분 그래프인지 확인한다. 이분 그래프란, 그래프의 정점을 두 그룹으로 나눌 수 있으며, 같은 그룹 내 정점들 간에는 간선이 존재하지 않는 그래프를 말한다.

Python 코드

from collections import deque

def is_bipartite(graph):
    colors = [-1] * len(graph)  # 초기화: -1은 색칠되지 않음을 나타냄

    for start in range(len(graph)):
        if colors[start] == -1:  # 색칠되지 않은 정점에 대해 탐색 시작
            queue = deque([start])
            colors[start] = 0  # 첫 정점을 색칠
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if colors[neighbor] == -1:  # 이웃 정점이 색칠되지 않은 경우
                        colors[neighbor] = 1 - colors[node]  # 다른 색으로 색칠
                        queue.append(neighbor)
                    elif colors[neighbor] == colors[node]:  # 동일한 색을 가진 인접 정점 발견
                        return False
    return True  # 모든 정점이 2-색칠 가능

# 사용 예시
graph = [
    [1, 3],
    [0, 2],
    [1, 3],
    [0, 2]
]
print(is_bipartite(graph))  # 출력: True

---

2. Hopcroft-Karp Algorithm을 이용한 최대 매칭

설명

Hopcroft-Karp 알고리즘은 BFS와 DFS를 조합하여 이분 그래프의 최대 매칭을 찾는다. BFS로 증대 경로를 탐색하고, DFS로 경로를 확장하여 매칭을 최적화한다.

Python 코드

def hopcroft_karp(graph, U, V):
    pair_u = [None] * len(U)
    pair_v = [None] * len(V)
    distance = [0] * (len(U) + 1)
    matching = 0

    def bfs():
        queue = deque()
        for u in range(len(U)):
            if pair_u[u] is None:
                distance[u] = 0
                queue.append(u)
            else:
                distance[u] = float('inf')
        distance[len(U)] = float('inf')

        while queue:
            u = queue.popleft()
            if distance[u] < distance[len(U)]:
                for v in graph[u]:
                    if distance[pair_v[v]] == float('inf'):
                        distance[pair_v[v]] = distance[u] + 1
                        queue.append(pair_v[v])
        return distance[len(U)] != float('inf')

    def dfs(u):
        if u != len(U):
            for v in graph[u]:
                if distance[pair_v[v]] == distance[u] + 1:
                    if dfs(pair_v[v]):
                        pair_v[v] = u
                        pair_u[u] = v
                        return True
            distance[u] = float('inf')
            return False
        return True

    while bfs():
        for u in range(len(U)):
            if pair_u[u] is None and dfs(u):
                matching += 1

    return matching

# 사용 예시
U = [0, 1, 2]
V = [0, 1, 2]
graph = [
    [0, 1],
    [0, 2],
    [1]
]
print(hopcroft_karp(graph, U, V))  # 출력: 최대 매칭 수

---

활용 분야

1. 작업 할당: 작업과 작업자 간의 최적 연결.
2. 학생-프로젝트 배정: 학생 그룹과 프로젝트 간의 최적 매칭.
3. 네트워크 최적화: 최소 컷, 최대 플로우 문제.
4. 추천 시스템: 사용자와 상품 간의 추천 관계 분석.

---