Определение

Наглядное представление: двудольный граф— это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Определение: неориентированный граф G = (W,E) называется двудольным, если множество его вершин можно разбить на две части , | U | > 0, | V | > 0, так, что ни одна вершина в U не соединена с вершинами в U и ни одна вершина в V не соединена с вершинами в V.

Пример: решётка, вершины которой раскрашены в 2 цвета в шахматном порядке.

Двудольный граф называется полным, если для каждой пары вершин существует ребро . Для | U | = i, | V | = j такой граф называется K_i,j

Упражнение 1. Приведите пример двудольного графа с 6 вершинами.

Упражнение 2. Докажите признаки двудольных графов:

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

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

Двудольные графы применяются, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. Например, в экономике — производители и потребители.

На рисунках вершины двудольного графа часто располагают на параллельных прямых.

С двудольными графами связана задача о назначениях. Пусть — множество претендентов на рабочие места, — множество рабочих мест. Необходимо каждого из претендентов обеспечить работой в соответствии с его профессиональной подготовкой.