Многодольный граф
k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (доль). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным[1].
Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого k > 2 задача определения, является ли данный неокрашенный граф k-дольным, становится NP-полной[2]. Впрочем, в некоторых приложениях теории графов k-дольный граф может быть задан на входе уже раскрашенным; это может случиться, когда множества вершин графа соответствуют разным типам объектов. Например, фолксономии математически моделировались трёхдольными графами, в которых три множества вершин соответствуют пользователям системы, ресурсам, которые подлежат пометке тегами, и собственно тегам[3]
Полный k-дольный граф — это k-дольный граф, такой, что любые две вершины, входящие в разные доли, смежны[1]. Полный k-дольный граф может быть описан нотацией
- <math>K_{v_1,v_2,\ldots,v_k},</math>
где <math>v_1,v_2,\ldots,v_k</math> — числа вершин в долях графа. Например, <math>K_{2,2,2}</math> — полный трёхдольный граф правильного октаэдра, состоящий из трёх независимых множеств, каждое из которых включает в себя две противоположные вершины октаэдра. Полный многодольный граф — это граф, который является полным k-дольным для некоторого k[4].
Граф Турана — полный многодольный граф, мощности любых двух доль которого отличаются не более чем на 1. Полные многодольные графы — частный случай кографов.
Напишите отзыв о статье "Многодольный граф"
Примечания
- ↑ 1 2 Лекции по теории графов, 1990, с. 11.
- ↑ Computers and Intractability, 1979.
- ↑ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph & Stumme, Gerd (2006), [opus.bsz-bw.de/ubhi/volltexte/2011/39/ "FolkRank : A Ranking Algorithm for Folksonomies"], LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, сс. 111–114, <opus.bsz-bw.de/ubhi/volltexte/2011/39/>
- ↑ Chromatic Graph Theory, 2008, p. 41.
Литература
- В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М.: Наука, Физматлит, 1990. — 384 с. — ISBN 5-02-013992-0.
- Gary Chartrand, Ping Zhang. [books.google.com/books?id=_l4CJq46MXwC&pg=PA41 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.
Отрывок, характеризующий Многодольный граф
– Ну, а наследники мои? – сказал Пьер. – Вдруг я женюсь… Ведь может случиться, – прибавил он с невольной улыбкой.– И осмеливаюсь доложить: хорошее дело, ваше сиятельство.
«Как он думает это легко, – подумал Пьер. – Он не знает, как это страшно, как опасно. Слишком рано или слишком поздно… Страшно!»
– Как же изволите приказать? Завтра изволите ехать? – спросил Савельич.
– Нет; я немножко отложу. Я тогда скажу. Ты меня извини за хлопоты, – сказал Пьер и, глядя на улыбку Савельича, подумал: «Как странно, однако, что он не знает, что теперь нет никакого Петербурга и что прежде всего надо, чтоб решилось то. Впрочем, он, верно, знает, но только притворяется. Поговорить с ним? Как он думает? – подумал Пьер. – Нет, после когда нибудь».
За завтраком Пьер сообщил княжне, что он был вчера у княжны Марьи и застал там, – можете себе представить кого? – Натали Ростову.
Княжна сделала вид, что она в этом известии не видит ничего более необыкновенного, как в том, что Пьер видел Анну Семеновну.
– Вы ее знаете? – спросил Пьер.
– Я видела княжну, – отвечала она. – Я слышала, что ее сватали за молодого Ростова. Это было бы очень хорошо для Ростовых; говорят, они совсем разорились.
– Нет, Ростову вы знаете?
– Слышала тогда только про эту историю. Очень жалко.
«Нет, она не понимает или притворяется, – подумал Пьер. – Лучше тоже не говорить ей».
Княжна также приготавливала провизию на дорогу Пьеру.
«Как они добры все, – думал Пьер, – что они теперь, когда уж наверное им это не может быть более интересно, занимаются всем этим. И все для меня; вот что удивительно».
В этот же день к Пьеру приехал полицеймейстер с предложением прислать доверенного в Грановитую палату для приема вещей, раздаваемых нынче владельцам.
«Вот и этот тоже, – думал Пьер, глядя в лицо полицеймейстера, – какой славный, красивый офицер и как добр! Теперь занимается такими пустяками. А еще говорят, что он не честен и пользуется. Какой вздор! А впрочем, отчего же ему и не пользоваться? Он так и воспитан. И все так делают. А такое приятное, доброе лицо, и улыбается, глядя на меня».
Пьер поехал обедать к княжне Марье.
Проезжая по улицам между пожарищами домов, он удивлялся красоте этих развалин. Печные трубы домов, отвалившиеся стены, живописно напоминая Рейн и Колизей, тянулись, скрывая друг друга, по обгорелым кварталам. Встречавшиеся извозчики и ездоки, плотники, рубившие срубы, торговки и лавочники, все с веселыми, сияющими лицами, взглядывали на Пьера и говорили как будто: «А, вот он! Посмотрим, что выйдет из этого».
При входе в дом княжны Марьи на Пьера нашло сомнение в справедливости того, что он был здесь вчера, виделся с Наташей и говорил с ней. «Может быть, это я выдумал. Может быть, я войду и никого не увижу». Но не успел он вступить в комнату, как уже во всем существе своем, по мгновенному лишению своей свободы, он почувствовал ее присутствие. Она была в том же черном платье с мягкими складками и так же причесана, как и вчера, но она была совсем другая. Если б она была такою вчера, когда он вошел в комнату, он бы не мог ни на мгновение не узнать ее.