Многодольный граф
k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (долей). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным[1].
Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого k > 2 задача определения, является ли данный неокрашенный граф k-дольным, становится NP-полной[2]. Впрочем, в некоторых приложениях теории графов k-дольный граф может быть задан на входе уже раскрашенным; это может случиться, когда множества вершин графа соответствуют разным типам объектов. Например, фолксономии математически моделировались трёхдольными графами, в которых три множества вершин соответствуют пользователям системы, ресурсам, которые подлежат пометке тегами, и собственно тегам[3]
Полный k-дольный граф — это k-дольный граф, такой, что любые две вершины, входящие в разные доли, смежны[1]. Полный k-дольный граф может быть описан нотацией
где — числа вершин в долях графа. Например, — полный трёхдольный граф правильного октаэдра, состоящий из трёх независимых множеств, каждое из которых включает в себя две противоположные вершины октаэдра. Полный многодольный граф — это граф, который является полным k-дольным для некоторого k[4].
Граф Турана — полный многодольный граф, мощности любых двух доль которого отличаются не более чем на 1. Полные многодольные графы — частный случай кографов.
Примечания[править | править код]
- ↑ 1 2 Лекции по теории графов, 1990, с. 11.
- ↑ Computers and Intractability, 1979.
- ↑ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111—114
- ↑ Chromatic Graph Theory, 2008, p. 41.
Литература[править | править код]
- В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М.: Наука, Физматлит, 1990. — 384 с. — ISBN 5-02-013992-0.
- Gary Chartrand, Ping Zhang. Chromatic Graph Theory. — CRC Press, 2008. — ISBN 9781584888017.
- Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5.