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

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

Пример двудольного графа без циклов

Полный двудольный граф с m = 5 и n = 3

Граф Хивуда двудольный.

В математической области теории графов двудольный граф (или биграф ) — это граф , вершины которого можно разделить на два непересекающихся и независимых множества и , то есть каждое ребро соединяет вершину в с одной в . Множество вершин обычно называют частями графа. Эквивалентно, двудольный граф — это граф, который не содержит циклов нечетной длины . ^{[1] [2]} ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$

Эти два набора можно рассматривать как раскраску графа в два цвета: если раскрасить все узлы в синий цвет, а все узлы в красный, каждое ребро будет иметь конечные точки разных цветов, как это требуется в задаче раскраски графа. ^{[3] [4]} Напротив, такая раскраска невозможна в случае недвудольного графа, такого как треугольник : после того, как один узел окрашен в синий цвет, а другой в красный, третья вершина треугольника соединяется с вершинами оба цвета, что предотвращает присвоение ему любого цвета. ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$

Часто пишут для обозначения двудольного графа, разбиение которого состоит из частей и , с обозначением ребер графа. Если двудольный граф несвязен , он может иметь более одного двудольного графа; ^[5] в этом случае обозначение полезно для указания одного конкретного бираздела, который может иметь значение в приложении. Если , то есть если два подмножества имеют одинаковую мощность , то граф называется сбалансированным двудольным. ^[3] Если все вершины на одной стороне двудольного деления имеют одинаковую степень , то оно называется бирегулярным . ${\displaystyle G=(U,V,E)}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle (U,V,E)}$ ${\displaystyle |U|=|V|}$ ${\displaystyle G}$ ${\displaystyle G}$

Примеры

При моделировании отношений между двумя разными классами объектов очень часто естественным образом возникают двудольные графы. Например, граф футболистов и клубов с перевесом между игроком и клубом, если игрок играл за этот клуб, является естественным примером сети филиалов , типа двудольного графа, используемого в анализе социальных сетей . ^[6]

Другой пример естественного появления двудольных графов — это ( NP-полная ) задача оптимизации железных дорог, в которой входными данными является расписание поездов и их остановок, а цель — найти как можно меньший набор железнодорожных станций, чтобы каждый поезд посещает хотя бы одну из выбранных станций. Эту проблему можно смоделировать как проблему доминирующего множества в двудольном графе, который имеет вершину для каждого поезда и каждой станции и ребро для каждой пары станций и поезда, который останавливается на этой станции. ^[7]

Третий пример относится к академической области нумизматики. Древние монеты изготавливаются с использованием двух положительных оттисков дизайна (аверса и реверса). Диаграммы, которые нумизматы создают для представления производства монет, представляют собой двудольные графики. ^[8]

Более абстрактные примеры включают следующее:

• Каждое дерево двудольное. ^[4]
• Графы циклов с четным числом вершин являются двудольными. ^[4]
• Любой планарный граф , все грани которого имеют четную длину, является двудольным. ^[9] Особыми случаями этого являются сетчатые графы и квадратные графы , в которых каждая внутренняя грань состоит из 4 ребер, а каждая внутренняя вершина имеет четырех или более соседей. ^[10]
• Полный двудольный граф на m и n вершинах, обозначаемый Kn _,m , является двудольным графом , где U и V — непересекающиеся множества размеров m и n соответственно, а E соединяет каждую вершину в U со всеми вершинами в V. Отсюда следует, что K _m,n имеет mn ребер. ^[11] С полными двудольными графами тесно связаны коронные графы , образованные из полных двудольных графов путем удаления ребер идеального паросочетания . ^[12] ${\displaystyle G=(U,V,E)}$
• Графы гиперкубов , частичные кубы и медианные графы являются двудольными. В этих графах вершины могут быть помечены битовыми векторами таким образом, что две вершины являются смежными тогда и только тогда, когда соответствующие битовые векторы различаются в одной позиции. Двуразделение может быть сформировано путем отделения вершин, битвекторы которых имеют четное число единиц, от вершин с нечетным числом единиц. Деревья и квадратные графы образуют примеры медианных графов, и каждый медианный граф представляет собой частичный куб. ^[13]

