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