군집 그래프

Cluster graph
이 기사는 완전한 그래프의 결합을 해체하는 것에 관한 것이다.정점이 군집화된 그래프는 군집화된 평면성을 참조하십시오.클러스터링 시각화는 클러스터 다이어그램을 참조하십시오.
1, 2, 3, 4, 4, 5, 6 크기의 군집(완전한 하위 그래프)이 있는 군집 그래프

수학의 한 분야인 그래프 이론에서 군집 그래프는 완전한 그래프의 분리 결합으로 형성된 그래프다.마찬가지로 그래프는 3Vx 유도 경로가 없는 경우에만 군집 그래프인데, 이러한 이유로 군집 그래프를 P-자유3 그래프라고도 한다.그것들은 완전한 다중 사이트 그래프와[1] 2-리프 파워의 보완 그래프들이다.[2]군집 그래프는 전이적으로 닫히고, 모든 전이적으로 닫힌 비방향 그래프는 군집 그래프다.[3]

관련 그래프 클래스

모든 군집 그래프는 블록 그래프, cograph, 그리고 발톱이 없는 그래프다.[1]클러스터 그래프의 모든 최대 독립 집합은 각 군집으로부터 단일 꼭지점을 선택하므로 그러한 집합의 크기는 항상 군집 수와 동일하다. 모든 최대 독립 집합의 크기가 같기 때문에 군집 그래프는 잘 가려진다.투란 그래프는 클러스터 그래프의 그래프를 보완한 것으로, 크기가 같거나 거의 동일한 모든 하위 그래프를 포함한다.로컬로 군집화된 그래프(모든 이웃이 군집 그래프인 그래프)는 다이아몬드가 없는 그래프로서 군집 그래프를 포함하는 다른 그래프 제품군이다.

군집 그래프가 모두 같은 크기의 군집형 그래프로 형성될 때 전체 그래프는 동질 그래프로서, 유도 하위 그래프 두 개 사이의 모든 이형성이 전체 그래프의 자동형으로 확장될 수 있다는 것을 의미한다.단 두 가지 예외를 제외하고, 군집 그래프와 그 보완물은 유일한 유한 동종 그래프이며,[4] 무한 군집 그래프도 셀 수 없이 무한 동종 그래프의 적은 수의 다른 유형 중 하나를 형성한다.[5]

계산 문제

그래프의 하위 색인은 그 정점을 유도 군집 그래프로 분할하는 것이다.따라서 군집 그래프는 정확히 1번 색소하수의 그래프가 된다.[6]

그래프를 클러스터 그래프로 변환하기 위해 그래프에서 추가하거나 제거할 작은 에지 집합을 찾는 연산 문제를 클러스터 편집이라고 한다.그것은 NP-완전하지만[7] 고정 매개변수-추적 가능하다.[8]

참조

  1. ^ a b 2016-06-26에 접속한 클러스터 그래프, 그래프 클래스의 정보 시스템 및 포함 정보.
  2. ^ Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms, 42: 69–108, doi:10.1006/jagm.2001.1195.
  3. ^ McColl, W. F.; Noshita, K. (1986), "On the number of edges in the transitive closure of a graph", Discrete Applied Mathematics, 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR 0856101
  4. ^ Gardiner, A. (1976), "Homogeneous graphs", Journal of Combinatorial Theory, Series B, 20 (1): 94–102, doi:10.1016/0095-8956(76)90072-1, MR 0419293.
  5. ^ Lachlan, A. H.; Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society, 262 (1): 51–94, doi:10.2307/1999974, MR 0583847.
  6. ^ Albertson, M. O.; Jamison, R. E.; Hedetniemi, S. T.; Locke, S. C. (1989), "The subchromatic number of a graph", Discrete Mathematics, 74 (1–2): 33–49, doi:10.1016/0012-365X(89)90196-9.
  7. ^ Shamir, Ron; Sharan, Roded; Tsur, Dekel (2004), "Cluster graph modification problems", Discrete Applied Mathematics, 144 (1–2): 173–182, doi:10.1016/j.dam.2004.01.007, MR 2095392.
  8. ^ Böcker, Sebastian; Baumbach, Jan (2013), "Cluster editing", The nature of computation, Lecture Notes in Comput. Sci., vol. 7921, Springer, Heidelberg, pp. 33–44, doi:10.1007/978-3-642-39053-1_5, MR 3102002.