Составной граф - Multipartite graph - Wikipedia

В теория графов, часть математики, k-дольный граф - граф, вершины которого разбиты или могут быть разбиты на k разные независимые множества. Точно так же это график, который можно цветной с k цвета, так что никакие две конечные точки ребра не имеют одинакового цвета. Когда k = 2 это двудольные графы, и когда k = 3 они называются трехсторонние графы.

Двудольные графы могут быть распознаны за полиномиальное время, но для любого k > 2это НП-полный, учитывая неокрашенный график, чтобы проверить, k-частный.[1]Однако в некоторых приложениях теории графов k-дольный граф может быть предоставлен в качестве входных данных для вычисления с уже определенной его окраской; это может произойти, когда наборы вершин в графе представляют различные типы объектов. Например, фольксономии были смоделированы математически трехчастными графами, в которых три набора вершин в графе представляют пользователей системы, ресурсы, которые пользователи помечают, и теги, которые пользователи применили к ресурсам.[2]

Пример завершен k-дольные графы
K2,2,2K3,3,3K2,2,2,2
Сложный трехчастный граф octahedron.svg
График октаэдр		3-генерализованный-3-ортоплекс-tripartite.svg
График сложный обобщенный октаэдр		Сложный многодольный граф 16-cell.svg
График 16 ячеек

А полный k-дольный граф это k-дольный граф, в котором есть ребро между каждой парой вершин из разных независимых множеств. Эти графики обозначаются обозначениями с большой буквы. K индексируется последовательностью размеров каждого набора в разделе. Например, K2,2,2 полный трехчастный граф правильный октаэдр, которые можно разбить на три независимых множества, каждое из которых состоит из двух противоположных вершин. А полный многодольный граф это полный граф k-частный для некоторых k.[3]В Графики Турана являются частным случаем полных многодольных графов, в которых каждые два независимых набора отличаются по размеру не более чем на одну вершину. k-дольные графы, полные многодольные графы и их дополнить графы, то кластерные графы, являются частными случаями кографы, и может быть распознан за полиномиальное время, даже если раздел не указан как часть ввода.

Рекомендации

  1. ^ Гарей, М.; Джонсон, Д.С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, GT4, ISBN  0-7167-1045-5.
  2. ^ Хотхо, Андреас; Jäschke, Роберт; Шмитц, Кристоф; Штумме, Герд (2006), "FolkRank: алгоритм ранжирования фольксономий", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Хильдесхайм, 9-11 октября 2006 г., стр. 111–114.
  3. ^ Чартран, Гэри; Чжан, Пин (2008), Теория хроматических графов, CRC Press, стр. 41, ISBN  9781584888017.