그래프 마이너

그래프 이론에서, 마이너(영어: minor)는 어떤 그래프의 변과 고립 꼭짓점을 지우거나, 변을 축약시켜 얻는 그래프이다. 어떤 변을 축약한다는 말은 그 변에 접한 두 꼭지점을 하나의 꼭지점으로 합치고 그 변을 지우는 것을 뜻한다.

그래프 마이너 이론은 그래프가 평면 그래프인 경우에만 완전 그래프 K₅ 또는 완전 이분 그래프 K_3,3을 마이너로 포함하지 않는다는 바그너 정리에서 출발했다.^[1] 로버트슨-시모어 정리는 삭제 및 변 축약에 의해 보존되는 모든 그래프 속성에 대해 유사한 금지된 마이너 특성화가 존재함을 의미한다.^[2] 모든 고정된 그래프 ${\displaystyle H}$에 대해, 입력 그래프 ${\displaystyle G}$의 마이너인지 여부를 다항 시간 내에 테스트할 수 있다.^[3] 금지된 마이너 특성화와 함께 이는 삭제 및 축약에 의해 보존되는 모든 그래프 속성이 다항 시간 내에 인식될 수 있음을 의미한다.^[4]

그래프 마이너와 관련된 다른 결과 및 추측에는 ${\displaystyle H}$를 마이너로 갖지 않는 그래프가 더 간단한 조각들을 붙여서 형성될 수 있다는 그래프 구조 정리와, 그래프 색칠의 불가능성과 큰 완전 그래프의 마이너로서의 존재를 연관시키는 하드비거 추측 등이 있다. 그래프 마이너의 중요한 변형에는 위상 마이너와 침수 마이너가 포함된다.

정의

(단순) 그래프 ${\displaystyle G}$에서, 변 ${\displaystyle uv\in E(G)}$를 축약(영어: contraction)하여 얻는 그래프 ${\displaystyle G/uv}$는 다음과 같다.

• ${\displaystyle V(G/uv)=V/{\sim }_{uv}}$. 여기서 ${\displaystyle \sim _{e}}$는 동치류가 ${\displaystyle \{w_{i}\}}$ (${\displaystyle w_{i}\neq u,v}$) 및 ${\displaystyle \{u,v\}}$인 동치 관계이다.
• ${\displaystyle [w_{1}][w_{2}]\in E(G/e)\iff [w_{1}]\neq [w_{2}]\land \exists w_{1}\in [w_{1}],w_{2}\in [w_{2}]\colon w_{1}w_{2}\in E(G)}$

즉, 한 변 ${\displaystyle uv}$를 없애고, ${\displaystyle uv}$의 양끝의 꼭짓점을 하나의 꼭짓점으로 합친다.

(무향) 그래프 ${\displaystyle G}$의 마이너는 ${\displaystyle G}$에 다음의 연산들을 가하여 얻을 수 있는 그래프이다.

• 변의 축약 ${\displaystyle G\mapsto G/uv}$
• 변의 삭제 ${\displaystyle G\mapsto G-uv}$
• 인접하는 변이 없는 꼭짓점의 삭제 ${\displaystyle G\mapsto G\setminus \{v\}}$

예

완전 그래프 K₅

는 페테르센 그래프

의 마이너이다. 바깥쪽 5개의 꼭짓점과 안쪽 5개의 꼭짓점들을 잇는 5개의 변을 축약하면 된다.

주요 결과 및 추측

