вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин Из Википедии, свободной энциклопедии
Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
Полный двудольный граф — это такой двудольный граф, что для любых двух вершин и , является ребром в . Полный двудольный граф с долями размера и обозначается как .
Графы называются звёздами, все полные двудольные графы, являющиеся деревьями, являются звёздами.
Граф иногда называется «коммунальным графом», название восходит к классической задаче «домики и колодцы», в современной интерпретации использующей «коммунальную» формулировку (подключить три домика к водо-, электро- и газоснабжению без пересечений линий на плоскости); задача неразрешима ввиду непланарности графа .
Задача поиска для данного двудольного графа полного двудольного подграфа с заданным параметром NP-полна.