그래프 마이너

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

그래프 마이너는 그래프에서 변을 축약하거나 삭제하고 고립된 정점을 제거하여 얻을 수 있는 그래프를 의미한다. 그래프 마이너는 그래프 이론의 핵심 개념으로, 그래프의 구조와 성질을 연구하는 데 사용된다. 그래프 마이너 관계는 유한 무방향 그래프의 동형 클래스에 대한 부분 순서를 형성하며, 닐 로버트슨과 폴 시모어의 정리에 의해 잘 준 순서임이 증명되었다. 그래프 마이너는 마이너 닫힌 그래프족, 그래프 구조 정리, 하드위거 추측 등 다양한 분야와 관련되어 연구되며, 위상적 마이너, 유도된 마이너, 임머전 마이너 등 다양한 변형이 존재한다. 그래프 마이너를 포함하는지 여부를 결정하는 문제는 일반적으로 NP-완전 문제이지만, 고정된 그래프 H에 대해서는 다항 시간 내에 해결할 수 있다.

더 읽어볼만한 페이지

그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

그래프 마이너
그래프 마이너 이론
그래프 마이너 정리를 설명하는 그림
일반 정보
분야	그래프 이론
다른 이름	그래프 부분 공간
주요 개념
관련 개념	그래프 부분 그래프 그래프 분해 그래프 채색
그래프 마이너
정의	그래프 마이너는 그래프의 모서리를 축약하거나 꼭짓점이나 모서리를 삭제하여 얻을 수 있는 그래프이다.
기호	H ⪯ G (H는 G의 마이너이다)
예시	K5 (K5는 완전 그래프이며, 꼭짓점이 5개이다.) K3,3 (K3,3은 완전 이분 그래프이며, 각 부분에 꼭짓점이 3개씩 있다.)
중요성
그래프 구조	그래프 마이너는 그래프의 구조를 이해하고 특성을 분석하는 데 중요한 도구이다.
그래프 속성	특정 그래프 마이너를 포함하지 않는 그래프 클래스는 다양한 그래프 속성을 연구하는 데 사용된다.
그래프 분해	그래프 마이너는 그래프 분해와 관련된 문제를 해결하는 데 도움이 된다.
주요 정리 및 결과
바그너 정리	평면 그래프는 K5나 K3,3을 마이너로 포함하지 않는 그래프와 같다.
그래프 마이너 정리	유한한 그래프 집합에 대해, 그래프가 그 집합의 멤버를 마이너로 포함하지 않는지 여부를 테스트하는 다항 시간 알고리즘이 존재한다.
로버트슨-세이무어 정리	모든 그래프 클래스에 대해, 해당 클래스에 속하지 않는 그래프의 마이너 집합은 유한하다.
응용 분야
VLSI 설계	VLSI (초고밀도 집적 회로) 설계에서 그래프 마이너 이론은 회로 레이아웃 최적화에 사용된다.
통신 네트워크	통신 네트워크 설계에서 그래프 마이너 이론은 네트워크 연결성을 보장하고 네트워크 성능을 향상시키는 데 사용된다.
알고리즘 설계	그래프 마이너 이론은 특정 그래프 클래스에 대한 효율적인 알고리즘을 설계하는 데 사용된다.
참고 문헌
참고 문헌	라슬로 로바스 (2006). https://books.google.com/books/about/Large_Networks_and_Graph_Limits.html?id=9wlRAQAACAAJ. 미국 수학회. K. 바그너 (1937a). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen. 114 (5): 570–590. N. 로버트슨, P. 세이무어 (2004). "Graph Minors. XIII. The Disjoint Paths Problem". Journal of Combinatorial Theory, Series B. 63 (1): 65–110.
같이 보기
관련 항목	그래프 이론 부분 그래프 그래프 분해

2. 정의

그래프 $G$ 의 '''마이너'''는 변의 축약, 변의 삭제, 인접하는 변이 없는 꼭짓점의 삭제 연산을 통해 얻을 수 있는 그래프이다.^[3]

2. 1. 기본 정의

(단순) 그래프

G

에서, 변

uv\in E(G)

를 '''축약'''(contraction^영어)하여 얻는 그래프

G/uv

는 다음과 같다.

$V(G/uv)=V/{\sim}_{uv}$ . 여기서 $\sim_e$ 는 동치류가 $\{w_i\}$ ( $w_i\ne u,v$ ) 및 $\{u,v\}$ 인 동치 관계이다.
$[w_1][w_2]\in E(G/e)\iff[w_1]\ne[w_2]\land \exists w_1\in[w_1],w_2\in[w_2]\colon w_1w_2\in E(G)$

즉, 한 변

uv

를 없애고,

uv

의 양끝의 꼭짓점을 하나의 꼭짓점으로 합친다.

(무향) 그래프

G

의 '''마이너'''는

G

에 다음 연산들을 가하여 얻을 수 있는 그래프이다.

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

변의 수축은 그래프에서 변을 제거하는 동시에 해당 변이 연결했던 두 정점을 병합하는 연산이다. 무방향 그래프

H

가 다른 무방향 그래프

G

의 마이너가 되려면,

G

에서 일부 변을 수축하고, 일부 변을 삭제하며, 일부 고립된 정점을 삭제하여

H

와 그래프 동형인 그래프를 얻을 수 있어야 한다.

G

에 대한 이러한 수축 및 삭제 시퀀스의 순서는 결과 그래프

H

에 영향을 미치지 않는다.^[3]

2. 2. 추가 정의

변의 수축은 그래프에서 변을 제거하는 동시에 해당 변이 연결했던 두 정점을 병합하는 연산이다. 무방향 그래프 ''H''가 다른 무방향 그래프 ''G''의 마이너가 되려면, ''G''에서 일부 변을 수축하고, 일부 변을 삭제하며, 일부 고립된 정점을 삭제하여 ''H''와 그래프 동형인 그래프를 얻을 수 있어야 한다. ''G''에 대한 이러한 수축 및 삭제 시퀀스의 순서는 결과 그래프 ''H''에 영향을 미치지 않는다.

그래프 마이너는 종종 매트로이드 마이너의 보다 일반적인 맥락에서 연구된다. 이 맥락에서는 모든 그래프가 연결되어 있고, 자기 루프와 다중 변을 허용하는 것(즉, 단순 그래프가 아닌 멀티 그래프)을 가정하는 것이 일반적이다. 루프의 수축과 절단선의 삭제는 금지된 연산이다. 이러한 관점은 변 삭제가 그래프의 랭크를 변경하지 않고, 변 수축이 항상 랭크를 1만큼 줄인다는 장점이 있다.

다른 맥락(예: 의사 숲 연구)에서는 절단선의 삭제를 허용하고, 연결되지 않은 그래프를 허용하지만 멀티 그래프를 금지하는 것이 더 합리적이다. 이 그래프 마이너 이론의 변형에서, 그래프는 변 수축 후 항상 자기 루프와 다중 변을 제거하도록 단순화된다.^[3]

함수 ''f''가 "마이너 단조"라고 불리는 경우는, ''H''가 ''G''의 마이너일 때마다 가 성립할 때이다.

3. 예시

완전 그래프 K₅가 페테르센 그래프의 마이너임을 보이는 예시는 다음과 같다.

위 그래프에서 ''H''는 ''G''의 마이너이다.

3. 1. K₅와 페테르센 그래프

완전 그래프 K₅는 페테르센 그래프의 마이너이다. 바깥쪽 5개의 꼭짓점과 안쪽 5개의 꼭짓점을 잇는 5개의 변을 축약하면 된다.

위 그림은 K₅를 페테르센 그래프로 변환하는 과정을 보여준다. 먼저 점선으로 표시된 모서리(및 결과적으로 고립된 꼭짓점)를 삭제하여 ''G''의 부분 그래프를 구성한다. 그 다음, 회색 모서리를 수축(연결된 두 꼭짓점 병합)하면 페테르센 그래프가 된다.

3. 2. 기타 예시

위의 예시에서 그래프 ''H''는 그래프 ''G''의 마이너이다.

위 그림은 이 과정을 보여준다. 먼저 ''G''에서 점선으로 표시된 모서리(및 그 결과로 고립된 꼭짓점)를 삭제하여 부분 그래프를 만든다. 그 다음 회색 모서리를 수축(연결된 두 꼭짓점을 병합)하여 그래프 H를 얻는다.

4. 주요 정리 및 추측

그래프 마이너 관계는 유한 무방향 그래프의 동형 클래스에 대한 부분 순서를 형성하며, 추이적이다. 닐 로버트슨과 폴 시모어는 이 부분 순서가 잘 준 순서임을 증명했는데, 이는 이전에 클라우스 바그너의 이름을 딴 바그너 추측으로 알려져 있었다.^[4]^[5]

시모어와 로버트슨은 그래프 구조 정리를 통해 그래프 마이너와 그래프의 위상적 임베딩 간의 근본적인 연결을 확립했다.^[6]

임의의 그래프 H에 대해, H-마이너를 갖지 않는 그래프는 희소 그래프여야 한다. H가 h개의 정점을 갖는 경우, n개의 정점을 갖는 H-마이너 프리 그래프는 최대 $\scriptstyle O(nh\sqrt{\log h})$ 개의 간선을 가질 수 있다.^[7]^[8]

H-마이너 프리 그래프는 평면 그래프에 대한 평면 분할 정리와 유사한 분할 정리를 가지며, H-마이너-프리 그래프는 트리 너비 $\scriptstyle O(\sqrt{n})$ 를 갖는다.^[9]^[10]

그래프 이론의 하드위거 추측은 그래프 G가 k개의 정점을 갖는 완전 그래프와 동형인 마이너를 포함하지 않는 경우, G는 k-1개의 색으로 적절한 채색을 가진다고 제안한다. k=5의 경우는 사색 정리의 재진술이다.^[11] 하드위거 추측은 k ≤ 6에 대해 증명되었지만, 일반적인 경우에는 알려져 있지 않다.^[12]

스나크 정리는 W. T. 터트가 추측한 사색 정리의 강화로, 브리지가 없는 입방 그래프가 모서리 채색에서 네 가지 색을 필요로 하는 경우 페터슨 그래프를 마이너로 가져야 한다는 것을 명시한다.^[13]

4. 1. 로버트슨-시모어 정리

그래프 마이너 관계는 유한 무향 그래프의 동형 클래스에 대한 부분 순서를 형성하며, 이는 추이적이다. 와 는 서로 동형인 경우에만 서로의 마이너가 될 수 있는데, 임의의 비자명 마이너 연산은 간선 또는 정점을 제거하기 때문이다. 닐 로버트슨과 폴 시모어의 심오한 결과는 이 부분 순서가 실제로 잘 준 순서임을 명시한다. 즉, 유한 그래프의 무한 목록 ()이 주어지면 항상 인 두 개의 인덱스가 존재하여 가 의 마이너가 된다. 이를 달리 표현하면, 그래프의 임의의 집합은 마이너 순서에서 유한 개의 극소 원소만 가질 수 있다는 것이다.^[4] 이 결과는 이전에 클라우스 바그너의 이름을 딴 바그너 추측으로 알려진 추측을 증명했다. 바그너는 훨씬 전에 이 추측을 했지만 1970년에야 출판했다.^[5]

4. 2. 그래프 구조 정리

시모어와 로버트슨은 증명 과정에서 고정된 그래프 에 대해 를 마이너로 갖지 않는 임의의 그래프의 대략적인 구조를 결정하는 그래프 구조 정리도 증명했다. 정리 자체의 진술은 길고 복잡하지만, 간단히 말해 이러한 그래프는 종수가 제한된 표면에 임베딩된 그래프에서 작은 방식으로 수정된 더 작은 그래프의 클리크 합의 구조를 가져야 함을 설정한다.^[6]

따라서, 그들의 이론은 그래프 마이너와 그래프의 위상적 임베딩 간의 근본적인 연결을 확립한다.^[6]

4. 3. 희소 그래프와의 관계

임의의 그래프 H에 대해, H-마이너를 갖지 않는 간단한 그래프는 희소 그래프여야 한다. 즉, 간선의 수가 정점의 수의 상수 배보다 작아야 한다.^[7] 더 구체적으로, H가 h개의 정점을 갖는 경우, n개의 정점을 갖는 H-마이너 프리 그래프는 최대

\scriptstyle O(nh\sqrt{\log h})

개의 간선을 가질 수 있으며, 일부 K_h-마이너 프리 그래프는 적어도 이만큼의 간선을 갖는다.^[8]

따라서, H가 h개의 정점을 갖는 경우, H-마이너 프리 그래프는 평균 차수

\scriptstyle O(h \sqrt{\log h})

를 가지며, 퇴화

\scriptstyle O(h \sqrt{\log h})

를 가진다.

4. 4. 분할 정리

마이너 프리 그래프는 평면 그래프에 대한 평면 분할 정리와 유사한 분할 정리를 갖는다. 고정된 와 임의의 개의 정점을 갖는 -마이너-프리 그래프 에 대해 $\scriptstyle O(\sqrt{n})$ 개의 정점의 부분 집합을 찾아 해당 정점을 제거하면 를 (연결되지 않을 수도 있는) 두 개의 부분 그래프로 분할할 수 있으며, 각 부분 그래프에는 최대 $\frac{2n}{3}$ 개의 정점이 있다.^[9] 더욱 강력하게, 고정된 에 대해, -마이너-프리 그래프는 트리 너비 $\scriptstyle O(\sqrt{n})$ 를 갖는다.^[10]

4. 5. 하드위거 추측

그래프 이론에서 하드위거 추측은 어떤 그래프 ''G''가 ''k''개의 정점에 대한 완전 그래프와 동형인 마이너를 포함하지 않는 경우, ''G''는 ''k'' – 1개의 색상으로 적절한 채색을 가진다고 제안한다.^[11] ''k'' = 5의 경우는 사색 정리의 재진술이다. 하드위거 추측은 ''k'' ≤ 6에 대해 증명되었지만,^[12] 일반적인 경우에는 알려져 있지 않다. 볼로바스, 캐틀린, 에르되시는 이를 "그래프 이론에서 가장 심오한 미해결 문제 중 하나"라고 부른다. 사색 정리를 그래프 마이너와 관련시키는 또 다른 결과는 로버트슨, 샌더스, 시모어, 토마스가 발표한 스나크 정리인데, 이는 W. T. 터트가 추측한 사색 정리의 강화로, 브리지리스 입방 그래프가 모서리 채색에서 네 가지 색상을 필요로 하는 경우 페터슨 그래프를 마이너로 가져야 한다는 것을 명시한다.^[13]

4. 6. 스나크 정리

로버트슨, 샌더스, 시모어, 토마스가 발표한 스나크 정리는 W. T. 터트가 추측한 사색 정리를 강화한 것이다. 이 정리에 따르면, 브리지가 없는 입방 그래프가 모서리 채색에서 네 가지 색을 필요로 하면 페터슨 그래프를 마이너로 갖는다.^[13]

5. 마이너 닫힌 그래프족

어떤 그래프족 ''F''에 속하는 모든 그래프의 마이너가 ''F''에 속하면, 이 족을 ''마이너 닫힘''이라고 한다. 예를 들어 평면 그래프나 고정된 2-다양체에 그래프 임베딩을 할 때, 간선을 제거하거나 축약해도 임베딩의 종수는 증가하지 않는다. 따라서 평면 그래프와 고정된 표면에 임베딩 가능한 그래프는 마이너 닫힌 족을 이룬다.

''F''가 마이너 닫힌 족이면, ''F''에 속하지 않는 마이너 최소 그래프의 유한 집합 ''X''가 존재한다(마이너의 잘 준 순서 성질). 이 그래프들은 ''F''의 금지된 마이너이다. 즉, 그래프가 ''F''에 속하는 것은 ''X''의 어떤 그래프도 마이너로 포함하지 않는 경우뿐이다. 따라서 모든 마이너 닫힌 족 ''F''는 금지된 마이너의 유한 집합 ''X''에 대해 ''X''-마이너 프리 그래프족으로 특징지을 수 있다.^[2] 바그너의 정리는 K₅와 K_3,3을 마이너로 갖지 않는 그래프로 평면 그래프를 특징짓는, 이러한 특성화의 대표적인 예이다.^[1]

5. 1. 마이너 닫힌 그래프족의 성질

많은 그래프족은 ''F''에 속하는 그래프의 모든 마이너가 ''F''에도 속하는 성질을 가지는데, 이러한 종류를 ''마이너 닫힘''이라고 한다. 예를 들어, 평면 그래프 또는 고정된 2-다양체에 그래프를 그래프 임베딩한 경우, 간선을 제거하거나 간선을 축약해도 임베딩의 종수가 증가하지 않는다. 따라서, 평면 그래프와 고정된 표면에 임베딩 가능한 그래프는 마이너 닫힌 족을 형성한다.

''F''가 마이너 닫힌 족이면, ''F''에 속하지 않는 그래프 중 마이너 최소 그래프의 유한 집합 ''X''가 있다. 이 그래프들은 ''F''에 대한 금지된 마이너이다. 즉, 그래프가 ''F''에 속하는 것은 그래프가 ''X''에 있는 어떤 그래프도 마이너로 포함하지 않는 경우에만 해당한다. 즉, 모든 마이너 닫힌 족 ''F''는 금지된 마이너의 어떤 유한 집합 ''X''에 대해 ''X''-마이너 프리 그래프족으로 특징지을 수 있다.^[2] 이러한 유형의 특징화의 가장 잘 알려진 예는 K₅와 K_3,3을 마이너로 갖지 않는 그래프로 평면 그래프를 특징짓는 바그너의 정리이다.^[1]

어떤 경우에는 마이너 닫힌 족의 그래프의 속성이 제외된 마이너의 속성과 밀접하게 관련될 수 있다. 예를 들어 다음과 같다.

마이너 닫힌 그래프 족 ''F''는 금지된 마이너에 숲이 포함되는 경우에 한해서 경로 너비가 제한된다.^[14]
''F''는 금지된 마이너에 경로 그래프의 분리된 합집합이 포함되는 경우에 한해서 트리-깊이가 제한된다.
''F''는 금지된 마이너에 평면 그래프가 포함되는 경우에 한해서 트리 너비가 제한된다.^[15]
''F''는 금지된 마이너에 정점 그래프 (단일 정점 제거로 평면 그래프로 만들 수 있는 그래프)가 포함되는 경우에 한해서 국소 트리 너비 (트리 너비와 지름 사이의 함수 관계)가 제한된다.^[16]

''H''가 단일 교차만으로 평면에 그려질 수 있다면(즉, 교차수가 1) ''H''-마이너 프리 그래프는 평면 그래프와 제한된 트리 너비의 그래프의 클릭 합으로 형성되는 단순화된 구조 정리를 갖는다.^[17] 예를 들어, ''K''₅와 ''K''_3,3은 모두 교차수가 1이며, 바그너가 보여준 바와 같이 다음과 같다.

''K''₅-프리 그래프는 정확히 평면 그래프와 8개 정점의 바그너 그래프의 3-클릭 합이다.
''K''_3,3-프리 그래프는 정확히 평면 그래프와 ''K''₅의 2-클릭 합이다.^[18]

6. 변형

그래프 마이너는 다음과 같이 다양하게 변형될 수 있다.

위상적 마이너: 그래프 H가 G의 부분 그래프와 그래프 동형인 G의 세분을 가지면, H는 G의 위상적 마이너이다.^[19] 모든 위상적 마이너는 마이너이기도 하지만, 페테르센 그래프의 완전 그래프 ''K''₅는 마이너이지만 위상적 마이너는 아니므로 그 역은 일반적으로 성립하지 않는다.^[20]
유도된 마이너: 그래프 H가 그래프 G의 유도된 부분 그래프에서 간선을 축약하여 얻을 수 있다면, H는 G의 유도된 마이너이다.
임머전 마이너: 그래프 H가 G에 대한 일련의 리프팅 연산과 동형 부분 그래프를 통해 G에서 얻을 수 있다면, H는 G의 임머전 마이너이다. 임머전 마이너 관계는 유한 그래프 집합에서 잘 준 순서이므로, 로버트슨-세이무어 정리가 적용된다.^[24]
얕은 마이너: 그래프 G의 얕은 마이너는, 마이너를 형성하기 위해 축약된 G의 간선들이 낮은 지름을 갖는 분리된 하위 그래프들의 모임을 형성하는 마이너이다. 얕은 마이너는 그래프 마이너와 하위 그래프 이론 사이를 보간한다.^[22]
패리티 조건: 홀수 마이너는 부분 트리에 패리티 조건을 추가하여 그래프 마이너 정의를 제한한다. 이분 그래프를 생성하는 이분 마이너 개념도 있으며, 바그너의 정리가 이분 마이너에 적용된다.^[26]

6. 1. 위상적 마이너

그래프 ''H''가 ''G''의 부분 그래프와 그래프 동형인 ''G''의 세분을 가지면, ''H''는 ''G''의 '''위상적 마이너'''이다.^[19] 모든 위상적 마이너는 마이너이기도 하다. 그러나 페테르센 그래프의 완전 그래프 ''K''₅는 마이너이지만 위상적 마이너는 아니므로, 그 역은 일반적으로 성립하지 않는다. 다만 최대 차수가 3 이하인 그래프에 대해서는 역이 성립한다.^[20]

위상적 마이너 관계는 유한 그래프 집합에서 잘 준 순서를 가지지 않으므로 로버트슨-세이모어 정리는 위상적 마이너에 적용되지 않는다.

6. 2. 유도된 마이너

그래프 ''H''가 그래프 ''G''의 유도된 부분 그래프에서 간선을 축약하여 얻을 수 있다면, ''H''는 ''G''의 '''유도된 마이너'''라고 불린다. 그렇지 않으면, ''G''는 ''H''-유도 마이너가 없다고 한다.

6. 3. 임머전 마이너

''리프팅''이라고 하는 그래프 연산은 ''임머전(immersion)''이라는 개념의 핵심이다. ''리프팅''은 인접한 변에 대한 연산이다. 세 개의 정점 ''v'', ''u'', ''w''가 주어졌을 때, ''(v,u)''와 ''(u,w)''가 그래프의 변이라면, ''vuw'' 또는 ''(v,u), (u,w)''에 대한 리프팅은 두 변 ''(v,u)''와 ''(u,w)''를 삭제하고 변 ''(v,w)''를 추가하는 연산이다. ''(v,w)''가 이미 존재했던 경우, ''v''와 ''w''는 이제 두 개 이상의 변으로 연결되며, 따라서 이 연산은 본질적으로 멀티 그래프 연산이다.

그래프 ''H''가 ''G''에 대한 일련의 리프팅 연산과 동형 부분 그래프를 찾아서 그래프 ''G''에서 얻을 수 있는 경우, ''H''는 ''G''의 임머전 마이너라고 한다.

임머전 마이너를 정의하는 또 다른 방법이 있는데, 이는 리프팅 연산과 동일하다. ''H''의 인접한 요소의 이미지가 ''G''에서 변이 없는 경로로 연결되는, ''H''의 정점에서 ''G''의 정점으로의 주입 사상이 존재하면, ''H''는 ''G''의 임머전 마이너라고 한다.

임머전 마이너 관계는 유한 그래프 집합에서 잘 준 순서이며, 따라서 로버트슨과 세이무어의 결과가 임머전 마이너에 적용된다. 이는 또한 모든 임머전 마이너 폐쇄족이 금지된 임머전 마이너의 유한족에 의해 특징지어진다는 것을 의미한다.

그래프 드로잉에서 임머전 마이너는 평면화된 평면 그래프의 형태로 나타난다. 평면에서 교차점을 가진 그래프의 드로잉에서, 각 교차점을 새로운 정점으로 대체하고 그 과정에서 각 교차된 변을 경로로 세분화하여 임머전 마이너를 형성할 수 있다. 이를 통해 평면 그래프에 대한 드로잉 방법을 비평면 그래프로 확장할 수 있다.

