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

Двудольным графом называется граф, вершины которого разбиты на два непересекающихся класса: V = V1 u V2, а ребра связывают вершины только из разных классов – не обязательно все пары (рис.15). Соответствие Г между непересекающимися множествами М и N можно представлять как двудольный граф с множеством вершин М u N и ребрами, связывающими каждый элемент множества М с его образом при соответствии Г. Так, соответствие между билетами теста и содержащимися в них задачами изображается графом со 150 вершинами в одном классе и 40 вершинами в другом. Каждая из вершин второго класса соединена с 25 различными вершинами первого класса. Если же каждая из вершин класса V1 связана ребром с каждой вершиной класса V2, то граф называется полным двудольным и обозначается Кm, n, где m = |V1|, n = |V2|.

Очевидно, граф Кm, n содержит (m+n) вершин и полный граф Кm, n т.п. ребер.

Задание. Изобразите граф К3,3 с минимально возможным числом пересечений.

Двудольный граф представляет возможные варианты 4 групп крови у ребенка супругов, один из которых имеет кровь II группы (тип АО), а второй произвольного типа Х. Изолированная вершина ВВ означает невозможность появления такого типа крови ни при каком Х.

Таблица 2