화음 그래프

두 개의 코드(녹색)가 있는 주기(검은색)입니다.이 부분에 대해서는 그래프가 화음입니다.그러나 녹색 모서리 하나를 제거하면 비좌표 그래프가 생성됩니다.실제로, 세 개의 검은 가장자리가 있는 다른 녹색 가장자리는 코드 없이 길이 4의 순환을 형성합니다.

그래프 이론의 수학적 영역에서, 화음 그래프는 4개 이상의 정점의 모든 사이클이 화음을 갖는 것으로, 화음은 주기의 일부가 아니지만 주기의 두 정점을 연결하는 가장자리이다.마찬가지로 그래프의 모든 유도 사이클에는 정확히 3개의 정점이 있어야 합니다.화음 그래프는 제거 순서가 완벽한 그래프, 각 최소 구분자가 집단인 그래프 및 트리의 하위 트리의 교차 그래프로도 특징지을 수 있습니다.이러한 그래프를 강체^[1] 회로 그래프 또는 삼각 그래프라고도 합니다.^[2]

화음 그래프는 완벽한 그래프의 하위 집합입니다.그것들은 선형 시간으로 인식될 수 있고, 그래프 색칠과 같은 다른 종류의 그래프에서 어려운 몇 가지 문제는 입력이 화음일 때 다항식 시간으로 해결될 수 있다.임의 그래프의 트리 폭은 해당 그래프를 포함하는 화음 그래프의 클리크 크기로 특징지을 수 있습니다.

완벽한 배제와 효율적인 인식

그래프에서 완전 소거 순서는 각 정점 v, v 및 v의 이웃에 대해 v의 순서로 clique를 형성하도록 그래프의 정점의 순서이다.그래프는 완전 제거 ^[3]순서가 있는 경우에만 화음입니다.

Rose, Lueker & Tarjan(1976) (Habib 등 참조). 2000)은 사전적 폭 우선 검색으로 알려진 알고리즘을 사용하여 코드 그래프의 완벽한 제거 순서를 효율적으로 찾을 수 있음을 보여준다.이 알고리즘은 그래프의 정점 파티션을 일련의 세트로 유지합니다.처음에는 이 시퀀스는 모든 정점으로 구성된 단일 세트로 구성됩니다.알고리즘은 시퀀스 내의 가장 오래된 세트 중 이전에 일치하지 않은 정점을 포함하는 정점 v를 반복적으로 선택하고 시퀀스의 각 세트 S를 2개의 작은 서브셋으로 분할합니다.첫 번째는 S의 v의 네이버로 구성되고 두 번째는 비네이버로 구성됩니다.모든 정점에 대해 이 분할 프로세스가 수행된 경우, 집합의 시퀀스는 완벽한 제거 순서와 반대로 세트당 하나의 정점을 가집니다.

이 사전적 폭 우선 탐색 프로세스와 순서가 완벽한 제거 순서인지 여부를 테스트하는 프로세스 모두 선형 시간에 실행할 수 있기 때문에 코드 그래프를 선형 시간에 인식할 수 있다.화음 그래프의 그래프 샌드위치 문제는 NP-완전인^[4] 반면, 화음 그래프의 프로브 그래프 문제는 다항식 ^[5]시간 복잡성을 가진다.

화음 그래프의 모든 완벽한 제거 순서 집합은 항원체의 기본 단어로 모델링할 수 있다; Chandran et al. (2003) 주어진 화음그래프의 모든 완전 삭제 순서를 효율적으로 나열하기 위한 알고리즘의 일부로서 안티로이드와의 접속을 사용한다.

최대 클리어와 그래프 컬러링

완전 제거 순서의 또 다른 적용은 다항 시간에서 화음 그래프의 최대 클리크를 찾는 것이지만, 일반 그래프에 대한 동일한 문제는 NP-완전이다.보다 일반적으로, 화음 그래프는 선형적으로 많은 최대 클리어를 가질 수 있지만, 비화음 그래프는 기하급수적으로 많을 수 있습니다.화음 그래프의 모든 최대 클리어를 나열하려면 단순히 완벽한 제거 순서를 찾고 v보다 늦은 v의 인접 요소와 함께 각 정점 v에 대한 클리크를 완벽한 제거 순서로 형성하고 결과 클리어가 최대인지 여부를 테스트합니다.

