В теории графов , которая является частью математики, k -раздельный граф - это граф, вершины которого разбиты или могут быть разбиты на k различных независимых множеств . Эквивалентно, это график , который может быть окрашен с K цветов, так что никакие две конечные точки кромки не имеют такой же цвет. При k = 2 это двудольные графы , а при k = 3 они называются трехдольными графами .
Двудольные графы могут быть распознаны за полиномиальное время, но для любого k > 2 он является NP-полным , учитывая неокрашенный граф, чтобы проверить, является ли он k -раздельным. [1] Однако в некоторых приложениях теории графов k -раздельный граф может быть задан в качестве входных данных для вычисления с уже определенной его окраской; это может произойти, когда наборы вершин в графе представляют различные типы объектов. Например, фолксономии были смоделированы математически трехчастными графами, в которых три набора вершин в графе представляют пользователей системы, ресурсы, которые пользователи отмечают тегами, и теги, которые пользователи применяют к ресурсам. [2]
| К 2,2,2 | К 3,3,3 | К 2,2,2,2 |
|---|---|---|
 График октаэдра |  График сложного обобщенного октаэдра |  График 16 ячеек |
Полный к -дольному графу является к -дольным графам , в котором существует ребро между каждой парой вершин из различных независимых множеств. Эти графы описываются обозначениями с прописной буквой K, в нижнем индексе которых указывается последовательность размеров каждого набора в разделе. Например, K 2,2,2 - это полный трехчастный граф правильного октаэдра , который можно разбить на три независимых множества, каждое из которых состоит из двух противоположных вершин. Полный многодольный граф представляет собой график , который является полным к -дольному для некоторых к . [3] графы ТУРАНявляются частным случаем полных многодольных графов, в которых каждые два независимых множества отличаются по размеру не более чем на одну вершину. Полные k -раздельные графы, полные многодольные графы и их дополнительные графы , кластерные графы , являются частными случаями кографов и могут быть распознаны за полиномиальное время, даже если разбиение не предоставляется как часть входных данных.
Ссылки [ править ]
- ^ Garey, MR ; Джонсон, Д.С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, GT4 , ISBN 0-7167-1045-5.
- ^ Хотхо, Андреас; Яшке, Роберт; Шмитц, Кристоф; Штумме, Герд (2006), «FolkRank: алгоритм ранжирования фольксономий», LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Хильдесхайм, 9-11 октября 2006 г. , стр. 111–114.
- ^ Chartrand, Гэри ; Чжан, Пинг (2008), Теория хроматических графов , CRC Press, стр. 41, ISBN 9781584888017.
