다중분포그래프

Multipartite graph

수학의 일부인 그래프 이론에서, k-partite 그래프는 정점이 k개의 서로 다른 독립된 집합으로 분할되거나 분할될 수 있는 그래프를 의미한다.마찬가지로 가장자리의 두 끝점이 동일한 색을 가지지 않도록 k 색상으로 색칠할 수 있는 그래프다.k = 2일 때 이것들은 초당적 그래프이고, k = 3일 때 3분위 그래프라고 불린다.

초당적 그래프는 다항 시간 내에 인식될 수 있지만, k > 2의 경우, 그것이 k-partite인지 여부를 시험하기 위해 무색인 그래프를 주어 NP-완전하다.[1]그러나, 그래프 이론의 일부 적용에서, k-partite 그래프는 색상이 이미 결정된 계산에 대한 입력으로 제공될 수 있다. 이것은 그래프에서 정점 집합이 다른 유형의 물체를 나타낼 때 발생할 수 있다.예를 들어, 포크노믹스는 그래프의 세 가지 꼭지점 집합이 시스템의 사용자, 사용자가 태그하는 리소스, 그리고 사용자가 리소스에 적용한 태그를 나타내는 3자 그래프에 의해 수학적으로 모델링되었다.[2]

전체 k-partite 그래프 예제
K2,2,2 K3,3,3 K2,2,2,2
Complex tripartite graph octahedron.svg
팔면체 그래프 		3-generalized-3-orthoplex-tripartite.svg
복합 일반화 옥타헤드론 그래프 		Complex multipartite graph 16-cell.svg
16-셀 그래프

완전한 k-partite 그래프는 서로 다른 독립된 집합의 모든 꼭지점 쌍 사이에 에지가 있는 k-partite 그래프다.이러한 그래프는 대문자 K를 칸막이에 있는 각 세트의 크기 순서로 첨자화한 표기법으로 설명된다.예를 들어, K는2,2,2 정규 팔면체의 완전한 삼분법 그래프로, 각각 정점 두 개로 구성된 세 개의 독립된 세트로 분할할 수 있다.전체 다중 사이트 그래프는 일부 k에 대해 완전한 k-partite를 나타내는 그래프다.[3]투란 그래프는 각각의 독립된 두 집합이 최대 하나의 꼭지점마다 크기가 다른 완전한 다중 사이트 그래프의 특별한 경우다.전체 k-partite 그래프, 전체 다중 사이트 그래프 및 그 보완 그래프인 군집 그래프는 cograph의 특수한 경우로서, 입력의 일부로 파티션이 제공되지 않는 경우에도 다항식 시간으로 인식할 수 있다.

참조

  1. ^ Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, ISBN 0-7167-1045-5.
  2. ^ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111–114.
  3. ^ Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, CRC Press, p. 41, ISBN 9781584888017.