6. 4. 얕은 마이너

그래프 ''G''의 얕은 마이너는 마이너를 형성하기 위해 축약된 ''G''의 에지가 낮은 지름을 갖는 분리된 하위 그래프 모음을 형성하는 마이너이다. 얕은 마이너는 그래프 마이너와 하위 그래프 이론 사이를 보간하며, 깊이가 높은 얕은 마이너는 일반적인 유형의 그래프 마이너와 일치하고, 깊이가 0인 얕은 마이너는 정확히 하위 그래프이다.^[22] 또한 얕은 마이너를 통해 마이너 닫힘을 따르지 않는 1-평면 그래프와 같은 그래프 클래스로 그래프 마이너 이론을 확장할 수 있다.^[23]

6. 5. 패리티 조건

홀수 마이너는 부분 트리에 패리티 조건을 추가하여 그래프 마이너 정의를 제한한다. ''H''가 ''G''의 부분 트리 모음으로 표현될 경우, ''H''가 ''G''의 홀수 마이너가 되는 경우는 ''G''의 각 부분 트리 내의 각 간선이 올바르게 색칠되고(끝점이 다른 색상), 두 부분 트리 간의 인접성을 나타내는 ''G''의 각 간선이 단색(두 끝점이 동일한 색상)이 되도록 ''G''의 정점에 두 가지 색상을 할당할 수 있을 때이다. 일반적인 종류의 그래프 마이너와 달리, 금지된 홀수 마이너를 가진 그래프는 반드시 희소 그래프는 아니다.^[24] 정점 ''k''개의 완전 그래프를 마이너로 포함한다는 하드위거 추측은 홀수 마이너의 관점에서 연구되었다.^[25]

그래프 마이너 개념의 또 다른 패리티 기반 확장은 이분 그래프를 생성하는 이분 마이너의 개념이다. 그래프 ''H''가 다른 그래프 ''G''의 이분 마이너가 되려면, ''H''는 ''G''에서 정점 삭제, 간선 삭제, 그래프의 주변 순환을 따라 서로 거리가 2인 정점 쌍 축약을 통해 얻을 수 있어야 한다. 바그너의 정리의 한 형태가 이분 마이너에 적용된다. 이분 그래프 ''G''가 평면 그래프인 것은 ''K''_3,3, 즉 요틸리티 그래프를 이분 마이너로 가지지 않는 것과 같다.^[26]

7. 알고리즘

그래프 마이너 포함 여부를 판별하는 알고리즘은 그래프의 구조적 특징을 분석하는 데 중요한 역할을 한다. 이 문제는 일반적으로 NP-완전 문제에 속하지만, 특정 조건 하에서는 다항 시간 또는 선형 시간 내에 해결할 수 있는 효율적인 알고리즘이 존재한다.

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

7. 1. 일반적인 경우 (NP-완전)

그래프 ''G''가 ''H''를 마이너로 포함하는지 여부를 결정하는 문제는 일반적으로 NP-완전 문제이다. 예를 들어 ''H''가 ''G''와 동일한 수의 정점을 가진 사이클 그래프인 경우, ''H''가 ''G''의 마이너가 되는 것은 ''G''가 해밀턴 사이클을 포함하는 경우와 같다.^[27] 그러나 ''G''가 입력의 일부이고 ''H''가 고정된 경우, 다항 시간 내에 해결할 수 있다. 더 구체적으로, 이 경우 ''H''가 ''G''의 마이너인지 테스트하는 실행 시간은 ''O''(''n''³)이며, 여기서 ''n''은 ''G''의 정점 수이고, 빅 오 표기법은 ''H''에 초지수적으로 의존하는 상수를 숨긴다.^[27] 원래 그래프 마이너 결과 이후 이 알고리즘은 ''O''(''n''²) 시간으로 개선되었다.^[28] 따라서 주어진 그래프가 금지된 마이너 중 하나를 포함하는지 테스트하는 다항 시간 알고리즘을 적용하여, 모든 마이너 닫힌 집합의 구성원을 다항 시간 내에 이론적으로 인식할 수 있다. 이 결과는 숨겨진 상수가 너무 커서 (표현하기 위해 크누스 윗 화살표 표기법의 세 계층이 필요함) 어떠한 적용도 배제하여 은하 알고리즘으로 만들기 때문에 실제로 사용되지 않는다.^[29] 또한, 이 결과를 구성적으로 적용하기 위해서는 그래프 집합의 금지된 마이너가 무엇인지 알아야 한다.^[30] 어떤 경우에는 금지된 마이너를 알고 있거나 계산할 수 있다.^[31]

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

