Полный двудольный граф
редактировать
Двудольный граф, в котором каждая вершина первого набора соединена с каждой вершиной второго набора
Полный двудольный граф |
---|
Полный двудольный граф с m = 5 и n = 3 |
Вершины | n + m |
---|
Ребра | mn |
---|
Радиус | |
---|
Диаметр | |
---|
Обхват | |
---|
Автоморфизмы | |
---|
Хроматическое число | 2 |
---|
Хроматический индекс | max {m, n} |
---|
Спектр | |
---|
Обозначение | |
---|
Таблица графов и параметров |
В поле Mathematical в теории графов, полный двудольный граф или biclique - это особый вид двудольный граф, где каждая вершина первого набора связана с каждой вершиной второго набора.
Сама теория графов обычно начинается с Леонарда Работа Эйлера 1736 года над Семью мостами Кенигсберга. Однако рисунки полных двудольных графов были напечатаны еще в 1669 году в связи с изданием работ Рамона Лулля под редакцией Афанасия Кирхера. Сам Ллулл сделал аналогичные рисунки полных графиков тремя веками ранее.
Содержание
- 1 Определение
- 2 Примеры
- 3 Свойства
- 4 См. Также
- 5 Ссылки
Определение
A полный двудольный граф - это граф, вершины которого можно разбить на два подмножества V 1 и V 2, так что ни одно ребро не имеет обоих концов в одном и том же подмножество, и каждое возможное ребро, которое могло бы соединять вершины в разных подмножествах, является частью графа. То есть это двудольный граф (V1, V 2, E) такой, что для любых двух вершин v 1 ∈ V 1 и v 2 ∈ V 2, v 1v2- ребро в E. Полный двудольный граф с разбиениями размера | V 1 | = m и | V 2 | = n, обозначается K m, n ; каждые два графика с одинаковыми обозначениями изоморфны.
Примеры
звездчатые графики K 1,3, K 1,4, K 1,5 и K 1,6.
- Для любого k, K 1, k называется звездой. Все полные двудольные графы, которые являются деревьями, являются звездами.
- Граф K 1,3 называется клешней и используется для определения графов без когтей.
- Граф K 3,3 называется графом полезности. Это использование происходит из стандартной математической головоломки, в которой три инженерных сети должны быть связаны с тремя зданиями; невозможно решить без пересечений из-за непланарности K 3,3.
- Максимальные биклики, найденные как подграфы орграфа отношения, называются концептами . Когда решетка формируется путем взятия встреч и соединений этих подграфов, отношение имеет решетку индуцированных понятий. Этот тип анализа отношений называется анализ формальных понятий.
Свойства
Пример K p, p полные двудольные графыK3,3 | K4,4 | K5,5 |
---|
| | |
. 3 раскраски ребер | . 4 раскраски ребер | . 5 раскраски ребер |
Правильные комплексные многоугольники вида 2 {4} p имеют полные двудольные графы с 2p вершинами (красный и синий) и п 2-кром. Их также можно нарисовать как p окраски краев. |
- Для данного двудольного графа проверка того, содержит ли он полный двудольный подграф K i, i для параметра i, является NP-полной проблемой.
- A планарный граф не может содержать K 3,3 в качестве второстепенного ; внешнепланарный граф не может содержать K 3,2 в качестве второстепенного (это не достаточные условия для планарности и внешней планарности, но они необходимы). И наоборот, каждый неплоский граф содержит либо K 3,3, либо полный граф K5в качестве минорного; это теорема Вагнера.
- Всякий полный двудольный граф. Kn, n - это граф Мура и (n, 4) - клетка.
- полные двудольные графы Kn, n и Kn, n + 1 имеют максимально возможное количество ребер среди всех графов без треугольников с одинаковым количеством вершин; это теорема Мантеля. Результат Мантела был обобщен на k-разделные графы и графы, которые избегают более крупных клик в качестве подграфов в теореме Турана, и эти два полных двудольных графа являются примерами графов Турана, экстремальные графы для этой более общей задачи.
- Полный двудольный граф Km, n имеет число покрытий вершин min {m, n} и ребро, покрывающее номер из max {m, n}.
- Полный двудольный граф Km, n имеет максимальный независимый набор размера max {m, n}.
- матрица смежности полного двудольного графа Km, n имеет собственные значения √nm, −√nm и 0; с кратностью 1, 1 и n + m − 2 соответственно.
- матрица лапласиана полного двудольного графа Km, n имеет собственные значения n + m, n, м и 0; с кратностью 1, m − 1, n − 1 и 1.
- Полный двудольный граф Km, n имеет mn остовных деревьев.
- Полный двудольный граф Km, n имеет максимальное соответствие размера min{m,n}.
- Полный двудольный граф Kn, n имеет правильную n-раскраску ребер, соответствующую латинскому квадрату.
- Каждый полный двудольный граф является модульным графом : каждая тройка вершин имеет медиану, которая принадлежит к кратчайшим путям между каждой парой вершин.
См. также
- Граф без бикликов, класс разреженных графов, определяемый отсутствием полных двудольных подграфов
- Коронный граф, граф, образованный удаление идеального совпадения из полного двудольного графа
- Полный многодольный граф, обобщение полных двудольных графов на более чем два набора вершин
- Атака на биклику
Ссылки