그래프 이론 맛보기 이분 그래프

그래프는 점과 점을 잇는 선으로 이루어진 구조다. 점을 정점, 선을 간선이라 한다. 무엇을 점으로 두고 무엇을 선으로 둘지는 문제에 따라 정한다.

두 무리로 나뉘는 그래프

정점을 두 무리로 나눌 수 있고, 모든 간선이 서로 다른 무리를 잇는 그래프를 이분 그래프라 한다. 같은 무리 안에서는 선이 없다.

지원자와 일자리, 학생과 동아리, 작업과 기계처럼 성격이 다른 두 집합을 짝지을 때 자연스럽게 나타나는 형태다.

홀수 길이의 고리

어떤 그래프가 이분 그래프인지 어떻게 판정할까. 답은 간단하다. 길이가 홀수인 고리가 하나도 없으면 이분 그래프다.

이유를 보면 이렇다. 정점에 두 가지 색을 칠하되, 이웃한 정점끼리 다른 색이 되도록 한다고 하자. 한 점에서 출발해 선을 따라가며 색을 번갈아 칠한다.

짝수 길이의 고리를 돌면 출발점으로 돌아왔을 때 원래 색과 같다. 문제가 없다. 홀수 길이의 고리를 돌면 다른 색이 된다. 같은 점에 두 색을 칠해야 하므로 모순이다.

판정 방법도 이 논리를 그대로 쓴다. 한 점에서 시작해 너비 우선 탐색으로 퍼져 나가며 색을 번갈아 칠하고, 이미 칠해진 점과 충돌하는지 확인한다.

짝짓기

이분 그래프에서 가장 자주 다루는 문제는 최대 매칭이다. 서로 겹치지 않게 짝을 최대한 많이 만드는 문제다. 한 사람은 한 자리에만, 한 자리에는 한 사람만 배정된다.

푸는 방법의 핵심은 증가 경로라는 개념이다. 아직 짝이 없는 점에서 출발해, 짝이 없는 간선과 있는 간선을 번갈아 지나 짝이 없는 다른 점에 도달하는 경로다.

이런 경로를 찾으면 경로 위의 선택을 뒤집는다. 짝이던 것은 풀고 아니던 것은 맺는다. 그러면 짝의 수가 정확히 하나 늘어난다. 증가 경로가 더 이상 없을 때가 최대다.

최소로 덮기

이분 그래프에는 널리 알려진 정리가 있다. 최대 매칭의 크기와, 모든 간선을 덮는 데 필요한 최소 정점의 수가 같다는 것이다. 쾨니그의 정리라 한다.

일반 그래프에서는 이 등식이 성립하지 않는다. 최소 정점 덮개 문제는 일반적으로 풀기 어려운 문제에 속하는데, 이분 그래프에서는 매칭으로 바꿔 빠르게 풀 수 있다.

구조에 제약이 하나 더해지면 어려운 문제가 쉬워지는 사례로 자주 인용된다.

어디에 쓰는가

의사를 병원에 배정하는 문제, 강의실을 시간대에 배정하는 문제, 광고를 지면에 배치하는 문제가 이 틀로 다뤄진다.

각자 선호 순서가 있는 경우에는 다른 방법을 쓴다. 양쪽이 서로를 더 원하는 짝이 생기지 않도록 배정하는 알고리즘이 있고, 실제로 의료 수련 과정의 배정에 쓰이고 있다.

용량 제약이 있는 경우에는 흐름 문제로 바꿔 푼다. 각 간선에 용량을 두고 최대 유량을 구하면 매칭 문제를 포함하는 더 넓은 문제를 다룰 수 있다.