화음 그래프의 클리크 그래프는 이중 화음 ^[6]그래프입니다.

가장 큰 최대 클리크는 최대 클리크이며, 코드 그래프가 완벽하기 때문에 이 클리크의 크기는 코드 그래프의 색수와 같습니다.화음 그래프는 완벽하게 정렬할 수 있습니다.완벽한 제거 ^[7]순서와 반대로 정점에 탐욕스러운 색채 알고리즘을 적용하면 최적의 색채를 얻을 수 있습니다.

화음 그래프의 색다항식은 계산하기 쉽다. $v_{1},v_{2},\ldots ,v_{n}.$ $v_{1},v_{2},\ldots ,v_{n}.$ $v_{1},v_{2},\ldots ,v_{n}.$ . $v_{1},v_{2},\ldots ,v_{n}.$ { $displaystyle v_{1$ }, $v_{2},\ldots,v_{n}$ $v_{1},v_{2},\ldots ,v_{n}.$ 으로 정렬된 완벽한 삭제를 찾습니다.} N을 $v_{1},v_{2},\ldots ,v_{n}.$ 해당 순서로 v 뒤에 오는_i v의 네이버_i 수와 같다고 합니다_i $.$ 예를_n 들어 N = 0입니다.색다항식은 $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ ( $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ - $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ 1) $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ ( $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ - $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ 2) $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ ( $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ - $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ ) $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ ) ( $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ - N $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ ) . { $displaystyle$ ( x - N $_$ ${$ 1 $}$ ( x - $N _$ {2} )\ $cdots$ ( x - N _ { n $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ } ) $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ (마지막 인자는 단순하게 x이므로 x는 다항식을 분할해야 합니다.)분명히, 이 계산은 ^[8]화음에 의존합니다.

최소 구분 기호

어떤 그래프에서든 정점 구분자는 제거된 정점의 집합으로 나머지 그래프는 연결이 끊깁니다. 구분자이기도 한 적절한 하위 집합이 없는 경우 구분자는 최소입니다.Dirac(1961년)의 정리에 따르면, 화음 그래프는 각 최소 구분자가 집단인 그래프이다. Dirac은 화음 그래프가 완벽하다는 것을 증명하기 위해 이 특성화를 사용했다.

화음 그래프의 패밀리는 A and S s B 모두 화음 유도 서브그래프를 형성하고 S b B는 패밀리를 형성하며 A에서 B까지 가장자리가 없는 3개의 빈 서브셋 A, S 및 B로 분할할 수 있는 그래프로 귀납적으로 정의할 수 있다.즉, 이러한 그래프는 clique 구분자에 의해 더 작은 하위 그래프로 재귀적으로 분해되는 그래프입니다.이러한 이유로 화음 그래프는 분해 가능한 ^[9]그래프라고도 불립니다.

하위 트리의 교차 그래프

6노드 트리의 8개 서브트리의 교차 그래프로 표시되는 8개의 정점이 있는 현 그래프.

가브릴(1974)로 인한 화음 그래프의 대체 특성화에는 나무와 그 하위 트리가 포함된다.

트리의 서브트리 집합에서 서브트리 그래프를 정의할 수 있습니다.이것은 서브트리당 하나의 정점과 트리의 하나 이상의 노드에서 겹치는 임의의 2개의 서브트리를 연결하는 에지를 가진 교차 그래프입니다.가브릴은 하위 트리 그래프가 정확히 화음 그래프라는 것을 보여주었다.

서브트리의 교점으로서의 화음그래프의 표현은 그래프 내의 가장 큰 패거리 크기보다 1 작은 트리폭으로 그래프의 트리분해를 형성한다.이렇게 해서 임의의 그래프 G의 트리분해를 화음그래프의 서브그래프로서의 G의 표현으로 볼 수 있다.그래프의 트리 분해는 접합 트리 알고리즘의 접합 트리이기도 합니다.

다른 그래프 클래스와의 관계

서브클래스

구간 그래프는 경로 그래프의 하위 트리의 교차 그래프이며 트리의 특수한 경우입니다.따라서 이들은 화음 그래프의 하위 패밀리입니다.

분할 그래프는 화음 그래프인 동시에 화음 그래프의 보완 그래프입니다.Bender, Richmond & Wormald(1985)는 n이 무한대로 가는 한계에서 분할된 n-vertex 화음 그래프의 비율이 1에 근접한다는 것을 보여주었다.

프톨레마이오스 그래프는 화음 및 거리 유전 그래프입니다.준임계 그래프는 화음 그래프와 코그래프인 프톨레마이오스 그래프의 하위 클래스입니다.블록 그래프는 두 개의 최대 클리어가 공통으로 최대 하나의 정점을 갖는 프톨레마이오스 그래프의 또 다른 하위 클래스입니다.특수한 유형은 풍차 그래프이며, 여기서 공통 정점은 모든 클리크 쌍에 대해 동일합니다.

강한 화음 그래프는 화음이며 유도 하위 그래프로 n-선(n † 3)을 포함하지 않는 그래프이다.여기서 n-선은 G에서 해밀턴 사이클의 가장자리에 인접한 n도 2개의 정점의 집합과 함께 n-vertex 화음 그래프 G이다.

K-트리는 모든 최대 클리크와 최대 클리크 구분자의 ^[10]크기가 동일한 코드 그래프입니다.아폴로 네트워크는 화음 최대 평면 그래프 또는 등가 평면 3 ^[10]트리이다.최대 외평면 그래프는 2-트리의 하위 클래스이므로 화음이기도 합니다.

슈퍼클래스

화음 그래프는 잘 알려진 완전 그래프의 하위 클래스입니다.화음 그래프의 다른 슈퍼클래스는 약화음 그래프, cop-win 그래프, 홀수 홀수 없는 그래프, 짝수 홀 없는 그래프 및 마이니엘 그래프를 포함한다.현상 그래프는 홀수 홀수와 짝수 홀이 없는 그래프입니다(그래프 이론의 구멍 참조).

모든 화음 그래프는 교살 그래프이며, 모든 주변 사이클이 삼각형인 그래프입니다. 왜냐하면 주변 사이클은 유도 사이클의 특별한 경우이기 때문입니다.교살 그래프는 화음 그래프와 최대 평면 그래프의 집단합에 의해 형성될 수 있는 그래프이다.따라서 교살된 그래프에는 최대 평면 ^[11]그래프가 포함됩니다.

화음 완성 및 트리 폭

G가 임의 그래프인 경우 G의 코드 완성도(또는 최소 채우기)는 G를 하위 그래프로 포함하는 코드 그래프입니다.최소 채우기의 매개 변수화된 버전은 고정 매개 변수 추적 가능하며 매개 변수화된 하위 지수 시간에 ^[12]^[13]해결 가능하다.G의 트리 폭은 이 클리크 크기를 최소화하기 위해 선택한 코드 완성도의 최대 클리크 내의 정점 수보다 1개 작습니다.k-트리는 트리 폭을 k보다 큰 수치로 늘리지 않고는 에지를 추가할 수 없는 그래프입니다.따라서 k-트리는 자체 화음 완성이며 화음 그래프의 하위 클래스를 형성한다.화음 완성은 또한 그래프의 ^[14]다른 관련 클래스를 특성화하는 데 사용할 수 있습니다.

메모들

^ 디락(1961년).
^ Berge(1967).
^ 풀커슨 & 그로스(1965).
^ Bodlaender, Fellows & Warnow(1992)
^ Berry, Golumbic & Lipshteyn (2007).
^ Szwarcfiter & Bornstein(1994년).
^ Maffray (2003)
^ 예를 들어 Agnarsson(2003)의 주석 2.5는 이 방법을 잘 알려진 방법이라고 부른다.
^ Peter Bartlett. "Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations" (PDF).
^ ^a ^b 파틸(1986년).
^ Seymour & Weaver(1984년).
^ 카플란, 샤미르, 타잔(1999년).
^ Fomin & Villanger (2013).
^ Parra & Scheffler(1997).

레퍼런스

를 클릭합니다Agnarsson, Geir (2003), "On chordal graphs and their chromatic polynomials", Mathematica Scandinavica, 93 (2): 240–246, doi:10.7146/math.scand.a-14421, MR 2009583.
를 클릭합니다Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi:10.1017/S1446788700023077, MR 0770128.
를 클릭합니다Berge, Claude (1967), "Some Classes of Perfect Graphs", in Harary, Frank (ed.), Graph Theory and Theoretical Physics, Academic Press, pp. 155–165, MR 0232694.
를 클릭합니다Berry, Anne; Golumbic, Martin Charles; Lipshteyn, Marina (2007), "Recognizing chordal probe graphs and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics, 21 (3): 573–591, doi:10.1137/050637091.
를 클릭합니다Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J. (1992), "Two strikes against perfect phylogeny" (PDF), Proc. of 19th International Colloquium on Automata Languages and Programming, Lecture Notes in Computer Science, vol. 623, pp. 273–283, doi:10.1007/3-540-55719-9_80, hdl:1874/16653.
를 클릭합니다Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), "Enumerating and characterizing the perfect elimination orderings of a chordal graph" (PDF), Theoretical Computer Science, 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4.
를 클릭합니다Dirac, G. A. (1961), "On rigid circuit graphs" (PDF), Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25 (1–2): 71–76, doi:10.1007/BF02992776, MR 0130190, S2CID 120608513.
를 클릭합니다Fomin, Fedor V.; Villanger, Yngve (2013), "Subexponential Parameterized Algorithm for Minimum Fill-In", SIAM J. Comput., 42 (6): 2197–2216, arXiv:1104.2230, doi:10.1137/11085390X, S2CID 934546.
를 클릭합니다Fulkerson, D. R.; Gross, O. A. (1965), "Incidence matrices and interval graphs", Pacific J. Math., 15 (3): 835–855, doi:10.2140/pjm.1965.15.835.
를 클릭합니다Gavril, Fănică (1974), "The intersection graphs of subtrees in trees are exactly the chordal graphs", Journal of Combinatorial Theory, Series B, 16: 47–56, doi:10.1016/0095-8956(74)90094-X.
를 클릭합니다Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press.
를 클릭합니다Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing", Theoretical Computer Science, 234 (1–2): 59–84, doi:10.1016/S0304-3975(97)00241-7.
를 클릭합니다Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs", SIAM J. Comput., 28 (5): 1906–1922, doi:10.1137/S0097539796303044.
를 클릭합니다Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1.
를 클릭합니다Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics, 79 (1–3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR 1478250.
를 클릭합니다Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069.
를 클릭합니다Rose, D.; Lueker, George; Tarjan, Robert E. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021, MR 0408312.
를 클릭합니다Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
를 클릭합니다Szwarcfiter, J.L.; Bornstein, C.F. (1994), "Clique graphs of chordal and path graphs", SIAM Journal on Discrete Mathematics, 7 (2): 331–336, doi:10.1137/s0895480191223191, hdl:11422/1497.

외부 링크

그래프 클래스 포함 정보 시스템: 코드 그래프
Weisstein, Eric W. "Chordal Graph". MathWorld.

[dirac-1] 디락(1961년).

[berge-2] Berge(1967).

[FOOTNOTEFulkersonGross1965-3] 풀커슨 & 그로스(1965).

[FOOTNOTEBodlaenderFellowsWarnow1992-4] Bodlaender, Fellows & Warnow(1992)

[FOOTNOTEBerryGolumbicLipshteyn2007-5] Berry, Golumbic & Lipshteyn (2007).

[FOOTNOTESzwarcfiterBornstein1994-6] Szwarcfiter & Bornstein(1994년).

[FOOTNOTEMaffray2003-7] Maffray (2003)

[8] 예를 들어 Agnarsson(2003)의 주석 2.5는 이 방법을 잘 알려진 방법이라고 부른다.

[9] Peter Bartlett. "Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations" (PDF).

[patil86-10] 파틸(1986년).

[FOOTNOTESeymourWeaver1984-11] Seymour & Weaver(1984년).

[FOOTNOTEKaplanShamirTarjan1999-12] 카플란, 샤미르, 타잔(1999년).

[FOOTNOTEFominVillanger2013-13] Fomin & Villanger (2013).

[FOOTNOTEParraScheffler1997-14] Parra & Scheffler(1997).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Search