Характеристики

Характеристика

Двудольные графы можно охарактеризовать несколькими различными способами:

• Неориентированный граф является двудольным тогда и только тогда, когда он не содержит нечетного цикла . ^{[14] [15]}
• Граф является двудольным тогда и только тогда, когда он раскрашивается в 2 цвета (т. е. его хроматическое число меньше или равно 2). ^[3]
• Граф является двудольным тогда и только тогда, когда каждое ребро принадлежит нечетному числу связей — минимальному подмножеству ребер, удаление которых увеличивает количество компонентов графа. ^[16]
• Граф является двудольным тогда и только тогда, когда спектр графа симметричен. ^[17]

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

В двудольных графах размер минимального покрытия вершин равен размеру максимального паросочетания ; это теорема Кенига . ^{[18] [19]} Альтернативная и эквивалентная форма этой теоремы состоит в том, что размер максимального независимого набора плюс размер максимального соответствия равен числу вершин. В любом графе без изолированных вершин размер минимального покрытия ребер плюс размер максимального паросочетания равны числу вершин. ^[20] Объединение этого равенства с теоремой Кенига приводит к тому, что в двудольных графах размер минимального реберного покрытия равен размеру максимального независимого множества, а размер минимального реберного покрытия плюс размер минимальное вершинное покрытие равно числу вершин.

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

Согласно сильной теореме о совершенном графе , совершенные графы имеют запрещенную характеристику графа, аналогичную характеристике двудольных графов: граф является двудольным тогда и только тогда, когда он не имеет нечетного цикла в качестве подграфа, и граф совершенен тогда и только тогда, когда он имеет нет нечетного цикла или его дополнения как индуцированного подграфа . Двудольные графы, линейные графы двудольных графов и их дополнения образуют четыре из пяти основных классов совершенных графов, используемых при доказательстве сильной теоремы о совершенных графах. ^[22]

Степень

Для вершины количество соседних вершин называется степенью вершины и обозначается . Формула суммы степеней для двудольного графа утверждает, что ^[23] ${\displaystyle \deg(v)}$

${\displaystyle \sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|\,.}$

Последовательность степеней двудольного графа представляет собой пару списков, каждый из которых содержит степени двух частей и . Например, полный двудольный граф K _3,5 имеет последовательность степеней . Изоморфные двудольные графы имеют одинаковую последовательность степеней. Однако последовательность степеней, как правило, не идентифицирует однозначно двудольный граф; в некоторых случаях неизоморфные двудольные графы могут иметь одинаковую последовательность степеней. ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle (5,5,5),(3,3,3,3,3)}$

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

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

Матрица двусмежности двудольного графа представляет собой матрицу размера (0,1) , имеющая единицу для каждой пары соседних вершин и ноль для несмежных вершин. ^[24] Матрицы бисмежности могут использоваться для описания эквивалентности между двудольными графами, гиперграфами и ориентированными графами. ${\displaystyle (U,V,E)}$ ${\displaystyle |U|\times |V|}$

Гиперграф — это комбинаторная структура, которая, как и неориентированный граф, имеет вершины и ребра, но в которой ребра могут представлять собой произвольные наборы вершин, а не иметь ровно две конечные точки. Двудольный граф можно использовать для моделирования гиперграфа, в котором U — множество вершин гиперграфа, V — множество гиперребер, а E содержит ребро от вершины гиперграфа v до ребра гиперграфа e точно тогда, когда v является одним из конечные точки e . При этом соответствии матрицы двудольных графов являются в точности матрицами инцидентности соответствующих гиперграфов. Как частный случай этого соответствия между двудольными графами и гиперграфами, любой мультиграф (граф, в котором между одними и теми же двумя вершинами может быть два или более ребер) может интерпретироваться как гиперграф, в котором некоторые гиперребра имеют равные наборы конечных точек, и представлен двудольным графом, не имеющим кратных смежностей и в котором все вершины на одной стороне двудольного графа имеют степень два. ^[25] ${\displaystyle (U,V,E)}$

