Двудольные графы

Определение. Двудольным называют граф G = (V, X), множество вершин V которого можно разделить на две части V = V₁È V₂ таким образом, чтобы рёбра соединяли вершины только из разных частей. Обозначают его G=(V₁,V_2,Х).

Определение. Полным двудольным называют двудольныйграф G = (V₁, V₂, Х), (½V₁½ = k,½V₂½ = l), у которого проведены все возможные ребра между вершинами V₁и V₂. Обозначают такой граф как K_k,l .

На рис.1.11 показаны примеры полных двудольных графов K_1,4, K_3,3 , K_3,5 .

Рис. 1.11. Примеры полных двудольных графов K_1,4, K_3,3 , K_3,5 .

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