사용자 도구

사이트 도구


ps:2색_색칠

2색 색칠

  • 인접한 두 노드는 다른 색을 갖도록 하면서, 전체 노드들을 2가지 색으로 색칠하기.
  • 일반적인 vertex k-coloring 은 NP라서 PS에서는 다룰일이 별로 없다.

기본정리

  • 2색 색칠이 가능하다 ⇔ 이분그래프이다
  • 그래프에 홀수길이 사이클이 없으면 2색 색칠 가능
    • 트리는 사이클이 아예 없으니 당연히 가능

알고리즘

  • 기본적으로는 그래프를 순회하면서 컬러를 지정하면 된다. 시간복잡도는 O(V+E)
  • Disjoint Set을 사용하는 방법도 가능하긴 하다.
    • BFS에 비해 느리다.
    • 하지만, incremental 하게 관리해야 할 필요가 있는 경우에는 이 방법이 필요하다
    • 코드는 A Bug’s Life 참고
  • 2-SAT으로 모델링해서 푸는 방법도 가능하다.
    • 이건 disjoint set을 쓰는것보다도 더욱 느릴것 같기는 하다.
    • 하지만 문제에 변형이 복잡하게 주어지면, 이렇게 모델링하는게 간단할수도 있을것 같긴 하다 (아직 본적은 없다)

구현

  • 보통은 2-colorable 한지(=이분그래프인지) 여부를 찾는 태스크가 실제 coloring을 요구하는 태스크보다 더 흔하기는 하다. 그래서 is_bipartite 와 같은 함수를 따로 만드는 것도 생각해봤지만, 기각.
  • 방문처리를 color를 주는것으로 처리하기 때문에, DFS나 BFS나 코드가 stack을 쓰느냐 queue를 쓰느냐를 제외하고는 그냥 똑같다. 속도는 BFS가 살짝 더 빨랐다.
  • DFS는 이런식
    • def two_coloring(graph):
          color = [None] * len(graph)
          for source in range(len(graph)):
              if color[source] is not None:
                  continue
              stack = [source]
              color[source] = True
              while stack:
                  u = stack.pop()
                  color_u = color[u]
                  for v in graph[u]:
                      if color[v] is None:
                          color[v] = not color_u
                          stack.append(v)
                      elif color[v] == color_u:
                          raise ValueError('Not bipartite graph')
          return color
  • BFS는 이런식
    • def two_coloring(graph: Graph) -> list[bool]:
          color = [None] * len(graph)
          for source in range(len(graph)):
              if color[source] is not None:
                  continue
              color[source] = True
              queue = collections.deque([source])
              while queue:
                  u = queue.popleft()
                  col_u = color[u]
                  for v in graph[u]:
                      if color[v] is None:
                          color[v] = not col_u
                          queue.append(v)
                      elif color[v] == col_u:
                          raise ValueError(
                              'Graph is not 2-colorable (not bipartite).'
                          )
          return color

코드

관련 문제

토론

댓글을 입력하세요:
G K M M K
 
ps/2색_색칠.txt · 마지막으로 수정됨: 2023/04/04 15:05 저자 teferi