그래프 마이너 관계가 유한 무향 그래프의 동형류에 대한 부분 순서를 형성한다는 것을 확인하는 것은 간단하다. 이는 추이적이다(G의 마이너의 마이너는 G 자체의 마이너이다), 그리고 G와 H는 비자명한 마이너 연산이 변이나 꼭짓점을 제거하기 때문에 동형인 경우에만 서로의 마이너가 될 수 있다. 닐 로버트슨과 폴 시모어의 깊은 결과는 이 부분 순서가 실제로 준 정렬이라는 것을 나타낸다. 유한 그래프의 무한 목록 ${\displaystyle (G_{1},G_{2},\dots )}$이 주어지면 항상 ${\displaystyle i<j}$인 두 인덱스가 존재하여 ${\displaystyle G_{i}}$가 ${\displaystyle G_{j}}$의 마이너가 된다. 이를 다르게 표현하는 동등한 방법은 어떤 그래프 집합이 마이너 순서 아래에서 유한한 수의 최소 원소만을 가질 수 있다는 것이다.^[5] 이 결과는 이전에 클라우스 바그너의 이름을 딴 바그너 추측으로 알려졌던 것을 증명했다. 바그너는 훨씬 이전에 이를 추측했지만 1970년에야 발표했다.^[6]

그들의 증명 과정에서 시모어와 로버트슨은 또한 그래프 구조 정리를 증명했는데, 이 정리에서 그들은 어떤 고정된 그래프 ${\displaystyle H}$에 대해 ${\displaystyle H}$를 마이너로 갖지 않는 그래프의 대략적인 구조를 결정한다. 정리의 진술 자체는 길고 복잡하지만, 요약하자면 이러한 그래프는 경계된 종수의 표면에 임베딩된 그래프에서 작은 방식으로 수정된 더 작은 그래프의 클리크 합 구조를 가져야 한다는 것을 확립한다. 따라서 그들의 이론은 그래프 마이너와 그래프의 위상적 임베딩 사이의 근본적인 연결을 확립한다.^[7]

