k -дольный граф — граф , множество вершин которого можно разбить на k независимых множеств ( доль ). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k -дольный граф называется двудольным .

Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого k > 2 задача определения, является ли данный неокрашенный граф k -дольным, становится NP-полной . Впрочем, в некоторых приложениях теории графов k -дольный граф может быть задан на входе уже раскрашенным; это может случиться, когда множества вершин графа соответствуют разным типам объектов. Например, фолксономии математически моделировались трёхдольными графами, в которых три множества вершин соответствуют пользователям системы, ресурсам, которые подлежат пометке тегами , и собственно тегам

Полный k -дольный граф — это k -дольный граф, такой, что любые две вершины, входящие в разные доли, смежны . Полный k -дольный граф может быть описан нотацией

${\displaystyle K_{v_{1},v_{2},\ldots ,v_{k}},}$

где ${\displaystyle v_{1},v_{2},\ldots ,v_{k}}$ — числа вершин в долях графа. Например, ${\displaystyle K_{2,2,2}}$ — полный трёхдольный граф правильного октаэдра , состоящий из трёх независимых множеств, каждое из которых включает в себя две противоположные вершины октаэдра. Полный многодольный граф — это граф, который является полным k -дольным для некоторого k .

Граф Турана — полный многодольный граф, мощности любых двух доль которого отличаются не более чем на 1. Полные многодольные графы — частный случай кографов .

Примечания

Литература

• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М. : Наука , Физматлит , 1990. — 384 с. — ISBN 5-02-013992-0 .
• Gary Chartrand, Ping Zhang. . — CRC Press , 2008. — ISBN 9781584888017 .
• Michael R. Garey, David S. Johnson. . — W. H. Freeman, 1979. — ISBN 0-7167-1045-5 .