Cograph

그래프 이론에서 cograph 또는 보완 감소 가능한 graph, 즉₄ P-free graph는 단일 vertex graph₁ K에서 보완과 분리 결합을 통해 생성될 수 있는 그래프다.즉, cographs 계열은 K를₁ 포함하는 그래프의 가장 작은 등급이며, 보완 및 분리 결합에 의해 폐쇄된다.

Cographs는 1970년대 이후 여러 저자에 의해 독자적으로 발견되어 왔으며, 초기 참고 문헌에는 Jung(1978), Lerchs(1971), Seinsche(1974), Sumner(1974), Sumner(1974) 등이 있다.그것들은 또한 D*-그래프,^[1] 유전적 데이시 그래프(James C의 관련 작업 이후)라고도 불려왔다.Dacey Jr. on Orthomodular lattles)^[2] 및 2-parity 그래프.^[3]이들은 분리합집합이 수반되는 간단한 구조분해를 가지고 있으며, 라벨이 붙은 트리로 간결하게 표현될 수 있는 그래프 연산을 보완하며, 보다 일반적인 그래프 클래스에서 어려운 최대 집단을 찾아내는 등 많은 문제를 효율적으로 해결하기 위해 알고리즘적으로 사용된다.

cograph의 특별한 경우로는 전체 그래프, 전체 쌍방향 그래프, 군집 그래프, 분계점 그래프가 있다.cographs는 다시 거리-연속 그래프, 순열 그래프, 비교가능성 그래프, 완벽한 그래프의 특별한 경우다.

정의

재귀건설

모든 cograph는 다음 규칙을 사용하여 구성할 수 있다.