Подобная реинтерпретация матриц смежности может быть использована, чтобы показать взаимно однозначное соответствие между ориентированными графами (на заданном количестве помеченных вершин, допускающих самоциклы) и сбалансированными двудольными графами с одинаковым количеством вершин по обе стороны от двуразделение. Ибо матрицей смежности ориентированного графа с n вершинами может быть любая (0,1) матрица размера , которую затем можно переинтерпретировать как матрицу смежности двудольного графа с n вершинами на каждой стороне его двудольного разбиения. ^[26] В этой конструкции двудольный граф представляет собой двудольное двойное покрытие ориентированного графа. ${\displaystyle n\times n}$

Алгоритмы

Тестирование двусторонности

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

Альтернативно, аналогичная процедура может использоваться с поиском в ширину вместо поиска в глубину. Опять же, каждому узлу присваивается цвет, противоположный цвету его родителя в лесу поиска, в порядке ширины. Если при окраске вершины существует ребро, соединяющее ее с ранее окрашенной вершиной того же цвета, то это ребро вместе с путями в лесу поиска в ширину, соединяющими две его конечные точки с их наименьшим общим предком , образует странный цикл. Если алгоритм завершается, не обнаружив таким образом нечетного цикла, то он, должно быть, нашел правильную раскраску и может с уверенностью заключить, что граф двудольный. ^[28]

Для графов пересечений отрезков прямых или других простых фигур на евклидовой плоскости можно проверить, является ли граф двудольным, и вернуть либо двухраскраску, либо нечетный цикл во времени , даже если сам граф может иметь до ребер . ^[29] ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O\left(n^{2}\right)}$

Трансверсализация нечетного цикла

Граф с нечетной трансверсалью цикла размером 2: удаление двух синих нижних вершин оставляет двудольный граф.

Трансверсализация нечетного цикла — это NP-полная алгоритмическая задача, которая спрашивает для данного графа G = ( V , E ) и числа k , существует ли набор из  k вершин, удаление которых из G приведет к тому, что результирующий граф станет двудольным. ^[30] Проблема решается с фиксированными параметрами , что означает, что существует алгоритм, время работы которого может быть ограничено полиномиальной функцией размера графа, умноженной на большую функцию от k . ^[31] Название трансверсальная нечетного цикла происходит от того факта, что граф является двудольным тогда и только тогда, когда он не имеет нечетных циклов . Следовательно, чтобы удалить вершины из графа и получить двудольный граф, нужно «попасть во все нечетные циклы» или найти так называемое трансверсальное множество нечетных циклов. На иллюстрации каждый нечетный цикл в графе содержит синие (самые нижние) вершины, поэтому удаление этих вершин уничтожает все нечетные циклы и оставляет двудольный граф.

Проблема раздвоения ребер — это алгоритмическая проблема удаления как можно меньшего количества ребер, чтобы сделать граф двудольным, а также важная проблема в алгоритмике модификации графов. Эта проблема также решается с фиксированными параметрами и может быть решена за время , ^[32] где k — количество удаляемых ребер, а m — количество ребер во входном графе. ${\textstyle O\left(2^{k}m^{2}\right)}$

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

Паросочетание в графе — это подмножество его ребер, никакие два из которых не имеют общей конечной точки . Алгоритмы с полиномиальным временем известны для решения многих алгоритмических задач о сопоставлениях, включая максимальное сопоставление (поиск сопоставления, которое использует как можно больше ребер), сопоставление с максимальным весом и стабильный брак . ^[33] Во многих случаях задачи сопоставления проще решать на двудольных графах, чем на недвудольных графах, ^[34] и многие алгоритмы сопоставления, такие как алгоритм Хопкрофта-Карпа для сопоставления максимальной мощности ^[35], работают правильно только на двудольных входных данных. .

