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

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

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

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

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

Примеры

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

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

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

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

Каждое дерево двудольное.
Циклические графы с четным числом вершин двудольны.
Каждый плоский граф , все грани которого имеют четную длину, двудольный. Частными случаями этого являются сеточные графы и квадратные графы , в которых каждая внутренняя грань состоит из 4 ребер, а каждая внутренняя вершина имеет четырех или более соседей.
Полный двудольный граф на т и п вершин, обозначим через К _{п, т} представляет собой двудольный граф , где U и V являются непересекающиеся множества размера т и п , соответственно, и Е соединяет каждую вершину в U со всеми вершинами из V . Следовательно, K _{m, n} имеет mn ребер. Тесно связаны с полными двудольными графами коронные графы , образованные из полных двудольных графов путем удаления ребер идеального соответствия . ${\ Displaystyle G = (U, V, E)}$
Графы гиперкубов , частичные кубы и медианные графы двудольные. В этих графах вершины могут быть помечены битовыми векторами таким образом, что две вершины являются смежными тогда и только тогда, когда соответствующие битовые векторы отличаются в одной позиции. Двойное разделение может быть образовано путем отделения вершин, битовые векторы которых имеют четное число единиц, от вершин с нечетным числом единиц. Деревья и квадратные графы образуют примеры медианных графов, и каждый медианный граф является частичным кубом.

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

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

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

Граф двудольный тогда и только тогда, когда он не содержит нечетного цикла .
Граф двудольный тогда и только тогда, когда он может быть 2-раскрашен (т.е. его хроматическое число меньше или равно 2).
Любой двудольный граф, состоящий из вершин, может иметь не более чем ребер. ${\ displaystyle n}$ ${\ Displaystyle п ^ {2} / 4}$
Спектр графа симметричен тогда и только тогда , когда это двудольный граф.

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

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

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

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

Степень

Для вершины количество смежных вершин называется степенью вершины и обозначается . Формула суммы степеней для двудольного графа утверждает, что ${\ 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)}$

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

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

Biadjacency матрица из двудольного графа является (0,1) матрицами размера , который имеет по одному для каждой пары смежных вершин и нуля для несмежных вершин. Матрицы взаимосопряженности могут использоваться для описания эквивалентностей между двудольными графами, гиперграфами и ориентированными графами. ${\ Displaystyle (U, V, E)}$ ${\ Displaystyle | U | \ раз | V |}$

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Languages

In other projects