Свойства

· Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины. Поэтому двудольный граф не может содержать клику размером более 2.

· Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум)

· Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые элементов одной из долей связаны по крайней мере с элементами другой (Теорема Холла).

· Полный двудольный граф, у которого в каждой части больше 2 вершин, является непланарным.

· Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

8) Теорема Кенинга о двудольности:

1) В любом двудольном графе число рёбер в максимальном паросочетании равно числу вершин в минимальном вершинном покрытии.

2) Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины

Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин "линия" обозначает либо строку, либо столбец в матрице). ^[4]

Данная формулировка легко переводится на язык двудольных графов:

Строки таблицы – это вершины одной части двудольного графа, столбцы – другой части.

Линии – это вершинное покрытие.

Единицы матрицы – рёбра. Требование, чтобы никакие две единицы не лежали на одной линии соответствует паросочетанию.

Дата добавления: 2015-10-13