Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пример двудольного графа без циклов
Полный двудольный граф с т = 5 и п = 3

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

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

Часто пишут для обозначения двудольного графа, разбиение которого имеет части и , с обозначением ребер графа. Если двудольный граф не связан , он может иметь более одного двудольного графа ; [5] в этом случае нотация помогает указать одно конкретное разделение, которое может иметь значение в приложении. Если , то есть, если два подмножества имеют одинаковую мощность , то это называется сбалансированным двудольным графом. [3] Если все вершины на одной стороне двудольного деления имеют одинаковую степень , то это называется бирегулярным .

Примеры [ править ]

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

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

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

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

  • Каждое дерево двудольное. [4]
  • Циклические графы с четным числом вершин двудольны. [4]
  • Каждый плоский граф , все грани которого имеют четную длину, двудольный. [9] Частными случаями этого являются сеточные графы и квадратные графы , в которых каждая внутренняя грань состоит из 4 ребер, а каждая внутренняя вершина имеет четырех или более соседей. [10]
  • Полный двудольный граф на т и п вершин, обозначим через К п, т представляет собой двудольный граф , где U и V являются непересекающиеся множества размера т и п , соответственно, и Е соединяет каждую вершину в U со всеми вершинами из V . Отсюда следует, что K m, n имеет mn ребер. [11] Тесно связаны с полными двудольными графами коронные графы , образованные из полных двудольных графов путем удаления ребер идеального паросочетания.. [12]
  • Графы гиперкубов , частичные кубы и медианные графы двудольные. В этих графах вершины могут быть помечены битовыми векторами таким образом, что две вершины являются смежными тогда и только тогда, когда соответствующие битовые векторы отличаются в одной позиции. Двучастие можно сформировать путем отделения вершин, битовые векторы которых имеют четное число единиц, от вершин с нечетным числом единиц. Деревья и квадратные графы образуют примеры медианных графов, и каждый медианный граф является частичным кубом. [13]

Свойства [ править ]

Характеристика [ править ]

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

  • Граф двудольный тогда и только тогда, когда он не содержит нечетного цикла . [14]
  • Граф двудольный тогда и только тогда, когда он может быть 2-раскрашен (т.е. его хроматическое число меньше или равно 2). [3]
  • Спектр графа симметричен тогда и только тогда , когда это двудольный граф. [15]

Теорема Кёнига и совершенные графы [ править ]

В двудольных графах размер минимального покрытия вершин равен размеру максимального соответствия ; это теорема Кёнига . [16] [17] Альтернативная и эквивалентная форма этой теоремы состоит в том, что размер максимального независимого множества плюс размер максимального соответствия равен количеству вершин. В любом графе без изолированных вершин размер минимального покрытия ребер плюс размер максимального соответствия равняется количеству вершин. [18]Комбинирование этого равенства с теоремой Кёнига приводит к тому, что в двудольных графах размер минимального покрытия ребер равен размеру максимального независимого множества, а размер минимального покрытия ребер плюс размер минимального покрытия вершин равно количеству вершин.

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

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

Степень [ править ]

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

Последовательность степеней двудольного графа - это пара списков, каждый из которых содержит степени двух частей и . Например, полный двудольный граф K 3,5 имеет последовательность степеней . Изоморфные двудольные графы имеют одинаковую последовательность степеней. Однако последовательность степеней, как правило, не однозначно идентифицирует двудольный граф; в некоторых случаях неизоморфные двудольные графы могут иметь одинаковую последовательность степеней.

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

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

Biadjacency матрица из двудольного графа является (0,1) матрицами размера , который имеет по одному для каждой пары смежных вершин и нуля для несмежных вершин. [21] Матрицы взаимосопряженности могут использоваться для описания эквивалентности двудольных графов, гиперграфов и ориентированных графов.

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

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

Алгоритмы [ править ]

Проверка двудольности [ править ]

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

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

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

Нечетное прохождение цикла [ править ]

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

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

Проблема бипартизации ребер - это алгоритмическая проблема удаления как можно меньшего количества ребер, чтобы граф стал двудольным, а также важной проблемой в алгоритмике модификации графов. Эта проблема также решаема с фиксированными параметрами и может быть решена во времени , [29] где  k - количество ребер, которые нужно удалить, а  m - количество ребер во входном графе.

Соответствие [ править ]

Основная статья: Соответствие (теория графов)

Соответствия в графе представляет собой подмножество его ребер, никакие два из которых разделяют конечную точку. Алгоритмы с полиномиальным временем известны для многих алгоритмических проблем сопоставлений, включая максимальное сопоставление (поиск сопоставления, в котором используется как можно больше ребер), сопоставление максимального веса и стабильное сопоставление . [30] Во многих случаях задачи сопоставления проще решить на двудольных графах, чем на недвудольных графах, [31] и многие алгоритмы сопоставления, такие как алгоритм Хопкрофта – Карпа для сопоставления максимальной мощности [32], работают правильно только на двудольных входах. .

