현 그래프

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

1. 개요
2. 정의
3. 성질
- 3.1. 완전 제거 순서
- 3.2. 최소 분리 집합
4. 응용
5. 다른 그래프와의 관계
- 5.1. 하위 클래스
- 5.2. 상위 클래스
6. 현 그래프와 관련된 문제
참조

1. 개요

현 그래프는 순환의 현을 갖는 그래프, 즉 크기가 4 이상인 모든 순환이 현을 포함하거나 모든 완전 부분 순환의 크기가 3 이하인 그래프를 의미한다. 이러한 그래프는 다항식 시간 알고리즘으로 판별 가능하며, 완전 제거 순서를 가질 때만 현 그래프이다. 현 그래프는 최대 클리크, 그래프 색칠, 트리 분해 등 다양한 응용 분야에서 활용되며, 완전 그래프나 나무와 같은 그래프를 포함하는 반면, 구간 그래프나 분할 그래프는 현 그래프의 하위 클래스에 속한다. 현 그래프와 관련된 문제로는 현 그래프 인식, 그래프 샌드위치 문제, 프로브 그래프 문제 등이 있다.

더 읽어볼만한 페이지

완벽 그래프 - 딜워스의 정리
딜워스의 정리는 부분 순서 집합의 너비와 사슬 분할의 최소 크기 간의 관계를 설명하며, 유한한 너비를 갖는 부분 순서 집합은 너비와 같은 수의 사슬로 분할될 수 있다고 말한다.
그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다.
그래프족 - 정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다.

현 그래프
그래프 정보
종류	그래프 이론
속성	모든 길이가 3보다 큰 순환은 코드를 가진다.
관련 클래스	완전 그래프 구간 그래프 트리
정의
설명	모든 길이가 3보다 큰 순환이 코드를 갖는 그래프
특징
완전성	모든 완전 그래프는 현 그래프이다.
트리	모든 트리는 현 그래프이다.
순환	3개 이상의 꼭짓점을 가진 순환 그래프는 해당 순환이 완전 그래프인 경우에만 현 그래프이다.
다른 이름
영어	Chordal graph
일본어	弦グラフ (Gengurafu)

2. 정의

그래프 $\Gamma$ 의 순환 $C\subset\Gamma$ 의 현(弦, chord^영어) $e\in E(\Gamma)$ 은 $C$ 의 두 꼭짓점 사이에 있지만, $C$ 에 포함되지 않는 $\Gamma$ 의 변이다.

그래프 $\Gamma$ 에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 그래프를 현 그래프라고 한다.

$\Gamma$ 의 크기가 4 이상인 임의의 순환은 현을 갖는다.
$\Gamma$ 의 모든 전부분 순환은 크기가 3 이하이다.

3. 성질

어떤 그래프가 현 그래프인지 여부는 다항식 시간 알고리즘으로 판별할 수 있다. 현 그래프는 완전 제거 순서를 가지며, 이는 사전식 너비 우선 탐색을 통해 효율적으로 찾을 수 있다.

현 그래프의 클리크는 쌍대 현 그래프(dually chordal graph)라고 불린다.^[8] 현 그래프가 완전 그래프일 때 극대 클리크는 최대 클리크가 된다. 이때 클리크의 정점 수는 그래프의 채색수(정점 채색)와 같아진다. 또한 현 그래프는 완전 제거 순서의 역순으로 정점을 선택하고 탐욕법을 사용하여 최적의 채색이 가능하다.

현 그래프의 채색 다항식은 쉽게 계산할 수 있다. 완전 제거 순서 $v_1,v_2,\ldots,v_n$ 을 유도하고, ''N''_''i''를 ''v''_''i''까지 삭제한 후의 ''v''_''i''의 차수(인접한 정점 수)로 한다. 예를 들어, 마지막 정점에 대한 ''N''인 ''N''_''n''은 다른 정점이 제거된 상태에서의 인접한 정점의 수이므로, ''N''_''n'' = 0이다. 채색 다항식은 $(x-N_1)(x-N_2)\cdots(x-N_n)$ 이며, 최종 항은 단순히 ''x''이므로, 이 다항식은 ''x''로 나누어 떨어진다. 또한 이 성질은 현 그래프의 형태로부터 쉽게 유도할 수 있다.^[8]

완전 제거 순서는 다항 시간 내에 현 그래프의 최대 클리크 문제에도 적용할 수 있다. 최대 클리크 문제는 일반적인 그래프에 대해 NP-완전이다. 더 일반적으로는 현 그래프는 극대 클리크를 정점 수에 비례하는 수만큼 가질 수 있지만, 일반적인 그래프에 대해서는 정점 수에 대해 극대 클리크의 개수는 지수 함수적으로 증가한다. 현 그래프의 극대 클리크를 열거하려면 완전 제거 순서를 찾아 해당 제거에 사용되는 클리크가 극대인지 판정하기만 하면 된다.

