Полный двудольный граф
- Полный двудольный граф — особый вид двудольного графа, в котором каждая вершина первого множества соединена с каждой вершиной второго множества.
- Теория графов обычно датируется работой Леонарда Эйлера «Семь мостов Кенигсберга».
- Определение полного двудольного графа: вершины могут быть разделены на два подмножества V1 и V2, ни одно ребро не имеет обеих конечных точек в одном подмножестве.
- Примеры полных двудольных графов: K1,3 (коготь), K3,3 (граф полезности), максимальные биклики в орграфе отношения.
- Свойства полных двудольных графов: проверка наличия полного двудольного подграфа Ki,i NP-полна, плоский граф не содержит K3,3, каждый полный двудольный граф имеет максимальное число ребер и вершин.
- Матрица смежности и матрица Лапласа полного двудольного графа имеют определенные собственные значения и кратность.
- Полный двудольный граф имеет максимальное соответствие размеру min{m,n} и правильную раскраску n ребер.
- Полный двудольный граф является модульным графом, каждая тройка вершин имеет медиану.
Полный текст статьи: