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