3. 1. 완전 제거 순서

그래프에서 완전 제거 순서는 각 정점 ''v''에 대해, ''v''와 순서에서 ''v'' 다음에 나타나는 ''v''의 이웃이 클리크를 형성하는 정점의 순서이다. 그래프는 완전 제거 순서를 가질 오직 그리고 만약에만 현 그래프이다.^[1]

사전식 너비 우선 탐색이라고 알려진 알고리즘을 사용하여 현 그래프의 완전 제거 순서를 효율적으로 찾을 수 있다.^[2] 이 알고리즘은 그래프의 정점을 일련의 집합으로 분할하여 유지한다. 처음에는 이 시퀀스는 모든 정점을 포함하는 단일 집합으로 구성된다. 이 알고리즘은 이전에 선택되지 않은 정점을 포함하는 시퀀스에서 가장 앞선 집합에서 정점 ''v''를 반복적으로 선택하고, 시퀀스의 각 집합 ''S''를 ''S''에서 ''v''의 이웃으로 구성된 첫 번째 하위 집합과 비이웃으로 구성된 두 번째 하위 집합의 두 개의 더 작은 하위 집합으로 분할한다. 이 분할 프로세스가 모든 정점에 대해 수행되면, 일련의 집합은 완전 제거 순서의 역순으로 집합당 하나의 정점을 갖게 된다.

이 사전식 너비 우선 탐색 프로세스와 순서가 완전 제거 순서인지 테스트하는 프로세스 모두 선형 시간 내에 수행될 수 있으므로 현 그래프를 선형 시간 내에 인식할 수 있다. 현 그래프에 대한 그래프 샌드위치 문제는 NP-완전^[3]인 반면, 현 그래프에 대한 프로브 그래프 문제는 다항 시간 복잡도를 갖는다.^[4]

현 그래프의 모든 완전 제거 순서 집합은 반매트로이드의 ''기본 단어''로 모델링될 수 있다. 주어진 현 그래프의 모든 완전 제거 순서를 효율적으로 나열하기 위한 알고리즘의 일부로 반매트로이드에 대한 이러한 연결을 사용한다.^[5]

3. 2. 최소 분리 집합

모든 그래프에서 정점 분리 집합은 제거 시 나머지 그래프를 연결 해제하는 정점 집합이다. 분리 집합은 또한 분리 집합인 진부분 집합이 없는 경우 최소이다. 현 그래프는 각 최소 분리 집합이 클리크인 그래프이다.^[4]

4. 응용

현 그래프는 다양한 분야에 응용된다. 현 그래프의 완전 제거 순서는 그래프의 여러 속성을 효율적으로 계산하는 데 사용되는 핵심 개념이다.

완전 제거 순서 찾기: 사전식 너비 우선 탐색 알고리즘을 사용하여 현 그래프의 완전 제거 순서를 선형 시간 안에 찾을 수 있다.
현 그래프 인식: 완전 제거 순서가 존재하는지 여부를 확인하여 그래프가 현 그래프인지 선형 시간 안에 판별할 수 있다.
그래프 샌드위치 문제: 현 그래프에 대한 그래프 샌드위치 문제는 NP-완전 문제이다. 반면, 현 그래프에 대한 프로브 그래프 문제는 다항 시간 복잡도를 갖는다.
반매트로이드: 현 그래프의 모든 완전 제거 순서 집합은 반매트로이드의 기본 단어로 모델링될 수 있다.

현 그래프의 클리크 그래프는 쌍대 현 그래프이다.

4. 1. 최대 클리크

완전 제거 순서를 활용하여 현 그래프의 최대 클리크를 다항 시간 내에 찾을 수 있다. 이는 일반 그래프의 경우 NP-완전 문제인 것과 대조적이다. 현 그래프는 선형적으로 많은 극대 클리크만 가질 수 있다.^[3]

현 그래프의 모든 극대 클리크를 나열하려면, 완전 제거 순서를 찾아 각 정점 v에 대해, 완전 제거 순서에서 v보다 뒤에 있는 v의 이웃과 함께 클리크를 형성하고, 결과 클리크 각각이 극대인지 테스트하면 된다.

가장 큰 극대 클리크는 최대 클리크이며, 현 그래프는 완벽하므로 이 클리크의 크기는 현 그래프의 색수와 같다.

4. 2. 그래프 색칠