7. 2. 고정된 H (다항 시간)

그래프 ''G''가 ''H''를 마이너로 포함하는지 여부를 결정하는 문제는 일반적으로 NP-완전 문제이다. 예를 들어, ''H''가 ''G''와 동일한 수의 정점을 가진 사이클 그래프인 경우, ''H''가 ''G''의 마이너가 되는 것은 ''G''가 해밀턴 사이클을 포함하는 경우와 같다. 그러나 ''G''가 입력의 일부이고 ''H''가 고정된 경우, 다항 시간 내에 해결할 수 있다. 더 구체적으로, 이 경우 ''H''가 ''G''의 마이너인지 테스트하는 실행 시간은 ''O''(''n''³)이며, 여기서 ''n''은 ''G''의 정점 수이고, 빅 오 표기법은 ''H''에 초지수적으로 의존하는 상수를 숨긴다.^[27] 원래 그래프 마이너 결과 이후 이 알고리즘은 ''O''(''n''²) 시간으로 개선되었다.^[28] 따라서 주어진 그래프가 금지된 마이너 중 하나를 포함하는지 테스트하는 다항 시간 알고리즘을 적용하여, 모든 마이너 닫힌 집합의 구성원을 다항 시간 내에 이론적으로 인식할 수 있다. 이 결과는 숨겨진 상수가 너무 커서 (표현하기 위해 크누스 윗 화살표 표기법의 세 계층이 필요함) 어떠한 적용도 배제하여 은하 알고리즘으로 만들기 때문에 실제로 사용되지 않는다.^[29] 또한, 이 결과를 구성적으로 적용하기 위해서는 그래프 집합의 금지된 마이너가 무엇인지 알아야 한다.^[30]

7. 3. 고정된 평면 그래프 H (선형 시간)

H가 고정된 평면 그래프인 경우, 입력 그래프 ''G''에서 ''H''가 ''G''의 마이너인지 선형 시간 내에 테스트할 수 있다.^[32]

7. 4. 평면 그래프 G (빠른 알고리즘)

''H''가 고정되지 않은 경우, ''G''가 평면 그래프인 경우 더 빠른 알고리즘이 알려져 있다.^[33]

참조

_[1] 간행물
_[2] 간행물
_[3] 간행물
_[4] 간행물
_[5] 간행물
_[6] 간행물
_[7] 간행물
_[8] 간행물
_[9] 간행물
_[10] 간행물
_[11] 간행물
_[12] 간행물
_[13] 간행물
_[14] 간행물
_[15] 간행물
_[16] 간행물
_[17] 간행물
_[18] 간행물
_[19] 간행물
_[20] 간행물
_[21] 간행물
_[22] 간행물
_[23] 간행물
_[24] 간행물 52nd Annual IEEE Symposium on Foundations of Computer Science Institute of Electrical and Electronics Engineers
_[25] 간행물 On the odd-minor variant of Hadwiger's conjecture https://ir.cwi.nl/pu[...]
_[26] 간행물 Bipartite minors
_[27] 간행물
_[28] 간행물
_[29] 논문 The NP-completeness column: An ongoing guide (edition 19)
_[30] 간행물
_[31] 논문 A Tourist Guide through Treewidth https://dspace.libra[...] 1993
_[32] 논문 A Tourist Guide through Treewidth https://dspace.libra[...] 1993
_[33] 논문 Fast Minor Testing in Planar Graphs http://www.lirmm.fr/[...] 2012-09-01

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com