완전 이분 그래프

1. 개요

완전 이분 그래프는 정점을 두 개의 부분 집합으로 분할할 수 있으며, 동일한 부분 집합 내에 변이 없고, 서로 다른 부분 집합의 정점을 연결하는 모든 변을 포함하는 그래프이다. 완전 이분 그래프는 k분 그래프이며 채색수는 k 이하이다. 완전 이분 그래프는 K_m,n으로 표기하며, 평면 그래프가 K_3,3을 그래프 마이너로 가질 수 없다는 성질을 갖는다.

2. 정의

집합 $V$의 $k$조각 분할
:$V=V\_1\backslash sqcup\backslash dotsb\; V\_k$
이 주어졌을 때, 이 분할에 대응하는 완전 $k$분 그래프(complete $k$-partite graph^영어)는 위와 같은 분할에 대하여 $k$분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.
:

완전 이분 그래프는 정점을 두 개의 부분 집합 $V\_1$과 $V\_2$로 분할할 수 있으며, 같은 부분 집합 내에 양쪽 끝점을 가진 변이 없고, 서로 다른 부분 집합의 정점을 연결할 수 있는 모든 가능한 변이 그래프의 일부인 그래프이다.

2.1. 표기법

집합 $V$의 $k$조각 분할
:$V=V\_1\backslash sqcup\backslash dotsb\; V\_k$
가 주어졌다고 하자. 이 집합의 분할에 대응하는 완전 $k$분 그래프(complete $k$-partite graph^영어)는 위와 같은 분할에 대하여 $k$분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다.

$V\_1,\backslash dotsc,V\_k$의 집합의 크기가 각각 $n\_1,\backslash dotsc,n\_k$일 때, 이에 대응하는 완전 $k$분 그래프는 $K\_\{n\_1,\backslash dotsc,n\_k\}$로 표기한다.

$k=1$일 경우, 이는 완전 그래프와 같다. $k=2$일 경우 이를 완전 이분 그래프(完全二分graph, complete bipartite graph^영어), $k=3$일 경우 이를 완전 삼분 그래프(完全三分graph, complete tripartite graph^영어)라고 한다.

3. 성질

완전 $k$분 그래프는 $k$분 그래프이며, 그 채색수는 $k$ 이하이다. 특히, 일 경우, 그 채색수는 $k$이다.

* 이분 그래프가 주어졌을 때, 매개변수 $i$에 대해 완전 이분 부분 그래프 $K\_\{i,i\}$를 포함하는지 테스트하는 것은 NP-완전 문제이다.
* 두 부분 그래프에서 변의 수 $m\backslash cdot\; n$이 최대가 되는 완전 이분 부분 그래프 $K\_\{m,n\}$를 구하는 것 또한 NP-완전 문제이다.
* k-정규 이분 그래프에 결혼 정리를 적용하면, 완전 이분 그래프 $K\_\{n,n\}$에는 라틴 방진에 대응하는 n색의 변 채색이 존재한다는 따름정리를 얻을 수 있다.

3.1. 크기

완전 k분 그래프 $K\_\{n\_1,\backslash dotsc,n\_k\}$의 꼭짓점의 수는 $|V(K\_\{n\_1,\backslash dotsc,n\_k\})|=\backslash sum\_\{i=1\}^kn\_k$이며, 변의 수는 $|V(K\_\{n\_1,\backslash dotsc,n\_k\})|=\backslash prod\_\{i=1\}^kn\_k$이다.

3.2. 그래프의 평면성

평면 그래프는 톰슨 그래프($K\_\{3,3\}$)를 그래프 마이너로 가질 수 없다. 반대로, 평면 그래프가 아닌 모든 그래프는 $K\_\{3,3\}$ 또는 $K\_5$를 그래프 마이너로 갖는다. (바그너 정리 Wagner’s theorem^영어)

3.3. 기타 성질

* 모든 완전 이분 그래프는 무어 그래프이며, -케이지이다.
* 완전 이분 그래프 및 은 꼭짓점의 수가 같을 때, 모든 삼각형 없는 그래프 중에서 가장 많은 변을 갖는다. 이는 만텔의 정리이다. 만텔의 정리는 -분할 그래프와 더 큰 클리크를 부분 그래프로 갖지 않는 그래프에 대한 튜란의 정리로 일반화되었으며, 이 두 완전 이분 그래프는 이 문제에 대한 튜란 그래프의 예시이다.
* 완전 이분 그래프 의 최소 정점 덮개 수는 이고, 최소 엣지 덮개 수는 이다.
* 완전 이분 그래프 은 크기가 인 최대 독립 집합을 갖는다.
* 완전 이분 그래프 의 인접 행렬은 고윳값 , , 0을 갖는다. 각각 중복도는 1, 1, 이다.
* 완전 이분 그래프 의 라플라시안 행렬은 고윳값 , , , 0을 갖는다. 각각 중복도는 1, , , 1이다.
* 완전 이분 그래프 은 개의 신장 트리를 갖는다.
* 완전 이분 그래프 은 크기가 인 최대 매칭을 갖는다.
* 완전 이분 그래프 은 라틴 방진에 해당하는 -엣지 채색을 갖는다.
* 모든 완전 이분 그래프는 모듈러 그래프이다. 즉, 꼭짓점의 모든 삼중항은 각 꼭짓점 쌍 사이의 최단 경로에 속하는 중위수를 갖는다.

4. 예

--
--
--

5. 역사

아타나시우스 키르허가 1669년에 완전 이분 그래프의 그림을 출판하였다.

6. 응용

완전 이분 그래프는 여러 분야에서 응용된다.

형식 개념 분석에서 관계의 방향 그래프의 부분 그래프로 발견되는 최대 이분 그래프는 '개념'이라고 불린다. 이러한 부분 그래프를 통해 형식 개념 분석을 할 수 있다.

또한, 주어진 이분 그래프에서 완전 이분 부분 그래프를 찾는 문제는 NP-완전 문제이다.

6.1. 형식 개념 분석

관계의 방향 그래프의 부분 그래프로 발견되는 최대 이분 그래프는 '개념'이라고 불린다. 이러한 부분 그래프의 만남과 결합을 통해 격자가 형성될 때, 관계는 유도된 개념 격자를 갖는다. 이러한 유형의 관계 분석을 형식 개념 분석이라고 한다.

6.2. NP-완전 문제

주어진 이분 그래프에서 완전 이분 부분 그래프를 찾는 문제는 NP-완전 문제이다. 매개변수 i가 주어졌을 때, 이분 그래프가 $K\_\{i,i\}$ 완전 이분 부분 그래프를 포함하는지 확인하는 것은 NP-완전 문제에 해당한다. 변의 수가 최대가 되는 완전 이분 부분 그래프 $K\_\{m,n\}$를 구하는 문제 역시 NP-완전 문제이다.