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

редактировать

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

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

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

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

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

Содержание

1 Примеры
2 Свойства
- 2.1 Характеристика
- 2.2 Теорема Кенига и совершенные графы
- 2.3 Степень
- 2.4 Связь с гиперграфами и ориентированными графами
3 Алгоритмы
- 3.1 Проверка двудольности
- 3.2 Пересечение нечетного цикла
- 3.3 Согласование
4 Дополнительные приложения
5 См. Также
6 Ссылки
7 Внешние ссылки

Примеры

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

Степень

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

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

\ sum_ {v \ in V} \ deg (v) = \ sum_ {u \ in U} \ deg (u) = | E | \,.

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

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

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

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

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

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

Алгоритмы

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

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

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

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

Transversal нечетного цикла

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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