Введение

Граф, разделенный на два независимых множества

В математической области теории графов, двудольный граф (или биграф) — это граф, чьи вершины можно разделить на два непересекающихся и независимых множества, U и V, так что каждое ребро соединяет вершину из U с вершиной из V. Множества вершин U и V обычно называются частями графа. Эквивалентно, двудольный граф — это граф, не содержащий циклов нечетной длины. Множества U и V можно рассматривать как раскраску графа двумя цветами: если все вершины в U покрасить в синий цвет, а все вершины в V — в красный, то у каждого ребра концы будут разного цвета, как требуется в задаче раскраски графа. В отличие от этого, такая раскраска невозможна для недвудольного графа, например, для треугольника: после того, как одна вершина окрашена в синий, а другая — в красный, третья вершина треугольника соединена с вершинами обоих цветов, что не позволяет присвоить ей ни один из цветов. Часто G = (U, V, E) используется для обозначения двудольного графа, чьим разделением являются множества U и V, где E обозначает ребра графа. Если двудольный граф несвязный, он может иметь более одного двудольного разделения; в этом случае обозначение G = (U, V, E) полезно для указания конкретного разделения, которое может быть важно в конкретном приложении. Если |U| = |V|, то есть, если два подмножества имеют одинаковую мощность, то граф называется сбалансированным двудольным графом. Если все вершины на одной стороне разделения имеют одинаковую степень, то граф называется бирегулярным.

Теорема Кенига и графы совершенства

В двухдольных графах размер минимального покрытия вершин равен размеру максимального совпадения; это теорема Кёнига. Альтернативная и эквивалентная формулировка этой теоремы заключается в том, что размер максимального независимого множества плюс размер максимального совпадения равен числу вершин. В любом графе без изолированных вершин размер минимального покрытия рёбер плюс размер максимального совпадения равен количеству вершин. Комбинируя это равенство с теоремой Кёнига, получаем, что в двухдольных графах размер минимального покрытия рёбер равен размеру максимального независимого множества, а размер минимального покрытия рёбер плюс размер минимального покрытия вершин равен количеству вершин. Другой класс связанных результатов касается совершенных графов: каждый двухдольный граф, дополнение каждого двухдольного графа, линейный граф каждого двухдольного графа и дополнение линейного графа каждого двухдольного графа – все совершенны. Совершенство двухдольных графов очевидно (их хроматическое число равно двум, а максимальный размер клики также равен двум), но совершенство дополнений двухдольных графов менее тривиально и является ещё одной переформулировкой теоремы Кёнига. Это был один из результатов, который мотивировал первоначальное определение совершенных графов. Совершенство дополнений линейных графов совершенных графов – это ещё одна переформулировка теоремы Кёнига, а совершенство самих линейных графов – переформулировка более ранней теоремы Кёнига, утверждающей, что каждый двухдольный граф имеет рёберную раскраску, использующую число цветов, равное его максимальной степени. Согласно теореме о сильных совершенных графах, совершенные графы имеют запрещённую характеристику графа, напоминающую характеристику двухдольных графов: граф двухдолен тогда и только тогда, когда он не содержит нечётный цикл в качестве подграфа, а граф совершенен тогда и только тогда, когда он не содержит нечётный цикл или его дополнение в качестве индуцированного подграфа. Двухдольные графы, линейные графы двухдольных графов и их дополнения образуют четыре из пяти основных классов совершенных графов, используемых в доказательстве теоремы о сильных совершенных графах. Следовательно, любой подграф двухдольного графа также двухдолен, поскольку он не может содержать нечётный цикл.

Степень

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

Последовательность степеней двудольного графа – это пара списков, каждый из которых содержит степени двух долей, и . Например, полный двудольный граф K3,5 имеет последовательность степеней . Изоморфные двудольные графы имеют одинаковую последовательность степеней. Однако последовательность степеней, как правило, не однозначно определяет двудольный граф; в некоторых случаях неизоморфные двудольные графы могут иметь одну и ту же последовательность степеней. Задача реализации двудольного графа – это задача нахождения простого двудольного графа с заданной последовательностью степеней, представленной двумя списками натуральных чисел. (Конечные нули можно игнорировать, поскольку они тривиально реализуются добавлением соответствующего количества изолированных вершин к графу.)

