Полный двудольный граф

редактировать
Двудольный граф, в котором каждая вершина первого набора соединена с каждой вершиной второго набора
Полный двудольный граф
Biclique K 3 5.svg Полный двудольный граф с m = 5 и n = 3
Вершины n + m
Ребра mn
Радиус {1 m = 1 ∨ n = 1 2 иначе {\ displaystyle \ left \ {{\ begin {array} { ll} 1 m = 1 \ vee n = 1 \\ 2 {\ text {else}} \ end {array}} \ right.}\ left \ {{\ begin {array} {ll} 1 m = 1 \ vee n = 1 \ \ 2 {\ text {else}} \ end {array}} \ right.
Диаметр {1 m = n = 1 2 в противном случае {\ displaystyle \ left \ {{\ begin {array} {ll} 1 m = n = 1 \\ 2 {\ text {else}} \ end {array}} \ right.}\ left \ {{\ begin {array} {ll} 1 m = n = 1 \\ 2 {\ text {else}} \ end {array}} \ right.
Обхват {∞ m = 1 ∨ n = 1 4 иначе {\ displaystyle \ left \ {{\ begin {array} {ll} \ infty m = 1 \ lor n = 1 \\ 4 {\ text {else}} \ end {array}} \ right. }{\ displaystyle \ left \ {{\ begin {array} {ll} \ infty m = 1 \ lor n = 1 \\ 4 {\ text {else}} \ end {array}} \ right.}
Автоморфизмы {2 м! п! п = м м! п! в противном случае {\ displaystyle \ left \ {{\ begin {array} {ll} 2m! n! n = m \\ m! n! {\ text {else}} \ end {array}} \ right.}\ left \ {{\ begin {array} {ll} 2m! n! n = m \\ m! n! {\ text {иначе}} \ end {array}} \ right.
Хроматическое число 2
Хроматический индекс max {m, n}
Спектр {0 n + m - 2, (± nm) 1} {\ displaystyle \ left \ {0 ^ {n + m-2}, (\ pm {\ sqrt {nm}}) ^ {1} \ right \}}{\ displaystyle \ left \ {0 ^ {n + m-2}, (\ pm {\ sqrt {nm}}) ^ {1} \ right \}}
ОбозначениеK m, n {\ displaystyle K_ {m, n}}K_ {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 3,3 называется графом полезности. Это использование происходит из стандартной математической головоломки, в которой три инженерных сети должны быть связаны с тремя зданиями; невозможно решить без пересечений из-за непланарности K 3,3.

Свойства

Пример K p, p полные двудольные графы
K3,3 K4,4K5,5
Сложный многоугольник 2-4-3-двудольный graph.png Сложный многоугольник 2-4-4 двудольный graph.png Сложный многоугольник 2-4-5-двудольный graph.png
Сложный многоугольник 2-4 -3.png . 3 раскраски реберСложный polygon 2-4-4.png . 4 раскраски реберСложный многоугольник 2-4-5.png . 5 раскраски ребер
Правильные комплексные многоугольники вида 2 {4} p имеют полные двудольные графы с 2p вершинами (красный и синий) и п 2-кром. Их также можно нарисовать как p окраски краев.

См. также

Ссылки

Последняя правка сделана 2021-05-15 08:13:54
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте