Многодольный граф
k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (доль). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным.
Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого k > 2 задача определения, является ли данный неокрашенный граф k-дольным, становится NP-полной. Впрочем, в некоторых приложениях теории графов k-дольный граф может быть задан на входе уже раскрашенным; это может случиться, когда множества вершин графа соответствуют разным типам объектов. Например, фолксономии математически моделировались трёхдольными графами, в которых три множества вершин соответствуют пользователям системы, ресурсам, которые подлежат пометке тегами, и собственно тегам
Полный k-дольный граф — это k-дольный граф, такой, что любые две вершины, входящие в разные доли, смежны. Полный k-дольный граф может быть описан нотацией
K v 1 , v 2 , … , v k , {displaystyle K_{v_{1},v_{2},ldots ,v_{k}},}где v 1 , v 2 , … , v k {displaystyle v_{1},v_{2},ldots ,v_{k}} — числа вершин в долях графа. Например, K 2 , 2 , 2 {displaystyle K_{2,2,2}} — полный трёхдольный граф правильного октаэдра, состоящий из трёх независимых множеств, каждое из которых включает в себя две противоположные вершины октаэдра. Полный многодольный граф — это граф, который является полным k-дольным для некоторого k.
Граф Турана — полный многодольный граф, мощности любых двух доль которого отличаются не более чем на 1. Полные многодольные графы — частный случай кографов.