Связь с гиперграфами и направленными графами

Матрица биадъяценции двудольного графа представляет собой (0,1)-матрицу размера , которая содержит единицу для каждой пары смежных вершин и ноль для несмежных вершин. Матрицы биадъяценции могут использоваться для описания эквивалентности между двудольными графами, гиперграфами и ориентированными графами. Гиперграф — это комбинаторная структура, которая, как и неориентированный граф, имеет вершины и ребра, но в которой ребра могут быть произвольными множествами вершин, а не обязательно иметь ровно две конечные точки. Двудольный граф может быть использован для моделирования гиперграфа, в котором U — множество вершин гиперграфа, V — множество гиперрёбер, а E содержит ребро от вершины гиперграфа v к гиперребру e точно тогда, когда v является одной из конечных точек e. При этом соответствии матрицы биадъяценции двудольных графов являются точно матрицами инцидентности соответствующих гиперграфов. Как частный случай этого соответствия между двудольными графами и гиперграфами, любой мультиграф (граф, в котором может быть два или более ребра между одними и теми же двумя вершинами) может быть интерпретирован как гиперграф, в котором некоторые гиперрёбра имеют одинаковые наборы конечных точек, и представлен двудольным графом, который не имеет множественных смежностей и в котором вершины с одной стороны двудольного разбиения все имеют степень два. Аналогичная переинтерпретация матриц смежности может быть использована для демонстрации взаимно однозначного соответствия между ориентированными графами (на заданном количестве помеченных вершин, допускающих самопетли) и сбалансированными двудольными графами с одинаковым количеством вершин по обе стороны двудольного разбиения. Ведь матрица смежности ориентированного графа с n вершинами может быть любой (0,1)-матрицей размера , которую затем можно переинтерпретировать как матрицу смежности двудольного графа с n вершинами на каждой стороне его двудольного разбиения. В этой конструкции двудольный граф является двудольным двойным покрытием ориентированного графа.

Проверка двусторонности

Можно проверить, является ли граф двудольным, и вернуть либо двухцветную раскраску (если он двудольный), либо нечётный цикл (если он не является) за линейное время, используя поиск в глубину. Основная идея заключается в присвоении каждой вершине цвета, отличного от цвета её родителя в дереве поиска в глубину, при присвоении цветов в порядке обхода дерева поиска в глубину (preorder). Это гарантированно обеспечит двухцветную раскраску остовного дерева, состоящего из рёбер, соединяющих вершины с их родителями, но может не правильно раскрасить некоторые рёбра, не входящие в дерево. В дереве поиска в глубину одна из двух конечных точек каждого недревесного ребра является предком другой конечной точки, и когда поиск в глубину обнаруживает такое ребро, он должен проверить, что эти две вершины имеют разные цвета. Если это не так, то путь в дереве от предка к потомку вместе с неправильно раскрашенным ребром образуют нечётный цикл, который возвращается алгоритмом вместе с результатом, что граф не является двудольным. Однако, если алгоритм завершается без обнаружения нечётного цикла такого типа, то каждое ребро должно быть правильно раскрашено, и алгоритм возвращает раскраску вместе с результатом, что граф является двудольным. В качестве альтернативы, аналогичная процедура может быть использована с поиском в ширину вместо поиска в глубину. Снова, каждому узлу присваивается цвет, противоположный цвету его родителя в дереве поиска, в порядке обхода в ширину. Если, когда вершина раскрашена, существует ребро, соединяющее её с ранее раскрашенной вершиной того же цвета, то это ребро вместе с путями в дереве поиска в ширину, соединяющими его две конечные точки с их наименьшим общим предком, образуют нечётный цикл. Если алгоритм завершается без обнаружения нечётного цикла таким образом, то он должен был найти правильную раскраску и может с уверенностью заключить, что граф является двудольным. Для графов пересечений отрезков линий или других простых фигур на евклидовой плоскости можно проверить, является ли граф двудольным, и вернуть либо двухцветную раскраску, либо нечётный цикл за время , даже если сам граф может иметь до рёбер.

