В теории графов , части математики, k -дольный граф — это граф , вершины которого разделены (или могут быть разделены ) на k различных независимых множеств . Эквивалентно, это граф, который можно раскрасить в k цветов, так что никакие две конечные точки ребра не будут иметь одинаковый цвет. При k = 2 это двудольные графы , а при k = 3 они называются трехдольными графами .
Двудольные графы могут быть распознаны за полиномиальное время , но для любого k > 2 это NP-полная задача , если задан неокрашенный граф, чтобы проверить, является ли он k -дольным. [1] Однако в некоторых приложениях теории графов k -дольный граф может быть задан в качестве входных данных для вычисления с уже определенной раскраской; это может произойти, когда наборы вершин в графе представляют различные типы объектов. Например, фолксономии были смоделированы математически с помощью трехдольных графов, в которых три набора вершин в графе представляют пользователей системы, ресурсы, которые пользователи помечают, и теги, которые пользователи применили к ресурсам. [2]
Полный k -дольный граф — это k -дольный граф, в котором между каждой парой вершин из разных независимых множеств есть ребро. Эти графы описываются с помощью нотации с заглавной буквой K , индексированной последовательностью размеров каждого множества в разбиении. Например, K 2,2,2 — это полный трехдольный граф правильного октаэдра , который можно разбить на три независимых множества, каждое из которых состоит из двух противоположных вершин. Полный многодольный граф — это граф, который является полным k -дольным для некоторого k . [3] Графы Турана являются особым случаем полных многодольных графов, в которых каждые два независимых множества отличаются по размеру не более чем на одну вершину. Полные k -дольные графы, полные многодольные графы и их дополнительные графы , кластерные графы , являются особыми случаями кографов и могут быть распознаны за полиномиальное время, даже если разбиение не указано как часть входных данных.