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

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

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

Полный двудольный граф с 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 вершинах, обозначаемый K _n,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]

Степень

Для вершины число смежных вершин называется степенью вершины и обозначается . Формула суммы степеней для двудольного графа гласит, что ^[24] ${\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) , в которой для каждой пары смежных вершин содержится единица, а для несмежных вершин — ноль. ^[25] Матрицы бисмежности могут использоваться для описания эквивалентностей между двудольными графами, гиперграфами и ориентированными графами. ${\displaystyle (U,V,E)}$ ${\displaystyle |U|\times |V|}$

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

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

Алгоритмы

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

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

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

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

Нечетный цикл трансверсальный

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Дистель, Рейнард (2005), Теория графов, Graduate Texts in Mathematics , Springer, ISBN 978-3-642-14278-9, архивировано из оригинала 2011-04-09 , извлечено 2012-02-27
2. Асратян, Армен С.; Денли, Тристан М.Дж.; Хэггквист, Роланд (1998), Двудольные графы и их приложения , Cambridge Tracts in Mathematics, т. 131, Cambridge University Press, 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, Cambridge University Press, стр. 299–302, ISBN 9780521387071.
7. Нидермейер, Рольф (2006), Приглашение к алгоритмам с фиксированными параметрами , Серия лекций Оксфордского университета по математике и ее приложениям, Издательство Оксфордского университета, стр. 20–21, ISBN 978-0-19-856607-6
8. Брейси, Роберт (2012), «О графической интерпретации монет 3-го года Ирода», в Якобсон, Дэвид М.; Коккинос, Никос (ред.), Иудея и Рим в монетах 65 г. до н. э. – 135 г. н. э.: доклады, представленные на международной конференции, организованной Spink, 13–14 сентября 2010 г. , Spink & Son , стр. 65–84
9. Сойфер, Александр (2008), Математическая раскраска , Springer-Verlag, стр. 136–137, ISBN 978-0-387-74640-1Этот результат иногда называют «теоремой о двух красках»; Сойфер приписывает его знаменитой статье Альфреда Кемпе 1879 года , содержащей ложное доказательство теоремы о четырех красках .
10. Бандельт, Х.-Дж.; Чепои, В.; Эппштейн, Д. (2010), «Комбинаторика и геометрия конечных и бесконечных квадратных графов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301, S2CID  10788524.
11. Асратиан, Денли и Хэггквист (1998), с. 11.
12. Архидьякон, Д .; Дебовски, М.; Диниц, Дж .; Гавлас, Х. (2004), «Системы циклов в полном двудольном графе без одного фактора», Дискретная математика , 284 (1–3): 37–43, doi :10.1016/j.disc.2003.11.021.
13. Овчинников, Сергей (2011), Графы и кубы , Universitext, Springer. См. особенно главу 5 «Частичные кубы», стр. 127–181.
14. Asratian, Denley & Häggkvist (1998), Теорема 2.1.3, стр. 8. Asratian et al. приписывают эту характеристику статье 1916 года Денеша Кёнига . Для бесконечных графов этот результат требует аксиомы выбора .
15. Банг-Йенсен, Йорген; Гутин, Грегори (2001), Диграфы: теория, алгоритмы и приложения (PDF) (1-е изд.), Springer, стр. 25, ISBN 9781852332686, заархивировано (PDF) из оригинала 2023-01-02 , извлечено 2023-01-02
16. Вудол, DR (1990), «Доказательство эйлерово-двудольной характеризации Макки», Дискретная математика , 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), Современная теория графов, Graduate Texts in Mathematics, т. 184, Springer, стр. 165, ISBN 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. ДеВос, Мэтт, «Matchings» (PDF) , Конспект лекций: Введение в теорию графов, Математика 345 , Университет Саймона Фрейзера
24. Ловас, Ласло (2014), Комбинаторные задачи и упражнения (2-е изд.), Elsevier, стр. 2014. 281, ISBN 9780080933092
25. Асратиан, Денли и Хэггквист (1998), стр. 17.
26. А.А. Сапоженко (2001) [1994], «Гиперграф», Энциклопедия математики , Издательство ЭМС
27. Бруальди, Ричард А.; Харари, Фрэнк ; Миллер, Зеви (1980), «Биграфы против орграфов с помощью матриц», Журнал теории графов , 4 (1): 51–73, doi :10.1002/jgt.3190040107, MR  0558453. Брулди и др. приписывают идею этой эквивалентности Дульмейджу, АЛ; Мендельсону, Н.С. (1958), «Покрытия двудольных графов», Канадский журнал математики , 10 : 517–534, doi : 10.4153/CJM-1958-052-0 , MR  0097069, S2CID  123363425.
28. Седжвик, Роберт (2004), Алгоритмы в Java, часть 5: Графовые алгоритмы (3-е изд.), Addison Wesley, стр. 109–111.
29. Кляйнберг, Джон ; Тардос, Ева (2006), Разработка алгоритмов , Аддисон Уэсли, стр. 94–97..
30. Эппштейн, Дэвид (2009), «Проверка двудольности геометрических графов пересечений», ACM Transactions on Algorithms , 5 (2): Art. 15, arXiv : cs.CG/0307023 , doi :10.1145/1497290.1497291, MR  2561751, S2CID  60496.
31. Яннакакис, Михалис (1978), «NP-полные задачи удаления узлов и ребер», Труды 10-го симпозиума ACM по теории вычислений (STOC '78) , стр. 253–264, doi : 10.1145/800133.804355 , S2CID  363248
32. Рид, Брюс ; Смит, Кейли; Ветта, Адриан (2004), «Нахождение нечетных трансверсалей цикла», Operations Research Letters , 32 (4): 299–301, CiteSeerX 10.1.1.112.6357 , doi :10.1016/j.orl.2003.10.009, MR  2057781 .
33. Го, Джионг; Грамм, Йенс; Хюффнер, Фальк; Нидермейер, Рольф; Вернике, Себастьян (2006), «Алгоритмы с фиксированными параметрами на основе сжатия для бипартизации множества вершин и ребер с обратной связью», Журнал компьютерных и системных наук , 72 (8): 1386–1396, doi : 10.1016/j.jcss.2006.02.001
34. Ахуджа, Равиндра К.; Магнанти, Томас Л.; Орлин, Джеймс Б. (1993), "12. Назначения и сопоставления", Сетевые потоки: теория, алгоритмы и приложения , Prentice Hall, стр. 461–509.
35. Ахуджа, Магнанти и Орлин (1993), стр. 463: «Недвудольные задачи сопоставления решить сложнее, поскольку они не сводятся к стандартным задачам сетевого потока».
36. Хопкрофт, Джон Э .; Карп, Ричард М. (1973), « Алгоритм n ^5/2 для максимального паросочетания в двудольных графах», SIAM Journal on Computing , 2 (4): 225–231, doi :10.1137/0202019.
37. Ахуджа, Магнанти и Орлин (1993), Приложение 12.1 Двустороннее назначение персонала, стр. 463–464.
38. Робинсон, Сара (апрель 2003 г.), «Находят ли студенты-медики свой (наилучший возможный) вариант?» (PDF) , SIAM News (3): 36, заархивировано из оригинала (PDF) 2016-11-18 , извлечено 2012-08-27.
39. Дульмейдж и Мендельсон (1958).
40. Мун, Тодд К. (2005), Кодирование с исправлением ошибок: математические методы и алгоритмы, John Wiley & Sons, стр. 638, ISBN 9780471648000.
41. Мун (2005), стр. 686.
42. Кассандр, Христос Г.; Лафортюн, Стефан (2007), Введение в дискретные событийные системы (2-е изд.), Springer, стр. 224, ISBN 9780387333328.
43. Грюнбаум, Бранко (2009), Конфигурации точек и линий, Graduate Studies in Mathematics , т. 103, Американское математическое общество , стр. 28, ISBN 9780821843086.

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

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