Двудольный граф: примеры. Теория графов
Двудольные графы - удивительные математические объекты с множеством практических применений в самых разных областях. Давайте разберемся, что это такое, изучим примеры и научимся строить такие графы.
Определение двудольного графа
Формально, двудольный граф - это граф, множество вершин которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной из другой. Иными словами, нет ни одного ребра, которое соединяло бы две вершины внутри одной части.
Интуитивно это можно представить так: есть две группы объектов, и связи между ними образуют ребра графа. Но объекты внутри каждой группы не связаны ребрами.
Двудольный граф отличается тем, что не содержит простых нечетных циклов.
Рассмотрим пример полного двудольного графа \K3,3\. Здесь 3 вершины в первой доле и 3 вершины во второй. И каждая вершина первой доли соединена ребрами со всеми вершинами второй:
Как проверить, является ли граф двудольным
Чтобы проверить, является ли произвольный граф двудольным, можно использовать следующий алгоритм:
- Выбрать любую непосещенную вершину и поместить в первую долю
- Пройти по графу в ширину, помещая новые вершины во вторую долю
- Если при обходе ребро ведет в уже посещенную вершину, проверить, чтобы обе вершины были в разных долях
- Повторять обход из непосещенных вершин, пока есть такие
Разберем этот алгоритм на конкретном примере графа:
Начнем обход из вершины A и поместим ее в первую долю. Затем по ребрам перейдем в вершины B и C, добавив их во вторую долю. Далее обходим оставшиеся вершины, не нарушая правило разделения на доли. Таким образом, получаем разбиение на 2 доли и видим, что граф действительно двудольный.
Асимптотическая сложность этого алгоритма составляет O(V+E), где V - количество вершин, E - количество ребер. То есть линейная сложность от размера графа. Что вполне приемлемо для практики.
Для оптимизации стоит начинать обход из висячих вершин (со степенью 1). Тогда с вероятностью 50% мы сразу попадем в нужную долю и сократим количество переборов.
Примеры двудольных графов
Двудольный граф естественным образом моделирует бинарные отношения между объектами двух типов. Например, отношение "студент сдал экзамен по предмету". Здесь студенты - объекты первого типа, предметы - второго типа. А сдача экзамена - это ребро между соответствующими вершинами графа.
Другой классический пример - граф футболистов и клубов. Где футболисты - первая доля вершин, клубы - вторая. А ребро означает, что игрок выступал за данный клуб.
Еще один интересный пример - сеть знакомств. Пусть есть компания людей, разбитая на мужчин и женщин. Тогда знакомство между мужчиной и женщиной - это ребро двудольного графа знакомств.
Задачи на двудольных графах
Рассмотрим некоторые типичные задачи, возникающие на двудольных графах.
Задача о паросочетаниях
Паросочетанием в двудольном графе называется подмножество ребер, никакие два из которых не имеют общей вершины. Паросочетания часто применяются при составлении расписаний и решении задач о назначениях.
Например, если вершины - это уроки и учителя, то максимальное паросочетание соответствует такому назначению уроков учителям, чтобы каждый учитель вел максимально возможное количество уроков одновременно.
Задача о минимальном разбиении на паросочетания
Если нужно разбить все ребра двудольного графа на паросочетания так, чтобы их было минимально возможное число - это тоже классическая задача теории расписаний.
Например, чтобы спланировать минимальное число дней экзаменационной сессии, при условии что в один день студент может сдавать только один экзамен.
Неориентированный граф против ориентированного
До сих пор речь шла о неориентированных графах, где направление ребер не имеет значения. Но что если ввести ориентацию?
Например, в графе студентов и предметов направление ребра "студент -> предмет" может обозначать желание студента сдавать данный предмет, а обратное направление - то, что предмет уже сдан.
Особенности ориентированного двудольного графа
При работе с ориентированным двудольным графом следует учитывать дополнительные особенности:
- Различаются входящие и исходящие ребра для каждой вершины
- Могут существовать ребра только в одном направлении между вершинами
- Понятие паросочетания требует корректного определения
Применение двудольных графов на практике
Кроме уже упомянутых примеров, двудольные графы часто применяются в задачах оптимизации, теории игр, логистике, информатике и других областях.
Двудольное представление конфликтов
Если есть две группы агентов с противоположными интересами, то все потенциальные конфликты между ними можно представить в виде ребер двудольного графа. Это позволяет использовать известные алгоритмы для анализа и предотвращения конфликтов.
Моделирование транспортных сетей
Транспортные сети, соединяющие пункты отправления и пункты назначения, также можно представить с помощью двудольного графа. Здесь в одной доле находятся пункты отправления грузов, а в другой - пункты получения. Ребра обозначают возможные маршруты доставки.
Такое представление позволяет эффективно решать задачи оптимизации логистических потоков методами теории графов.
Построение расписаний
Уже упоминалась возможность использования двудольного графа для моделирования задачи составления расписания. Рассмотрим подходы к решению такой задачи более подробно.
Жадный алгоритм
Простой эвристический алгоритм заключается в следующем:
- Выбрать вершину с максимальной степенью
- Назначить ей максимально возможное число паросочетаний
- Повторять, пока есть неназначенные вершины
Такой жадный подход не гарантирует оптимальности, но часто дает хорошее приближение за полиномиальное время.
Метод ветвей и границ
Для точного решения можно применить метод ветвей и границ - перебор вариантов с отсечением заведомо неоптимальных решений. Это позволяет найти оптимальное расписание, но требует экспоненциального времени в худшем случае.
Открытые проблемы теории двудольных графов
Несмотря на кажущуюся простоту, двудольные графы продолжают привлекать внимание исследователей. Рассмотрим две известные открытые проблемы в этой области.
Гипотеза о паросочетаниях
Эта гипотеза утверждает, что любой двудольный граф с n вершинами в каждой доле имеет паросочетание размера не меньше 0.8n. Пока не удалось ни доказать, ни опровергнуть эту гипотезу в общем случае.