클리크(그래프 이론)

Clique (graph theory)
그 외의 사용법에 대해서는, 「Clique」(동음이의)를 참조해 주세요.
를 포함한 그래프
  • 23 × 1개의 클립(정점),
  • 42 × 2 슬롯 클리(엣지),
  • 19 × 3각형 클리프(밝고 진한 파란색 삼각형) 및
  • 2 × 4각 클리(진청색 영역)
11개의 밝은 파란색 삼각형은 최대의 클리프를 형성합니다.2개의 짙은 파란색 4개의 클리크는 최대값과 최대값이며 그래프의 클리크 번호는 4입니다.

그래프 이론의 수학적 영역에서 클리크(/ˈkliːk/ 또는 /kklkk/)는 클리크 내의 서로 다른 두 개의 정점이 인접하도록 방향성이 없는 그래프의 정점의 서브셋입니다.즉, G(\ G의 클리크는 완전한G(\G)의 유도 서브그래프입니다.클리크는 그래프 이론의 기본 개념 중 하나이며 많은 다른 수학 문제 및 그래프 구성에 사용됩니다.컴퓨터 과학에서도 클리크가 연구되어 왔습니다.그래프에 주어진 크기의 클리크가 있는지 확인하는 작업(클리크 문제)은 NP-완전하지만, 이 경도 결과에도 불구하고 클리어를 찾기 위한 많은 알고리즘이 연구되었습니다.

완전한 서브그래프에 대한 연구는 적어도 Erdss & Szekeres(1935)[1]에 의한 램지 이론의 그래프 이론의 재구성으로 거슬러 올라가지만, clique라는 용어는 소셜 네트워크에서 완전한 서브그래프를 사용하여 사람들, 즉 서로를 아는 사람들의 그룹을 모델링한 Luce & Perry(1949)에서 유래했다.집단은 과학, 특히 생물정보학에서 다른 많은 응용 분야를 가지고 있다.

정의들

무방향 그래프 G = (V, E)에서 clique, C는 각각의 다른 두 정점이 인접하도록 정점 C δ V의 부분 집합이다.이는 C에 의해 유도된 G의 유도 서브그래프가 완전 그래프라는 조건과 같다.경우에 따라서는 clique라는 용어는 서브그래프를 직접 가리킬 수도 있습니다.

최대 클리크는 인접한 정점을 하나 더 포함시켜 확장할 수 없는 클리크입니다.즉, 더 큰 클리크의 정점 집합 내에 독점적으로 존재하지 않는 클리크입니다.일부 저자는 최대값이 요구되는 방식으로 클리어를 정의하고 최대값이 아닌 전체 하위 그래프에 대해 다른 용어를 사용합니다.

그래프의 최대 클리크 G는 더 많은 정점이 있는 클리크가 존재하지 않도록 하는 클리크입니다.또한 그래프 G의 클리크 수 θ(G)는 G의 최대 클리크 내의 정점 수이다.

G의 교차로 번호는 G의 모든 모서리를 모두 커버하는 최소 클리프 수입니다.

그래프 G의 clique cover number는 그래프의 꼭지점 V 집합을 포함하는 G의 최소 clique 수입니다.

그래프의 최대 클리크 가로 방향은 그래프의 각 최대 클리크가 부분 [2]집합에 적어도 하나의 정점을 포함하는 속성을 가진 정점의 부분 집합입니다.

clique의 반대는 모든 clique가 보완 그래프의 독립 세트에 대응한다는 점에서 독립 집합입니다.이 클리크 커버 문제는 그래프에 있는 모든 정점을 포함하는 클리크를 가능한 한 적게 찾는 것과 관련이 있습니다.

관련 개념은 완전한 초당 하위 그래프인 바이클라이프입니다.그래프의 초당 치수는 그래프의 모든 모서리를 커버하는 데 필요한 최소 바이클리크 수입니다.

수학

클리어에 관한 수학적 결과는 다음과 같다.

  • 투란의 정리는 조밀한 [3]그래프에서 파벌의 크기에 하한을 부여한다.그래프에 모서리가 충분히 있는 경우 큰 클리크를 포함해야 합니다.예를 들어 의 꼭지점 " 2 " 2 " 2 "보다 큰 "n 2 " " " " { \ left \ \ \ { } { \ \ \ frcdeil { n { n { n } 엣지를 모든 그래프에는 3개의 클리텍스를 포함해야 합니다.
  • 램지의 정리는 모든 그래프 또는 그 보완 그래프가 최소한 로그 수 이상의 [4]정점을 가진 패거리를 포함하고 있다고 말한다.
  • Moon & Moser(1965)의 결과에 따르면 3n개의 정점이 있는 그래프는 최대n 3개의 클리어를 가질 수 있다.이 경계를 충족하는 그래프는 달-모저 그래프3,3,... K로, 투란의 정리에서 극단 사례로 발생하는 투란 그래프의 특수한 경우이다.
  • 아직 입증되지 않은 Hadwiger의 추측은 그래프에서 가장 큰 부류의 크기(Hadwiger 수)와 그 색수를 연관시킨다.
  • Erdss-Faber-Lovasz 추측은 그래프 색상과 클리어에 관련된 또 다른 증명되지 않은 진술이다.

그래프에는 다음과 같은 중요한 클래스가 정의되거나 그 특색이 있습니다.

  • 클러스터 그래프는 연결된 구성 요소가 클리크인 그래프입니다.
  • 블록 그래프는 쌍접속 컴포넌트가 클리크인 그래프입니다.
  • 화음 그래프는 정점을 완전 소거 순서로 정렬할 수 있는 그래프이며, 순서에서 v보다 늦게 오는 각 정점 v의 인접이 clique를 형성하도록 정렬할 수 있다.
  • 코그래프는 모든 유도 하위 그래프가 단일 정점에서 최대 독립 집합과 교차하는 특성을 갖는 그래프입니다.
  • 구간 그래프는 각 정점 v에 대해 v를 포함한 클리어가 순서대로 나열되도록 최대 클리어의 순서를 매길 수 있는 그래프이다.
  • 선 그래프는 각 정점이 커버 내의 정확히 두 개의 클리어에 속하도록 모서리를 에지 분리 클리어로 커버할 수 있는 그래프입니다.
  • 완전 그래프는 각 유도 서브그래프에서 클리크 번호가 색수와 동일한 그래프입니다.
  • 분할 그래프는 일부 집단에서 모든 가장자리의 끝점을 하나 이상 포함하는 그래프입니다.
  • 삼각형이 없는 그래프는 정점과 모서리 외에는 클리프가 없는 그래프입니다.

또한, 다른 많은 수학적 구성에는 그래프의 클리프가 포함된다.그 중.

  • 그래프 G의 clike complex는 G의 모든 clique에 대해 simplex를 갖는 추상적인 단순 복합 X(G)이다.
  • 심플렉스 그래프는 그래프 G 내의 각 클리크마다 정점을 갖는 무방향 그래프 δ(G)와 단일 정점으로 다른 두 클리크를 연결하는 엣지이다.이것은 중앙값 그래프의 한 예이며 그래프 클리어의 중앙값 대수와 관련되어 있습니다.3개의 클리 A, B, C의 중앙값 m(A, B, C)는 정점이 A, B 및 [5]C의 적어도2개의 클리크에 속하는 클리크입니다.
  • clique-sum은 두 그래프를 공유 clique에 따라 병합하여 결합하는 방법입니다.
  • 클리크 폭(Clique-width)은 분리된 결합, 레이블 다시 만들기 연산 및 주어진 레이블로 모든 정점 쌍을 연결하는 연산으로부터 그래프를 구축하는 데 필요한 개별 정점 레이블의 최소 수 측면에서 그래프의 복잡성에 대한 개념이다.clique-width가 1인 그래프는 정확히 clique의 분리된 결합입니다.
  • 그래프의 교차 번호는 모든 그래프의 모서리를 커버하는 데 필요한 최소 클리프 수입니다.
  • 그래프의 클리크 그래프는 최대 클리크의 교차 그래프입니다.

완전한 하위 그래프와 밀접하게 관련된 개념은 완전한 그래프와 완전한 그래프 부차분할이다.특히, 쿠라토프스키의 정리와 바그너의 정리는 각각 금지된 완전하고 완전한 부분분할과 부차분할로 평면 그래프를 특징짓는다.

컴퓨터 공학

주요 기사: Clique 문제

컴퓨터 과학에서 clique 문제는 주어진 그래프에서 최대 clique 또는 모든 clique를 찾는 계산 문제입니다.이것은 Karp의 21개의 NP-완전 문제 [6]중 하나인 NP-완전 문제입니다.또한 고정 매개 변수를 다루기 어렵고 근사하기 어렵습니다.그럼에도 불구하고, 클리어를 계산하기 위한 많은 알고리즘이 (브론-커보시 알고리즘과 같은) 지수 시간에 실행되거나 다항 시간에 문제를 해결할 수 있는 평면 그래프 또는 완벽한 그래프와 같은 그래프 계열에 특화되어 개발되었다.

적용들

그래프 이론적 용법에서 "클리크"라는 단어는 소셜 네트워크에서 완전한 서브그래프를 사용하여 클리(서로 아는 사람들의 그룹)를 모델링한 Luce & Perry(1949)의 연구에서 유래했다.Festinger(1949)가 덜 기술적인 용어를 사용한 기사에서 동일한 정의를 사용했다.두 작품 모두 매트릭스를 사용하여 소셜 네트워크에서 클리어를 찾아내는 것을 다루고 있습니다.이론적으로 소셜 클리프를 모델링하기 위한 지속적인 노력은 예를 참조하십시오.알바(1973년), 페이(1974년), 도리언&우다드(1994년).

생물정보학과는 많은 다른 문제들이 집단을 이용하여 모델링되었다.예를 들어, Ben-Dor, 샤미르 &, Yakhini(1999년)모델은 문제의 군집화 유전자 표현 자료 중 하나로 메시아의 최소 숫자의 변화가 필요하기 그래프를 설명하는 데이터를 그래프를 형성되는 연결되지 않은 노조의 파벌, 타나이, Sharan &, 샤미르(2002년)을 논의하기 비슷한 biclustering 문제 표현 자료에서. 는 하루에 500파운드클러스터는 패거리여야 합니다.스기하라(1984년)는, 클리어를 사용해 먹이 사슬의 생태적 틈새를 모델화한다.Day & Sankoff(1986)는 진화목의 유추 문제를 종의 정점 특성으로 갖는 그래프에서 최대 클리프(clipse)를 찾는 문제 중 하나로 설명한다. 두 개의 정점은 두 문자를 결합한 완벽한 계통 발생이 존재하는 경우 가장자리를 공유한다.Samudrala & Moult(1998) 모델 단백질 구조 예측은 단백질의 서브유닛의 위치를 정점으로 하는 그래프에서 클리프(cliffe)를 찾는 문제였다.또한 Spirin & Mirny(2003)는 단백질-단백질 상호 작용 네트워크에서 클리어를 탐색함으로써 서로 밀접하게 상호작용하고 클러스터 외부의 단백질과 거의 상호작용하지 않는 단백질 클러스터를 발견했다.검정력 그래프 분석은 이러한 네트워크 내에서 집단 및 관련 구조를 찾아 복잡한 생물학적 네트워크를 단순화하는 방법입니다.

전기공학에서는 Prihar(1956년)는 통신 네트워크를 분석하기 위해 clicle을 사용하고, Paull & Unger(1959년)는 부분적으로 특정된 부울 함수를 계산하기 위한 효율적인 회로를 설계하기 위해 사용합니다.자동 테스트 패턴 생성에도 클리크가 사용되고 있습니다.가능한 장애의 비호환성 그래프에 있는 큰 클리크는 테스트 [7]세트의 크기를 하한으로 합니다.Cong & Smith(1993)는 작은 서브유닛에 대한 전자회로의 계층적 분할을 찾는 데 있어서 clicle의 적용을 설명한다.

화학에서는 로즈 외 (2003) 대상 구조와 높은 유사성을 갖는 화학 데이터베이스의 화학물질을 기술하기 위해 집단을 사용한다.Kuhl, Crippen & Friesen(1983)은 두 화학물질이 서로 결합하는 위치를 모델링하기 위해 집단을 사용합니다.

「 」를 참조해 주세요.

메모들

  1. ^ 금지된 완전하고 완전한 초당 하위 그래프로 평면 그래프를 특징짓는 쿠라토스키(1930)의 초기 연구는 원래 그래프 이론이 아닌 위상학적 용어로 표현되었다.
  2. ^ Chang, Kloks & Lee(2001).
  3. ^ 투란(1941년).
  4. ^ Graham, Rothschild & Spencer(1990).
  5. ^ Barthélemy, Leclerc & Monjardet(1986), 200페이지.
  6. ^ 카르프(1972년).
  7. ^ Hamzaoglu & Patel(1998).

레퍼런스

  • 를 클릭합니다Alba, Richard D. (1973), "A graph-theoretic definition of a sociometric clique" (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080/0022250X.1973.9989826.
  • 를 클릭합니다Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188, S2CID 6092438.
  • 를 클릭합니다Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), "Clustering gene expression patterns.", Journal of Computational Biology, 6 (3–4): 281–297, CiteSeerX 10.1.1.34.5341, doi:10.1089/106652799318274, PMID 10582567.
  • 를 클릭합니다Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", Graph-theoretic concepts in computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, pp. 32–43, doi:10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, MR 1905299.
  • 를 클릭합니다Cong, J.; Smith, M. (1993), "A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design", Proc. 30th International Design Automation Conference, pp. 755–760, CiteSeerX 10.1.1.32.735, doi:10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
  • 를 클릭합니다Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
  • 를 클릭합니다Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks", Social Networks, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2.
  • 를 클릭합니다Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry" (PDF), Compositio Mathematica, 2: 463–470.
  • 를 클릭합니다Festinger, Leon (1949), "The analysis of sociograms using matrix algebra", Human Relations, 2 (2): 153–158, doi:10.1177/001872674900200205, S2CID 143609308.
  • 를 클릭합니다Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory, New York: John Wiley and Sons, ISBN 978-0-471-50046-9.
  • 를 클릭합니다Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 978-1581130089, S2CID 12258606.
  • 를 클릭합니다Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-13.
  • 를 클릭합니다Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105, S2CID 122923018.
  • 를 클릭합니다Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en Topologie" (PDF), Fundamenta Mathematicae (in French), 15: 271–283, doi:10.4064/fm-15-1-271-283.
  • 를 클릭합니다Luce, R. Duncan; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika, 14 (2): 95–116, doi:10.1007/BF02289146, hdl:10.1007/BF02289146, PMID 18152948, S2CID 16186758.
  • 를 클릭합니다Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577.
  • 를 클릭합니다Paull, M. C.; Unger, S. H. (1959), "Minimizing the number of states in incompletely specified sequential switching functions", IRE Transactions on Electronic Computers, EC-8 (3): 356–367, doi:10.1109/TEC.1959.5222697.
  • 를 클릭합니다Peay, Edmund R. (1974), "Hierarchical clique structures", Sociometry, 37 (1): 54–65, doi:10.2307/2786466, JSTOR 2786466.
  • 를 클릭합니다Prihar, Z. (1956), "Topological properties of telecommunications networks", Proceedings of the IRE, 44 (7): 927–933, doi:10.1109/JRPROC.1956.275149, S2CID 51654879.
  • 를 클릭합니다Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
  • 를 클릭합니다Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, CiteSeerX 10.1.1.64.8918, doi:10.1006/jmbi.1998.1689, PMID 9636717.
  • 를 클릭합니다Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
  • 를 클릭합니다Sugihara, George (1984), "Graph theory, homology and food webs", in Levin, Simon A. (ed.), Population Biology, Proc. Symp. Appl. Math., vol. 30, pp. 83–101.
  • 를 클릭합니다Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), "Discovering statistically significant biclusters in gene expression data", Bioinformatics, 18 (Suppl. 1): S136–S144, doi:10.1093/bioinformatics/18.suppl_1.S136, PMID 12169541.
  • Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in Hungarian), 48: 436–452

외부 링크