어떤 그래프 ${\displaystyle H}$에 대해, 단순 ${\displaystyle H}$-마이너 자유 그래프는 희소해야 한다. 이는 변의 수가 꼭짓점 수의 상수 배수보다 작다는 것을 의미한다.^[8] 더 구체적으로, ${\displaystyle H}$가 ${\displaystyle h}$개의 꼭짓점을 갖는다면, ${\displaystyle n}$-꼭짓점 단순 ${\displaystyle H}$-마이너 자유 그래프는 최대 ${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$개의 변을 가질 수 있으며, 일부 ${\displaystyle K_{h}}$-마이너 자유 그래프는 최소한 이만큼의 변을 가진다.^[9] 따라서 ${\displaystyle H}$가 ${\displaystyle h}$개의 꼭짓점을 갖는다면, ${\displaystyle H}$-마이너 자유 그래프는 평균 차수 ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$를 가지며, 또한 축퇴도 ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$를 가진다. 또한, ${\displaystyle H}$-마이너 자유 그래프는 평면 그래프의 평면 분리자 정리와 유사한 분리자 정리를 가진다. 어떤 고정된 ${\displaystyle H}$와 어떤 ${\displaystyle n}$-꼭짓점 ${\displaystyle H}$-마이너 자유 그래프 ${\displaystyle G}$에 대해, 제거 시 ${\displaystyle G}$를 각 부분 그래프당 최대 ${\displaystyle {\tfrac {2n}{3}}}$개의 꼭짓점을 갖는 두 개의 (연결되지 않을 수도 있는) 부분 그래프로 분할하는 ${\displaystyle \scriptstyle O({\sqrt {n}})}$개의 꼭짓점의 부분 집합을 찾을 수 있다.^[10] 더 나아가, 어떤 고정된 ${\displaystyle H}$에 대해, ${\displaystyle H}$-마이너 자유 그래프는 트리 폭 ${\displaystyle \scriptstyle O({\sqrt {n}})}$을 가진다.^[11]

그래프 이론의 하드비거 추측은 그래프 ${\displaystyle G}$가 ${\displaystyle k}$ 꼭짓점의 완전 그래프와 동형인 마이너를 포함하지 않으면 ${\displaystyle G}$가 ${\displaystyle k-1}$색을 사용하여 적절한 색칠을 가진다고 제안한다.^[12] ${\displaystyle k=5}$의 경우는 4색 정리의 재진술이다. 하드비거 추측은 ${\displaystyle k\leq 6}$에 대해 증명되었지만,^[13] 일반적인 경우에는 알려져 있지 않다. Bollobás, Catlin & Erdős (1980)는 이를 "그래프 이론에서 가장 깊은 미해결 문제 중 하나"라고 부른다. 4색 정리와 그래프 마이너를 연관시키는 또 다른 결과는 로버트슨, 샌더스, 시모어, 토머스가 발표한 스나크 정리인데, 이는 윌리엄 토머스 텃이 추측한 4색 정리의 강화로서, 4색을 요구하는 어떤 변 색칠을 가진 브리지 없는 삼차 그래프는 페테르센 그래프를 마이너로 가져야 한다고 진술한다.^[14]

마이너-닫힌 그래프족

 로버트슨-시모어 정리 문서에 이 부분의 마이너-닫힌 그래프족, 일부 목록 포함에 관한 추가 정보가 있습니다.

많은 그래프족은 F에 속하는 그래프의 모든 마이너가 F에도 속하는 속성을 가지고 있다. 이러한 종류를 마이너-닫힘이라고 한다. 예를 들어, 어떤 평면 그래프나 고정된 위상적 곡면에 대한 그래프의 임베딩에서, 변을 제거하거나 변을 축약하는 것은 임베딩의 종수를 증가시키지 않는다. 따라서 평면 그래프와 어떤 고정된 곡면에 임베딩될 수 있는 그래프는 마이너-닫힌 족을 형성한다.

F가 마이너-닫힌 족이라면 (마이너의 잘-준비된 순서 속성 때문에) F에 속하지 않는 그래프 중에는 유한한 마이너-최소 그래프 집합 X가 존재한다. 이 그래프들은 F에 대한 금지된 마이너이다. 그래프는 X에 있는 어떤 그래프도 마이너로 포함하지 않는 경우에만 F에 속한다. 즉, 모든 마이너-닫힌 족 F는 유한한 금지된 마이너 집합 X에 대한 X-마이너 자유 그래프의 족으로 특징지어질 수 있다.^[2] 이러한 유형의 특성화 중 가장 잘 알려진 예는 평면 그래프를 K₅도 K_3,3도 마이너로 갖지 않는 그래프로 특징짓는 바그너 정리이다.^[1]

어떤 경우에는 마이너-닫힌 족에 속하는 그래프의 속성이 제외된 마이너의 속성과 밀접하게 연결될 수 있다. 예를 들어, 마이너-닫힌 그래프 족 F는 금지된 마이너가 숲을 포함하는 경우에만 유한한 경로 폭을 가지며,^[15] F는 금지된 마이너가 경로 그래프의 서로소 합집합을 포함하는 경우에만 유한한 트리 깊이를 가지며, F는 금지된 마이너가 평면 그래프를 포함하는 경우에만 유한한 트리 폭을 가지며,^[16] F는 금지된 마이너가 정점 그래프 (단일 정점을 제거하여 평면으로 만들 수 있는 그래프)를 포함하는 경우에만 유한한 국부 트리 폭을 가진다.^[17] 만약 H가 단일 교차만으로 평면에 그려질 수 있다면 (즉, 교차 수가 1이라면), H-마이너 자유 그래프는 평면 그래프와 유한한 트리 폭을 가진 그래프의 클리크 합으로 형성되는 간소화된 구조 정리를 가진다.^[18] 예를 들어, K₅와 K_3,3은 모두 교차 수 1을 가지며, 바그너가 보여주었듯이 K₅-자유 그래프는 정확히 평면 그래프와 8개의 꼭짓점을 가진 바그너 그래프의 3-클리크 합이며, K_3,3-자유 그래프는 정확히 평면 그래프와 K₅의 2-클리크 합이다.^[19]

변형

위상 마이너

그래프 H는 H의 세분화가 G의 부분 그래프와 동형인 경우 그래프 G의 위상 마이너라고 불린다.^[20] 모든 위상 마이너는 또한 마이너이다. 그러나 역은 일반적으로 사실이 아니다(예를 들어 페테르센 그래프의 완전 그래프 K₅는 마이너이지만 위상 마이너는 아니다), 그러나 최대 차수가 3보다 크지 않은 그래프에는 성립한다.^[21]

위상 마이너 관계는 유한 그래프 집합에 대한 잘-준비된 순서가 아니므로^[22] 로버트슨과 시모어의 결과는 위상 마이너에 적용되지 않는다. 그러나 모든 분지 집합을 k개의 바깥쪽 변과 함께 아래쪽 차수가 최소 2인 k개의 잎을 가진 모든 트리로 대체함으로써 유한 금지 위상 마이너 특성화를 유한 금지 마이너 특성화로부터 구성하는 것은 간단하다.

유도 마이너

그래프 H는 G의 유도 부분 그래프에서 변을 축약하여 얻을 수 있는 경우 G의 유도 마이너라고 불린다. 그렇지 않으면 G는 H-유도 마이너 자유라고 한다.^[23]

침수 마이너

리프팅(lifting)이라는 그래프 연산은 침수(immersions)라는 개념에서 중요하다. 리프팅은 인접한 변에 대한 연산이다. 세 꼭짓점 v, u, w가 주어지고, (v,u)와 (u,w)가 그래프의 변인 경우, vuw의 리프팅 또는 이에 상응하는 (v,u), (u,w)의 리프팅은 두 변 (v,u)와 (u,w)를 삭제하고 변 (v,w)를 추가하는 연산이다. (v,w)가 이미 존재했던 경우에는 v와 w가 이제 하나 이상의 변으로 연결되므로, 이 연산은 본질적으로 다중 그래프 연산이다.

그래프 H가 (G에 대한) 일련의 리프팅 연산을 통해 얻어진 다음 동형인 부분 그래프를 찾을 수 있는 경우, H는 G의 침수 마이너라고 한다. 침수 마이너를 정의하는 또 다른 방법이 있는데, 이는 리프팅 연산과 동등하다. H는 G의 침수 마이너라고 할 수 있다. 즉, H의 꼭짓점에서 G의 꼭짓점으로의 단사 사상이 존재하여 H의 인접한 요소의 이미지가 G에서 변이 서로소인 경로로 연결된다.

침수 마이너 관계는 유한 그래프 집합에 대한 잘-준비된 순서이므로 로버트슨과 시모어의 결과는 침수 마이너에 적용된다. 또한 이는 모든 침수 마이너-닫힘 족이 유한한 금지된 침수 마이너 족에 의해 특징지어진다는 것을 의미한다.

그래프 그리기에서 침수 마이너는 비평면 그래프의 평면화로 나타난다. 즉, 교차점이 있는 평면의 그래프 그림에서 각 교차점을 새 꼭짓점으로 대체하고, 그 과정에서 각 교차된 변을 경로로 세분화하여 침수 마이너를 형성할 수 있다. 이를 통해 평면 그래프의 그리기 방법을 비평면 그래프로 확장할 수 있다.^[24]

얕은 마이너

그래프 G의 얕은 마이너는 마이너를 형성하기 위해 축약된 G의 변이 낮은 직경을 가진 서로소 부분 그래프들의 집합을 형성하는 마이너이다. 얕은 마이너는 그래프 마이너와 부분 그래프 이론 사이를 보간한다. 높은 깊이를 가진 얕은 마이너는 일반적인 그래프 마이너 유형과 일치하며, 깊이 0을 가진 얕은 마이너는 정확히 부분 그래프이다.^[25] 또한 그래프 마이너 이론을 마이너를 취하는 데 닫혀 있지 않은 1-평면 그래프와 같은 그래프 클래스로 확장할 수 있다.^[26]

패리티 조건

그래프 마이너의 대안적이면서 동등한 정의는 H가 G의 꼭짓점들이 G의 서로소 부분 트리들의 집합으로 표현될 수 있는 경우에 H가 G의 마이너이며, 두 꼭짓점이 H에서 인접하면 G의 해당 두 트리 내의 꼭짓점들과 그 연결된 변이 존재한다는 것이다. 홀수 마이너는 이 정의에 패리티 조건을 추가하여 제한한다. H가 위에서처럼 G의 부분 트리들의 집합으로 표현된다면, H는 G의 홀수 마이너이며, 이는 G의 꼭짓점에 두 가지 색깔을 할당하여 각 부분 트리 내의 G의 각 변이 적절히 색칠되고(끝점이 다른 색깔을 가짐) 두 부분 트리 사이의 인접성을 나타내는 G의 각 변이 단일 색깔(두 끝점이 같은 색깔)이 되는 방식이다. 일반적인 그래프 마이너와 달리, 금지된 홀수 마이너를 가진 그래프는 반드시 희소하지는 않다.^[27] 하드비거 추측, 즉 k-색칠 그래프는 반드시 k-꼭짓점 완전 그래프를 마이너로 포함한다는 추측은 홀수 마이너의 관점에서도 연구되었다.^[28]

그래프 마이너 개념의 다른 패리티 기반 확장은 이분 마이너 개념인데, 이는 시작 그래프가 이분 그래프일 때 이분 그래프를 생성한다. 그래프 H는 그래프 G의 이분 마이너이며, H는 G에서 꼭짓점 삭제, 변 삭제, 그리고 그래프의 말초 순환을 따라 서로 2만큼 떨어진 꼭짓점 쌍을 축소하여 얻을 수 있다. 이분 마이너에 대한 바그너 정리의 한 형태가 적용된다. 이분 그래프 G는 평면 그래프이며, 이는 유틸리티 그래프 K_3,3을 이분 마이너로 갖지 않는 경우에만 해당한다.^[29]

알고리즘

그래프 G가 H를 마이너로 포함하는지 결정하는 문제는 일반적으로 NP-완전이다. 예를 들어, H가 G와 같은 수의 꼭짓점을 가진 순환 그래프인 경우, H가 G의 마이너인 것은 G가 해밀턴 회로를 포함하는 경우에만 해당한다. 그러나 G가 입력의 일부이고 H가 고정된 경우, 이는 다항 시간 내에 해결될 수 있다. 더 구체적으로, 이 경우 H가 G의 마이너인지 테스트하는 실행 시간은 O(n³)이며, 여기서 n은 G의 꼭짓점 수이고 점근 표기법은 H에 대해 초지수적으로 의존하는 상수를 숨긴다.^[3] 원래 그래프 마이너 결과 이후, 이 알고리즘은 O(n²) 시간으로 개선되었다.^[30] 따라서 주어진 그래프가 금지된 마이너 중 하나를 포함하는지 테스트하는 다항 시간 알고리즘을 적용함으로써, 어떤 마이너-닫힘 족의 구성원을 다항 시간 내에 인식하는 것이 이론적으로 가능하다. 이 결과는 숨겨진 상수가 너무 커서(표현하려면 커누스 윗화살표 표기법의 세 계층이 필요) 어떤 응용도 배제되기 때문에 실제로 사용되지 않아 은하계 알고리즘이 된다.^[31] 또한, 이 결과를 구성적으로 적용하려면 그래프 족의 금지된 마이너가 무엇인지 알아야 한다.^[4] 일부 경우에는 금지된 마이너가 알려져 있거나 계산될 수 있다.^[32]

H가 고정된 평면 그래프인 경우, 입력 그래프 G에서 H가 G의 마이너인지 여부를 선형 시간 내에 테스트할 수 있다.^[33] H가 고정되지 않은 경우에는 G가 평면인 경우 더 빠른 알고리즘이 알려져 있다.^[34]