Нечетный цикл поперечного

Нечётный цикл поперечный – это NP-полная алгоритмическая задача, которая заключается в следующем: задан граф G = (V,E) и число k, существует ли множество из k вершин, удаление которых из G сделает полученный граф двудольным. Задача является фиксированно-параметризуемой, то есть существует алгоритм, время работы которого можно ограничить полиномиальной функцией от размера графа, умноженной на более сложную функцию от k. Название "нечётный цикл поперечный" происходит от того факта, что граф является двудольным тогда и только тогда, когда он не содержит нечётных циклов. Следовательно, чтобы удалить вершины из графа и получить двудольный граф, необходимо "пересечь все нечётные циклы", или найти так называемое множество вершин, являющееся нечётным циклом поперечным. На иллюстрации каждый нечётный цикл в графе содержит синие (нижние) вершины, поэтому удаление этих вершин уничтожает все нечётные циклы и оставляет двудольный граф. Задача бипартизации рёбер – это алгоритмическая задача об удалении минимального количества рёбер, чтобы сделать граф двудольным, и она также является важной задачей в алгоритмике модификации графов. Эта задача также фиксированно-параметризуема и может быть решена за время , где k – количество рёбер, которые необходимо удалить, а m – количество рёбер во входном графе.

Соответствие

Соответствие в графе — это подмножество его ребер, любые два из которых не имеют общую вершину. Для многих алгоритмических задач, связанных с соответствиями, известны алгоритмы, работающие за полиномиальное время, включая нахождение максимального соответствия (соответствия, использующего максимально возможное количество ребер), максимального соответствия по весу и стабильного брака. Во многих случаях задачи о соответствии проще решать на двудольных графах, чем на недвудольных, и многие алгоритмы для нахождения соответствий, такие как алгоритм Хопкрофта — Карпа для нахождения соответствия максимальной мощности, корректно работают только для двудольных графов. В качестве простого примера рассмотрим ситуацию, когда группа людей ищет работу из числа доступных вакансий, при этом не все люди подходят для всех вакансий. Эту ситуацию можно смоделировать как двудольный граф, где ребро соединяет каждого соискателя с каждой подходящей ему вакансией. Полное соответствие описывает способ одновременного трудоустройства всех соискателей и заполнения всех вакансий; теорема Холла о браке дает характеристику двудольных графов, допускающих полное соответствие. Национальная программа сопоставления резидентов применяет методы сопоставления графов для решения этой задачи для студентов-медиков США, ищущих работу, и вакансий в больницах. Разложение Дулмажа — Мендельсона — это структурное разложение двудольных графов, полезное для нахождения максимальных соответствий.

Дополнительные заявки

Двухдольные графы широко используются в современной теории кодирования, особенно для декодирования кодовых слов, принятых по каналу связи. Примерами этого служат факторные графы и графы Таннера. Граф Таннера — это двухдольный граф, в котором вершины с одной стороны бипартиции представляют разряды кодового слова, а вершины с другой стороны — комбинации разрядов, которые должны в сумме давать ноль в кодовом слове без ошибок. Факторный граф — это тесно связанная вероятностная сеть, используемая для вероятностного декодирования кодов LDPC и турбокодов. В информатике сеть Петри — это математический инструмент моделирования, применяемый для анализа и моделирования конкурентных систем. Система моделируется как двудольный ориентированный граф с двумя множествами узлов: множество "мест", содержащих ресурсы, и множество "переходов", которые генерируют и/или потребляют ресурсы. На узлы и ребра накладываются дополнительные ограничения, определяющие поведение системы. Сети Петри используют свойства двудольных ориентированных графов и другие свойства для обеспечения математических доказательств поведения систем, а также для упрощения реализации их моделирования. В проективной геометрии графы Леви — это разновидность двухдольного графа, используемого для моделирования инцидентности между точками и прямыми в конфигурации. В соответствии с геометрическим свойством точек и прямых, согласно которому любые две прямые пересекаются не более чем в одной точке, а любые две точки соединяются единственной прямой, графы Леви не могут содержать циклы длиной четыре, следовательно, их длина окружности должна быть не менее шести.