2️⃣Bipartite Graph

intro

2️⃣ Bipartite Graph(이분 그래프)란, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로 칠할 수 있는 graph를 뜻한다. 

 

2️⃣ a graph in which the vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the other set.

: 즉, graph 내의 모든 간선은 두 가지 다른 색깔의 정점으로 무조건 연결되어 있어야 하고, 반대로 말하면, 한 간선이라도 동일한 색깔의 정점으로 연결되어 있다면 이분 그래프가 아니다. 또 다른 말로, 같은 그룹에 속한 정점, 즉 동일한 색깔의 정점(vertices in the same set)은 서로 단 1개의 간선이라도 연결되어 있어서는 안된다.

 

2️⃣ example

★ 같은 집합끼리의 정점은 서로 전혀 연결되어 있지 않고, 다른 집합하고만 연결되어 있다.(연결 그래프)

★ 어느 정점과도 연결되어 있지 않은 단 1개의 정점(비연결 그래프)도 Bipartite Graph에 포함한다. 위 Bipartite Graph 연결 그래프가 여러 묶음으로 존재하는 비연결 그래프 역시 Bipartite Graph에 포함한다.

 

2️⃣ application

① 매칭 문제: 예를 들어 job seeker와 job vacncy간의 연결이라든지, one set과 또 다른 other set간의 연결 문제에서 자주 사용되는 graph

② 사회적 연결망: 유저와 유저의 관심사 등등 분석이 용이함

③ 웹 검색 엔진: query와 web page와의 연결

how to identify? (이분 그래프 판별 알고리즘)

★ 연결 그래프마다 진행(즉, 비연결 그래프라면 그래프 매 노드마다 visited 유무 체크하고 진행)

① 아무 정점을 고르고 X 집합 배정

② 해당 정점의 모든 neighbor를 Y 집합 배정

③ Y 집합 내의 모든 정점의 neighbor를 X 집합 배정 / 그 반대방향 X 집합 내의 모든 정점의 neighbor를 Y집합 배정

④ 연결 graph 내의 모든 정점이 X 또는 Y 집합으로 배정될 때까지 반복

→ 위 ④ 과정 탐색을 진행하다가 자신과 인접한 정점이 속한 집합이 자신의 집합과 같음을 발견하면 이분 그래프가 아님 바로 판별

⑤ 위 연결 graph 내의 모든 과정을 거친 결과, 이분 그래프가 아님 판별이 없다면 이분 그래프!

 

def is_bipartite(graph,color,start):
    queue = deque([start])
    color[start] = 'A'
    while queue:
        node = queue.popleft()
        for v in graph[node]:
            if color[v] == 0: #not reached
                if color[node] == 'A':
                    color[v] = 'B'
                else:
                    color[v] = 'A'
                queue.append(v)
            else: #already colored
                if color[v] == color[node]:
                    return 'NO'
    return 'YES'

 

→ visited를 단순히 True / False로 나누지 않고, A color / B color / 무방문 0 이렇게 3개 체크 (처음에 0 초기화)

→

① 무방문이라면 현재 node가 A일 경우 B로 마킹 / 그 반대라면 B일 경우 A로 마킹

② 이미 방문했다면(즉 A나 B로 마킹된 노드라면), 현재 node와 같은 색깔이면 바로 이분 그래프 아님(return). 맞다면 계속 진행

---

geeksforgeeks