В качестве простого примера предположим, что группа людей ищет работу из набора должностей, причем не все люди подходят для всех должностей. Эту ситуацию можно смоделировать как двудольный граф , ребро которого соединяет каждого соискателя с каждой подходящей работой. ^[36] Идеальное соответствие описывает способ одновременного удовлетворения всех соискателей и заполнения всех вакансий; Теорема Холла о браке дает характеристику двудольных графов, допускающих идеальные паросочетания. Национальная программа подбора резидентов применяет методы сопоставления графов для решения этой проблемы для американских студентов-медиков , ищущих работу, и для работы в больницах . ^[37] ${\displaystyle P}$ ${\displaystyle J}$ ${\displaystyle (P,J,E)}$

Разложение Далмаджа – Мендельсона — это структурное разложение двудольных графов, которое полезно для поиска максимальных паросочетаний. ^[38]

Дополнительные приложения

Двудольные графы широко используются в современной теории кодирования , особенно для декодирования кодовых слов , полученных из канала. Факторные графы и графы Таннера являются примерами этого. Граф Таннера — это двудольный граф, в котором вершины на одной стороне двудольного деления представляют собой цифры кодового слова, а вершины на другой стороне представляют собой комбинации цифр, сумма которых, как ожидается, без ошибок будет равна нулю в кодовом слове. ^[39] Факторный граф — это тесно связанная сеть доверия , используемая для вероятностного декодирования LDPC и турбокодов . ^[40]

В информатике сеть Петри — это инструмент математического моделирования, используемый при анализе и моделировании параллельных систем. Система моделируется как двудольный ориентированный граф с двумя наборами узлов: набором узлов «места», которые содержат ресурсы, и набором узлов «событий», которые генерируют и/или потребляют ресурсы. Существуют дополнительные ограничения на узлы и ребра, ограничивающие поведение системы. Сети Петри используют свойства двудольных ориентированных графов и другие свойства, позволяющие математически доказывать поведение систем, а также позволяют легко реализовать моделирование системы. ^[41]

В проективной геометрии графы Леви представляют собой форму двудольного графа, используемого для моделирования взаимодействий между точками и линиями в конфигурации . В соответствии с геометрическим свойством точек и линий, согласно которому каждые две прямые пересекаются не более чем в одной точке и каждые две точки соединяются одной прямой, графы Леви обязательно не содержат циклов длины четыре, поэтому их обхват должен быть шесть или более. . ^[42]

Смотрите также

• Двудольная размерность — минимальное количество полных двудольных графов, объединение которых является данным графом.
• Двудольное двойное покрытие — способ преобразования любого графа в двудольный путем удвоения его вершин.
• Двудольный гиперграф , обобщение двудольности на гиперграфы .
• Двудольный матроид — класс матроидов, включающий графические матроиды двудольных графов.
• Проекция двудольной сети — метод взвешивания для сжатия информации о двудольных сетях.
• Выпуклый двудольный граф — двудольный граф, вершины которого можно упорядочить так, чтобы окрестности вершин были смежными.
• Многодольный граф , обобщение двудольных графов на более чем два подмножества вершин.
• Граф четности , обобщение двудольных графов, в котором каждые два индуцированных пути между одними и теми же двумя точками имеют одинаковую четность.
• Квазидвудольный граф , разновидность задачи о дереве Штейнера, в которой терминалы образуют независимый набор, что позволяет использовать алгоритмы аппроксимации, обобщающие алгоритмы для двудольных графов.
• Разделенный граф — граф, вершины которого можно разделить на два подмножества, одно из которых является независимым, а другое — кликой.
• Задача Заранкевича о максимальном числе ребер в двудольном графе с запрещенными подграфами

Рекомендации