В качестве простого примера предположим, что все люди ищут работу из набора рабочих мест, и не все люди подходят для всех рабочих мест. Эту ситуацию можно смоделировать как двудольный граф, в котором ребро соединяет каждого соискателя с каждой подходящей работой. [33] согласования идеально описывает способ одновременно удовлетворяющий всем лицам , ищущим работу и заполнение всех рабочих мест; Теорема Холла о браке дает характеристику двудольных графов, которая допускает совершенное сопоставление. Национальный Resident Matching Программа применяет методы график соответствия , чтобы решить эту проблему для американских медицинских студентов , ищущих работу и больницы ординатуры рабочих мест. [34]

Разложение Dulmage-Менделсон является структурным разложением двудольных графов , который является полезным в поиске максимального паросочетания. [35]

Дополнительные приложения [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Дистель, Рейнард (2005), Теория графов , Тексты для выпускников по математике , Springer, ISBN 978-3-642-14278-9
  2. ^ Асратян, Армен С .; Денли, Тристан MJ; Хэггквист, Роланд (1998), Двудольные графы и их приложения , Cambridge Tracts in Mathematics, 131 , Cambridge University Press, ISBN 9780521593458.
  3. ^ a b c Asratian, Denley & Häggkvist (1998) , стр. 7.
  4. ^ a b c Шайнерман, Эдвард Р. (2012), Математика: дискретное введение (3-е изд.), Cengage Learning, стр. 363, ISBN 9780840049421.
  5. ^ Chartrand, Гэри ; Чжан, Пинг (2008), Теория хроматических графов , Дискретная математика и ее приложения, 53 , CRC Press, стр. 223, ISBN 9781584888000.
  6. ^ Вассерман, Стэнли ; Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения , структурный анализ в социальных науках, 8 , Cambridge University Press, стр. 299–302, ISBN 9780521387071.
  7. ^ Нидермейер, Рольф (2006), Приглашение к алгоритмам с фиксированными параметрами , Оксфордская серия лекций по математике и ее приложениям, Oxford University Press, стр. 20–21, ISBN 978-0-19-856607-6
  8. ^ Брейси, Роберт (2012), «О графической интерпретации монет третьего года Ирода», в Jacobson, David M .; Коккинос, Никос (ред.), Иудея и Рим в монетах 65 г. до н.э. - 135 г. н.э .: доклады, представленные на международной конференции, организованной Спинком, 13–14 сентября 2010 г. , Spink & Son , стр. 65–84
  9. ^ Сойфер, Александр (2008), Математическая раскраска , Springer-Verlag, стр. 136-137, ISBN 978-0-387-74640-1. Этот результат иногда называют «теоремой двух цветов»; Сойфер связывает это с известной статьей Альфреда Кемпе 1879 года, содержащей ложное доказательство теоремы о четырех цветах .
  10. ^ Бандельт, Х.-Дж .; Чепой, В .; Эппштейн, Д. (2010), "Комбинаторика и геометрия конечных и бесконечных квадратных графов", Журнал SIAM по дискретной математике , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301 , S2CID 10788524 .
  11. ^ Асратян, Denley & Häggkvist (1998) , стр. 11.
  12. ↑ Архидьякон, Д .; Дебовский, М .; Dinitz, J .; Гавлас, Х. (2004), "Циклические системы в полном двудольном графе минус однофакторный", Дискретная математика , 284 (1–3): 37–43, DOI : 10.1016 / j.disc.2003.11.021.
  13. ↑ Овчинников, Сергей (2011), Графики и кубы , Universitext, Springer. См. Особенно главу 5, «Частичные кубы», стр. 127–181.
  14. ^ Асратян, Denley & Häggkvist (1998) , теорема 2.1.3, стр. 8. Asratian et al. приписывают эту характеристику статье Денеса Кёнига 1916 года. Для бесконечных графов этот результат требует аксиомы выбора .
  15. ^ Биггс, Норман (1994), алгебраическая теория графов , Кембриджская математическая библиотека (2-е изд.), Cambridge University Press, стр. 53, ISBN 9780521458979.
  16. ^ Konig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai лапок , 38 : 116-119.
  17. ^ Гросс, Джонатан Л .; Йеллен, Джей (2005), Теория графов и ее приложения , Дискретная математика и ее приложения (2-е изд.), CRC Press, стр. 568, ISBN 9781584885054.
  18. ^ Chartrand, Гэри; Чжан, Пинг (2012), Первый курс теории графов , Courier Dover Publications, стр. 189–190, ISBN 9780486483689.
  19. ^ Бела Боллобас (1998), Современная теория графов , Тексты для выпускников по математике, 184 , Springer, стр. 165, ISBN 9780387984889.
  20. ↑ Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (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  .
  21. ^ Асратян, Denley & Häggkvist (1998) , стр. 17.
  22. ^ А.А. Сапоженко (2001) [1994], «Гиперграф» , Энциклопедия математики , EMS Press
  23. ^ Brualdi, Ричард А .; Харари, Фрэнк ; Миллер, Зевите (1980), "Bigraphs по сравнению с орграфами с помощью матриц", Журнал теории графов , 4 (1): 51-73, DOI : 10.1002 / jgt.3190040107 , МР 0558453 . Brualdi et al. приписывают идею этой эквивалентности Далмаджу, Алабама; Мендельсон, Н. С. (1958), "Накрытия двудольных графов", Canadian Journal математики , 10 : 517-534, DOI : 10,4153 / CJM-1958-052-0 , MR 0097069 .
  24. ^ Седжвик, Роберт (2004), Алгоритмы на Java, Часть 5: Графические алгоритмы (3-е изд.), Аддисон Уэсли, стр. 109–111.
  25. ^ Клейнберг, Джон ; Тардос, Ива (2006), Разработка алгоритмов , Аддисон Уэсли, стр. 94–97..
  26. ^ Эппштейн, Дэвид (2009), «Проверка двудольности геометрических графов пересечений», ACM Transactions on Algorithms , 5 (2): Art. 15, Arxiv : cs.CG/0307023 , DOI : 10,1145 / 1497290,1497291 , МР 2561751 , S2CID 60496  .
  27. ^ Yannakakis, Михалис (1978), "Узел и края удаления NP-полных задач", Труды 10 - го симпозиума ACM по теории вычислений (STOC '78) , С. 253-264,. DOI : 10.1145 / 800133,804355 , S2CID 363248 
  28. ^ Рид, Брюс ; Смит, Кейли; Vetta, Адриан (2004), "Обнаружение нечетных трансверсалей цикла" Исследование операций Letters , 32 (4): 299-301, CiteSeerX 10.1.1.112.6357 , DOI : 10.1016 / j.orl.2003.10.009 , МР 2057781  .
  29. ^ Го, Цзюн; Грамм, Йенс; Хюффнер, Фальк; Нидермайер, Рольф; Вернике, Себастьян (2006), «Основанные на сжатии алгоритмы с фиксированными параметрами для набора вершин с обратной связью и бипартизации ребер», Журнал компьютерных и системных наук , 72 (8): 1386–1396, DOI : 10.1016 / j.jcss.2006.02. 001
  30. ^ Ахуджа, Равиндра К .; Magnanti, Thomas L .; Орлин, Джеймс Б. (1993), "12. Назначения и сопоставления", Сетевые потоки: теория, алгоритмы и приложения , Прентис Холл, стр. 461–509..
  31. ^ Ахаджа, Magnanti & Орлин (1993) , стр. 463: «Проблемы недвольного сопоставления труднее решить, потому что они не сводятся к стандартным проблемам сетевого потока».
  32. ^ Хопкрофт, Джон Э .; Карп, Ричард М. (1973), "О п 5/2 алгоритма максимальных паросочетаний в двудольных графах", SIAM журнал по вычислениям , 2 (4): 225-231, DOI : 10,1137 / 0202019.
  33. ^ Ахадж, Magnanti & Орлин (1993) , 12.1 Применение Двудольного персонал Назначения, стр. 463-464.
  34. ↑ Робинсон, Сара (апрель 2003 г.), «Встречаются ли студенты-медики со своим (наилучшим возможным) совпадением?» (PDF) , SIAM Новости (3): 36, архивируются от оригинала (PDF) на 2016-11-18 , извлекаются 2012-08-27 .
  35. ^ Dulmage и Мендельсон (1958) .
  36. ^ Мун, Тодд К. (2005), Кодирование с исправлением ошибок: математические методы и алгоритмы , John Wiley & Sons, стр. 638, ISBN 9780471648000.
  37. ^ Луна (2005) , стр. 686.
  38. ^ Cassandras, Christos G .; Лафортюн, Стефан (2007), Введение в системы дискретных событий (2-е изд.), Springer, стр. 224, ISBN 9780387333328.
  39. ^ Грюнбаум, Бранко (2009), Конфигурации точек и линий , Аспирантура по математике , 103 , Американское математическое общество , стр. 28, ISBN 9780821843086.

Внешние ссылки [ править ]

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