1. 단일 꼭지점 그래프는 cograph이다.
2. $G{\displaystyle }$ ${\displaystyle G}$이(가) cograph라면, 그 보완 $그래프{\displaystyle \stackrel{}{}}$ G${\$
3. $G{\displaystyle }$ ${\displaystyle G}$과($)$ H {\$displaystyle$ H$}$이(가) cographes라면$$, 이들의 분리 결합 $G{\displaystyle }$ ${\displaystyle \cup }$ ${\displaystyle H}$ ${\displaystyle G\cup H}$도 마찬가지다$.$

cograph는 단일 버텍스 그래프에서 시작하여 이러한 연산을 사용하여 구성할 수 있는 그래프로 정의될 수 있다.^[4]또는 보완 작업을 사용하는 대신 결합 작업을 사용할 수 있는데, ${\displaystyle \mathrm{결합}}$ 작업은 $분리{\displaystyle }$ $유니언{\displaystyle }$ G${\displaystyle }${ H ${\displaystyle$ G$\cup H}$을(를) 형성한 다음$$ G ${\displaystyle G}$의 모든 꼭지점과 $H{\displaystyle }$ ${\displaystyle H}$의 꼭지점 사이에 에지를 추가하는 것으로 구성된다$.$

기타 특성화

cographs의 몇 가지 대체 특성을 제공할 수 있다.그 중:

• cograph는 유도 서브그래프로 4개의 꼭지점(따라서 길이 3)에 경로 P를₄ 포함하지 않는 그래프다.That is, a graph is a cograph if and only if for any four vertices ${\displaystyle v_{1},v_{2},v_{3},v_{4}}$, if ${\displaystyle \{v_{1},v_{2}\},\{v_{2},v_{3}\}}$ and ${\displaystyle \{v_{3},v_{4}\}}$ are edges of the graph t암탉은 적어도${\displaystyle }${${\displaystyle {v\mathrm{}}_{}}$ 1, v 3${\displaystyle {}_{}}$ { v ${\displaystyle {}_{}}$, ${\displaystyle {v\mathrm{}}_{}{}_{}}$4 ${\displaystyle {}_{}}$ ${\displaystyle \{v_{1},v_{3}\},\{v_{$1},{$4}\},$${\displaystyle }${${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystystyle \{v_{2$},$v_{2}$중 하나 또한 에지이다$$.^[4]
• cograph는 유도 서브그래프가 하나의 정점에 있는 어떤 최대 독립된 집합과 교차하는 속성을 가진 그래프다.
• cograph는 모든 비경쟁 유도 서브그래프가 동일한 인접성을 가진 최소 두 개의 정점을 갖는 그래프다.
• cograph는 연결된 모든 유도 서브그래프가 분리된 보완체를 갖는 그래프다.
• cograph는 연결된 유도 서브그래프의 직경이 최대 2인 그래프다.
• cograph는 모든 연결된 구성요소가 지름이 최대 2인 거리 계통 그래프인 그래프다.
• cograph는 최대 2의 clique 너비를 가진 그래프다.^[5]
• cograph는 시계열-병렬 부분순서의 비교가능성 그래프다.^[1]
• cograph는 분리 가능한 순열의 순열 그래프다.^[6]
• cograph는 최소한의 화음 완성도가 사소한 완벽 그래프인 그래프다.^[7]
• cograph는 유전적으로 잘 색이 나는 그래프로서, 유도된 모든 서브그래프의 탐욕스러운 색상은 최적의 색의 수를 사용한다.^[8]
• P가₄ 없다는 것은 어떤 정점 순서로도 완벽한 순서에 대한 방해물이 존재하지 않는다는 것을 의미하기 때문에 그래프는 그래프의 모든 정점 순서가 완벽한 순서인 경우에만 cograph이다.

코트리

코트리(cotree)는 내부 노드에 숫자 0과 1로 라벨을 붙인 나무를 말한다.모든 cotree T는 T의 잎을 정점으로 하는 cograph G를 정의하며, 여기서 T의 각 노드에 뿌리를 둔 하위 트리는 해당 노드에서 내려오는 잎 집합에 의해 정의된 G의 유도 하위 그래프에 해당한다.

• 단일 리프 노드로 구성된 하위 트리는 단일 꼭지점을 갖는 유도 하위 그래프에 해당한다.
• 0으로 표시된 노드에 루트된 하위 트리는 해당 노드의 자식들이 정의한 하위 그래프의 조합에 해당한다.
• 1로 표시된 노드에 루트된 하위 트리는 해당 노드의 자녀가 정의한 하위 그래프의 결합에 해당한다. 즉, 우리는 결합을 형성하고 다른 하위 트리의 잎에 해당하는 두 꼭지점 사이에 가장자리를 추가한다.또는 그래프 집합의 결합은 각 그래프를 보완하고 보완의 결합을 형성한 다음 결과의 결합을 보완하여 형성된 것으로 볼 수 있다.

동자나무에서 형성된 cograph를 설명하는 동등한 방법은 해당 잎의 가장 낮은 공통 조상에 1로 라벨을 붙인 경우에만 두 개의 꼭지점이 가장자리로 연결된다는 것이다.반대로 모든 cograph는 cotree에 의해 이런 식으로 표현될 수 있다.만일 우리가 이 트리의 뿌리-잎 경로에 있는 라벨을 0과 1로 바꾸도록 요구한다면, 이 표현은 독특하다.^[4]

계산 속성

Cographs는 선형 시간 내에 인식될 수 있으며, 모듈식 분해,^[9] 분할 정제,^[10][11] LexBFS 또는 분할 분해를 사용하여 cotree 표현을 구성했다.^[12]일단 cotree표현이 구성되면, 많은 익숙한 그래프 문제들은 cotree에 대한 간단한 bottom-up 계산을 통해 해결될 수 있다.

예를 들어 cograph에서 최대 clique를 찾으려면 cotree의 하위 트리로 표시되는 각 하위 그래프의 최대 clike를 bottom-up 순서로 계산하십시오.0이라는 레이블이 붙은 노드의 경우, 최대 클릭은 해당 노드의 하위 노드에 대해 계산된 클릭 중 최대 클릭이다.1이라는 레이블이 붙은 노드의 경우, 최대 집단은 해당 노드의 자식들을 위해 계산된 집단의 결합이며, 크기는 어린이 집단의 크기의 합계와 같다.따라서 요람의 각 노드에 저장된 값을 교대로 최대화 및 합하여 최대 클라이크 크기를 계산할 수도 있고, 교대로 최대 클라이크 크기를 계산하여 결합을 최대화 및 취함으로써 최대 클라이크 자체를 구성할 수도 있다.유사한 상향식 트리 계산을 통해 최대 독립 집합, 정점 색상 번호, 최대 클릭 커버 및 해밀턴성(해밀턴 사이클의 존재)을 cography에서 선형 시간으로 계산할 수 있다.^[4]cographs는 clique-width를 경계로 했기 때문에, Courcelle의 정리는 cographs에 대한 그래프(MSO₁)의 단차적 2차 논리상의 어떤 속성을 선형 시간으로 시험하는데 사용될 수 있다.^[13]

주어진 그래프가 cograph에서 k 꼭지점 떨어져 있는지 또는 t 가장자리에서 떨어져 있는지 테스트하는 문제는 고정 매개변수 추적 가능하다.^[14]그래프를 cograph로 k-edge-delet할 수 있는지 여부를 결정하는 것은^* O(2.415^k) 시간에,^[15] k-edge-edded를 O(4.612^k)에서^* cograph로 해결할 수 있다.^[16]그래프에서 k 정점을 삭제해 그래프의 최대 유도 cograph 하위 그래프를 찾을 수 있다면 O^*(3.30^k) 시간에 찾을 수 있다.^[15]

두 개의 cograph는 그들의 cotree가 (동일한 라벨을 가진 두 개의 인접 정점이 없는 표준 형태에서) 이형인 경우에만 이형이다.이러한 동등성 때문에, 두 개의 cograph가 이형성인지 아닌지를 선형 시간 내에 판단할 수 있다. 그들의 cotree를 구성하고 라벨링된 나무에 대해 선형 시간 이형성 테스트를 적용함으로써 말이다.^[4]

H가 cograph G의 유도 하위 그래프인 경우 H는 그 자체로 cograph이다. G의 경우 cotree에서 잎 일부를 제거한 다음 1자녀만 있는 노드를 억제하여 H를 위한 cotree를 형성할 수 있다.유도 서브그래프가 되는 관계가 cographs에 잘 준순서가 된다는 것은 Kruskal의 트리 정리로부터 따온 것이다.^[17]따라서, cographs의 하위 제품군(평면도 cographs 등)이 유도 서브그래프 작동에 의해 폐쇄되는 경우, 제한된 수의 금지된 유도 서브그래프를 가진다.계산적으로, 이는 그러한 하위 패밀리의 시험 멤버쉽이 주어진 그래프의 요람에 대한 상향식 계산을 사용하여 이러한 금지된 하위 그래프를 포함하는지 여부를 시험함으로써 선형적으로 수행될 수 있음을 의미한다.단, 두 cograph의 크기가 모두 가변적인 경우, 두 cograph 중 하나가 다른 cograph의 유도 서브그래프인지 여부를 검정하는 것은 NP-완전이다.^[18]

Cographs는 한 번 읽기 기능을 인식하는 알고리즘에서 중요한 역할을 한다.^[19]

열거

n = 1, 2, 3, ...에 대해 정점이 n인 연결된 cograph의 수는 다음과 같다.

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ...(OEIS의 경우 시퀀스 A000669)

n > 1의 경우, 모든 cograph에 대해 정확히 하나의 cograph 또는 그것의 보완 그래프가 연결되어 있기 때문에, 동일한 수의 분리된 cograph가 있다.

관련 그래프 패밀리

서브클래스

모든 전체 그래프 K는_n cograph이며, 1-노드와 n-leaf로 구성된 cotree가 있다.마찬가지로, 모든 완전한 초당적 그래프_a,b K는 cograph이다.그것의 동나무는 0노드 아이 두 명을 가진 1노드에 뿌리를 두고 있는데, 하나는 잎자루를 가진 아이와 다른 하나는 잎자루를 가진 아이들이다.투란 그래프는 동일한 크기의 독립 집합의 가족의 결합에 의해 형성될 수 있으므로, 각 독립 집합에 대해 0노드를 갖는 1노드에 뿌리를 둔 cograph이다.

모든 분계점 그래프도 cograph이다.임계값 그래프는 이전의 모든 정점에 연결되거나 정점에 연결되지 않은 정점을 반복적으로 추가함으로써 형성될 수 있다. 각 정점은 분리 결합 또는 결합 운영 중 하나이며, 이 경우 동봉이 형성될 수 있다.^[20]

슈퍼클래스

모든 종족과 최대 독립 집합이 비어 있지 않은 교차점을 갖는 속성별 cograph의 특성은 모든 유도 하위 그래픽이 모든 최대 종족과 교차하는 독립 집합을 포함하는 매우 완벽한 그래프의 정의 속성의 더 강력한 버전이다.cograph에서는 모든 최대 독립 집합이 모든 최대 계층과 교차한다.따라서 모든 cograph는 매우 완벽하다.^[21]

cographs가 P-free라는₄ 사실은 완벽하게 주문할 수 있다는 것을 의미한다.사실, cograph의 모든 꼭지점 순서는 완벽한 순서인데, 이것은 더 나아가 최대 클라이크 발견과 최소 착색은 어떤 욕심 많은 착색도 없이 선형으로 찾을 수 있다는 것을 암시한다.

모든 cograph는 거리 계통 그래프로, cograph의 모든 유도 경로가 최단 경로임을 의미한다.cograph는 거리 계통 그래프 중에서 각각의 연결된 구성 요소에 지름 2를 갖는 것으로 특징지어질 수 있다.모든 cograph는 또한 해체조합을 교체하고 부분 주문에 대한 분리조합과 순서 합산으로 cograph를 구성한 결합운영을 통해 얻은 직렬-병렬 부분순서의 비교가능성 그래프다.매우 완벽한 그래프, 완벽하게 정렬 가능한 그래프, 거리-연속 그래프, 비교가능성 그래프가 모두 완벽한 그래프이기 때문에 cographs도 완벽하다.^[20]

메모들

참조

외부 링크

• "Cograph graphs", Information System on Graph Class Inclusions
• Weisstein, Eric W. "Cograph". MathWorld.