1. Дистель, Рейнард (2005), Теория графов, Тексты для выпускников по математике , Springer, ISBN 978-3-642-14278-9, заархивировано из оригинала 9 апреля 2011 г. , получено 27 февраля 2012 г.
2. Асратян, Армен С.; Денли, Тристан MJ; Хэггквист, Роланд (1998), Двудольные графы и их приложения , Кембриджские трактаты по математике, том. 131, Издательство Кембриджского университета, ISBN 9780521593458.
3. Asratian, Denley & Häggkvist (1998), стр. 7.
4. Шайнерман, Эдвард Р. (2012), Математика: дискретное введение (3-е изд.), Cengage Learning, стр. 363, ISBN 9780840049421.
5. Чартран, Гэри ; Чжан, Пин (2008), Теория хроматических графов, Дискретная математика и ее приложения, том. 53, CRC Press, с. 223, ISBN 9781584888000.
6. Вассерман, Стэнли ; Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения, Структурный анализ в социальных науках, том. 8, Издательство Кембриджского университета, стр. 299–302, ISBN. 9780521387071.
7. Нидермайер, Рольф (2006), Приглашение к алгоритмам с фиксированными параметрами , Оксфордская серия лекций по математике и ее приложениям, Oxford University Press, стр. 20–21, ISBN 978-0-19-856607-6
8. Брейси, Роберт (2012), «О графической интерпретации монет Ирода третьего года», Джейкобсон, Дэвид М.; Коккинос, Никос (ред.), Иудея и Рим в монетах 65 г. до н. э. – 135 г. н. э.: доклады, представленные на международной конференции, организованной Спинком, 13–14 сентября 2010 г. , Spink & Son , стр. 65–84.
9. Сойфер, Александр (2008), Математическая книжка-раскраска , Springer-Verlag, стр. 136–137, ISBN 978-0-387-74640-1. Этот результат иногда называют «теоремой двух цветов»; Сойфер приписывает это знаменитой статье Альфреда Кемпе 1879 года , содержащей ложное доказательство теоремы о четырех цветах .
10. Бандельт, H.-J.; Чепой, В.; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301, S2CID  10788524.
11. Асратян, Денли и Хэггквист (1998), с. 11.
12. Архидиакон, Д .; Дебовский, М.; Диниц, Дж .; Гавлас, Х. (2004), «Системы циклов в полном двудольном графе минус однофакторный», Discrete Mathematics , 284 (1–3): 37–43, doi :10.1016/j.disc.2003.11.021.
13. Овчинников, Сергей (2011), Графы и кубы , Universitext, Springer. См. особенно главу 5, «Частичные кубы», стр. 127–181.
14. Асратян, Денли и Хэггквист (1998), теорема 2.1.3, с. 8. Асратян и др. приписывают эту характеристику статье Денеша Кёнига 1916 года . Для бесконечных графов этот результат требует аксиомы выбора .
15. Банг-Йенсен, Йорген; Гутин, Грегори (2001), Орграфы: теория, алгоритмы и приложения (PDF) (1-е изд.), Стр. 25, ISBN 9781852332686, заархивировано (PDF) из оригинала 02 января 2023 г. , получено 2 января 2023 г.
16. Вудалл, Д.Р. (1990), «Доказательство эйлеровой двудольной характеристики Макки», Discrete Mathematics , 84 (2): 217–220, doi : 10.1016/0012-365X(90)90380-Z, MR  1071664
17. Биггс, Норман (1994), Алгебраическая теория графов, Кембриджская математическая библиотека (2-е изд.), Cambridge University Press, стр. 53, ISBN 9780521458979.
18. Кениг, Денес (1931), «Gráfok és mátrixok», Matematikai és Fizikai Lapok , 38 : 116–119.
19. Гросс, Джонатан Л.; Йеллен, Джей (2005), Теория графов и ее приложения, Дискретная математика и ее приложения (2-е изд.), CRC Press, стр. 568, ISBN 9781584885054.
20. Чартран, Гэри ; Чжан, Пин (2012), Первый курс теории графов, Courier Dover Publications, стр. 189–190, ISBN 9780486483689.
21. Бела Боллобас (1998), Современная теория графов, Тексты для выпускников по математике, том. 184, Спрингер, с. 165, ИСБН 9780387984889.
22. Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , CiteSeerX 10.1.1.111.7265 , doi :10.4007/annals.2006.164.51 , S2CID  119151552 .
23. Ловас, Ласло (2014), Комбинаторные задачи и упражнения (2-е изд.), Elsevier, стр. 2014. 281, ISBN 9780080933092
24. Асратян, Денли и Хэггквист (1998), с. 17.
25. А. А. Сапоженко (2001) [1994], «Гиперграф», Энциклопедия математики , EMS Press
26. Бруальди, Ричард А.; Харари, Фрэнк ; Миллер, Зеви (1980), «Биграфы против орграфов через матрицы», Журнал теории графов , 4 (1): 51–73, doi : 10.1002/jgt.3190040107, MR  0558453. Бруальди и др. приписывают идею этой эквивалентности Дулмейджу, Ал.; Мендельсон, Н.С. (1958), «Покрытия двудольных графов», Canadian Journal of Mathematics , 10 : 517–534, doi : 10.4153/CJM-1958-052-0 , MR  0097069, S2CID  123363425.
27. Седжвик, Роберт (2004), Алгоритмы на Java, Часть 5: Алгоритмы графов (3-е изд.), Аддисон Уэсли, стр. 109–111.
28. Кляйнберг, Джон ; Тардос, Ева (2006), Разработка алгоритмов , Аддисон Уэсли, стр. 94–97..
29. Эппштейн, Дэвид (2009), «Проверка двудольности графов геометрических пересечений», Транзакции ACM в алгоритмах , 5 (2): Ст. 15, arXiv : cs.CG/0307023 , doi : 10.1145/1497290.1497291, MR  2561751, S2CID  60496.
30. Яннакакис, Михалис (1978), «NP-полные проблемы с удалением узлов и ребер», Труды 10-го симпозиума ACM по теории вычислений (STOC '78) , стр. 253–264, doi : 10.1145/800133.804355 , S2CID  363248
31. Рид, Брюс ; Смит, Кейли; Ветта, Адриан (2004), «Нахождение трансверсалей нечетного цикла», Operations Research Letters , 32 (4): 299–301, CiteSeerX 10.1.1.112.6357 , doi :10.1016/j.orl.2003.10.009, MR  2057781 .
32. Го, Цзюн; Грамм, Йенс; Хюффнер, Фальк; Нидермайер, Рольф; Вернике, Себастьян (2006), «Алгоритмы с фиксированными параметрами на основе сжатия для набора вершин обратной связи и разделения ребер», Journal of Computer and System Sciences , 72 (8): 1386–1396, doi : 10.1016/j.jcss.2006.02. 001
33. Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993), «12. Присвоения и сопоставления», Сетевые потоки: теория, алгоритмы и приложения , Прентис Холл, стр. 461–509..
34. Ахуджа, Маньянти и Орлин (1993), с. 463: «Проблемы недвустороннего сопоставления труднее решить, поскольку они не сводятся к стандартным задачам сетевого потока».
35. Хопкрофт, Джон Э .; Карп, Ричард М. (1973), « Алгоритм n ^5/2 для максимального сопоставления в двудольных графах», SIAM Journal on Computing , 2 (4): 225–231, doi : 10.1137/0202019.
36. Ахуджа, Маньянти и Орлин (1993), Приложение 12.1 Двустороннее назначение персонала, стр. 463–464.
37. Робинсон, Сара (апрель 2003 г.), «Встречают ли студенты-медики свою (лучшую возможную) пару?» (PDF) , SIAM News (3): 36, заархивировано из оригинала (PDF) 18 ноября 2016 г. , получено 27 августа 2012 г..
38. Дулмейдж и Мендельсон (1958).
39. Мун, Тодд К. (2005), Кодирование с коррекцией ошибок: математические методы и алгоритмы, John Wiley & Sons, стр. 638, ISBN 9780471648000.
40. Луна (2005), с. 686.
41. Кассандра, Христос Г.; Лафортюн, Стефан (2007), Введение в системы дискретных событий (2-е изд.), Springer, стр. 224, ISBN 9780387333328.
42. Грюнбаум, Бранко (2009), Конфигурации точек и линий, Аспирантура по математике , том. 103, Американское математическое общество , с. 28, ISBN 9780821843086.

Внешние ссылки

• «Граф двудольный», Математическая энциклопедия , EMS Press , 2001 [1994]
• Информационная система по классам графов и их включениям: двудольный граф
• Вайсштейн, Эрик В. , «Двудольный граф», MathWorld
• Двудольные графы в системной биологии и медицине