현 그래프는 완전 그래프이므로, 최대 클리크의 크기는 현 그래프의 색수와 같다. 최적의 채색은 완전 제거 순서의 역순으로 정점에 탐욕 채색 알고리즘을 적용하여 얻을 수 있다.^[3]

현 그래프의 채색 다항식은 쉽게 계산할 수 있다. 완전 제거 순서

v_1, v_2, \ldots, v_n

을 찾는다.

N_i

를 해당 순서에서

v_i

다음에 오는

v_i

의 이웃 수와 같게 한다. 예를 들어,

N_n = 0

이다. 색 다항식은

(x-N_1)(x-N_2)\cdots(x-N_n)

이다. (마지막 인수는 단순히

x

이므로,

x

는 다항식을 나누며, 그래야 한다.)^[8]

4. 3. 트리 분해

Gavril|가브릴^영어^[3]에 따르면, 현 그래프는 트리와 그 부분 트리(subtree)의 교차 그래프(intersection graph)로 표현될 수 있다.

트리의 부분 트리 모음으로부터, 각 부분 트리에 하나의 정점을 가지고, 트리에서 하나 이상의 노드에서 겹치는 두 부분 트리를 연결하는 교차 그래프인 '''부분 트리 그래프'''를 정의할 수 있다. 가브릴은 부분 트리 그래프가 정확히 현 그래프라고 밝혔다.

현 그래프를 부분 트리의 교차로 표현하면 그래프의 트리 분해가 형성되며, 트리 폭은 그래프에서 가장 큰 클리크의 크기보다 1 작다. 임의의 그래프 ''G''의 트리 분해는 현 그래프의 부분 그래프로써 ''G''를 표현하는 것으로 간주될 수 있다. 그래프의 트리 분해는 정션 트리 알고리즘의 정션 트리이기도 하다.^[3]

5. 다른 그래프와의 관계

현 그래프는 다른 그래프들과 여러 관계를 맺고 있다.
완전 제거 순서는 "인접한 정점 집합이 클릭을 형성하는 그래프의 정점 ''v''의 제거"를 반복하여 그래프 전체가 제거되는 순서이다. 그래프가 현 그래프이면, 그리고 그 경우에만 그래프는 완전 제거 순서를 갖는다.^[1]

사전식 너비 우선 탐색(LexBFS)을 통해 현 그래프의 완전 제거 순서를 효율적으로 찾을 수 있다.^[2] 이 알고리즘은 그래프의 정점을 집합 열로 분할하는 방식으로 작동한다. 먼저 모든 정점을 포함하는 하나의 집합에서 시작하여, 정점 ''v''를 선택하고 ''v''에 인접한 정점과 인접하지 않은 정점으로 집합을 나눈다. 이 과정을 반복하면 완전 제거 순서의 역순으로 정점이 정렬된다.

사전식 너비 우선 탐색과 출력된 순서가 완전 제거 순서인지 확인하는 과정은 모두 선형 시간이 걸리므로, 현 그래프는 선형 시간 안에 판별할 수 있다. 현 그래프에 대한 프로브 그래프 문제는 다항 시간 내에 해결 가능하지만,^[3] 현 그래프에 대한 그래프 샌드위치 문제는 NP-완전이다.^[4]

현 그래프에 대한 모든 완전 제거 순서 집합은 반 매트로이드(antimatroid)의 기저로 모델링할 수 있다.^[5]

5. 1. 하위 클래스

구간 그래프는 경로 그래프의 부분 트리의 교차 그래프이며, 이는 트리의 특별한 경우이므로 현 그래프의 하위 집합이다.

분할 그래프는 어떤 그래프와 그 보 그래프가 모두 현 그래프인 그래프이다. 정점 수 ''n''이 증가함에 따라, 현 그래프가 분할 그래프일 확률은 1에 가까워진다.

프톨레마이오스 그래프는 현 그래프 중에서 거리 유전 그래프이기도 한 그래프를 말한다. 거리 유전 그래프는 두 정점 간의 거리가, 그 두 정점을 포함하는 임의의 연결된 유도 부분 그래프에서도 변하지 않는 그래프이다.
* 준-임계 그래프는 프톨레마이오스 그래프의 일종이며, 현 그래프이고 코그래프인 프톨레마이오스 그래프를 말한다.
* 블록 그래프도 프톨레마이오스 그래프의 일종이며, 임의의 두 극대 클리크가 적어도 하나의 정점을 공유하는 그래프이다.
** 풍차 그래프는 더 나아가 블록 그래프의 특수한 예시이며, 임의의 두 극대 클리크의 공유 정점이 하나의 정점인 그래프이다.

강한 현 그래프는 ''n''-sun (n>=3) 그래프를 유도 부분 그래프로 갖지 않는 현 그래프이다. 여기서 ''n''-sun 그래프는 2''n''개의 정점으로 이루어진 해밀턴 사이클에, 홀수 번째 떨어진 정점을 잇는 현이 1개만 포함된 그래프이다.

''K''-트리는 모든 극대 클리크와 극대 클리크 분리가 같은 크기인 현 그래프이다.^[5]
* 아폴로니안 네트워크는 현 그래프인 극대 평면 그래프 또는 평면 그래프인 3-트리이다.^[5]
* 극대 외평면 그래프는 2-트리의 서브 클래스이며, 따라서 현 그래프이다.

5. 2. 상위 클래스

현 그래프는 다음과 같은 그래프들의 상위 클래스이다.

완전 그래프
약한 현 그래프 (Weakly chordal graph)
경찰-승리 그래프 (Cop-win graph)
홀수가 없는 그래프 (Odd-hole-free graph)
짝수가 없는 그래프 (Even-hole-free graph)
Meyniel 그래프
교살 그래프 (Strangulated graph)

현 그래프는 홀수가 없는 그래프와 짝수가 없는 그래프 모두에 해당한다.^[4] 현 그래프는 모든 주변 사이클이 삼각형인 교살 그래프의 한 종류이다. 교살 그래프는 현 그래프와 최대 평면 그래프의 클리크 합으로 형성될 수 있으며, 최대 평면 그래프를 포함한다.^[4]

6. 현 그래프와 관련된 문제

그래프에서 ''완전 제거 순서''는 그래프의 각 정점 에 대해, 와 순서에서 다음에 나타나는 의 이웃이 클리크를 형성하는 정점의 순서이다. 그래프는 완전 제거 순서를 가질 오직 그리고 만약에만 현 그래프이다.

사전식 너비 우선 탐색을 사용하여 현 그래프의 완전 제거 순서를 효율적으로 찾을 수 있다.^[1] 이 알고리즘은 그래프의 정점을 일련의 집합으로 분할하여 유지한다. 처음에는 모든 정점을 포함하는 단일 집합으로 구성되고, 이전에 선택되지 않은 정점을 포함하는 시퀀스에서 가장 앞선 집합에서 정점 를 반복적으로 선택하고, 시퀀스의 각 집합 를 의 이웃으로 구성된 첫 번째 하위 집합과 비이웃으로 구성된 두 번째 하위 집합의 두 개의 더 작은 하위 집합으로 분할한다. 이 분할 프로세스가 모든 정점에 대해 수행되면, 일련의 집합은 완전 제거 순서의 역순으로 집합당 하나의 정점을 갖게 된다.

이 사전식 너비 우선 탐색 프로세스와 순서가 완전 제거 순서인지 테스트하는 프로세스 모두 선형 시간 내에 수행될 수 있으므로 현 그래프를 선형 시간 내에 인식할 수 있다. 현 그래프에 대한 그래프 샌드위치 문제는 NP-완전^[2]인 반면, 현 그래프에 대한 프로브 그래프 문제는 다항 시간 복잡도를 갖는다.^[3]

현 그래프의 모든 완전 제거 순서 집합은 반매트로이드의 ''기본 단어''로 모델링될 수 있다. 주어진 현 그래프의 모든 완전 제거 순서를 효율적으로 나열하기 위한 알고리즘의 일부로 반매트로이드에 대한 이러한 연결을 사용한다.^[4]

만약 가 임의의 그래프라면, 의 '''코드 완료'''(또는 '''최소 채움'''이라고도 함)는 를 부분 그래프로 포함하는 코드 그래프이다. 최소 채움의 매개변수 버전은 고정 매개변수 추적 가능하며, 더 나아가 매개변수 서브지수 시간 내에 해결 가능하다.^[5]^[6]

의 트리 너비는 이 클리크 크기를 최소화하도록 선택된 코드 완료의 최대 클리크에 있는 정점 수보다 1 작다.

-트리는 트리 너비를 보다 큰 숫자로 증가시키지 않고 추가적인 간선을 추가할 수 없는 그래프이다. 따라서 -트리는 자체 코드 완료이며, 코드 그래프의 하위 클래스를 형성한다. 코드 완료는 또한 몇 가지 다른 관련 그래프 클래스를 특징짓는 데 사용할 수 있다.^[7]

참조

_[1] 서적
_[2] 서적
_[3] 서적
_[4] 웹사이트 Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations http://www.stat.berk[...]
_[5] 서적
_[6] 서적
_[7] 웹사이트 Triangulated Graph
_[8] 서적
_[9] 웹사이트 Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations: http://www.stat.berk[...] 2019-03-01
_[10] 서적

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

문의하기 : help@durumis.com