Задача двудольной реализации

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Задача принадлежит классу сложности P. Согласно теореме Гейла — Райзера[англ.], для решения данной задачи нужно проверить, что , а также что для каждого верно, что .

В других обозначениях

[править | править код]

Задача может быть поставлена в терминах матриц из нулей и единиц. Если такой двудольный граф существует, то у его матрицы бисмежности суммы столбцов и суммы строк соответствуют и . Таким образом, задача может быть сформулирована как поиск 0-1-матрицы для данных сумм столбцов и строк. В классической литературе задача иногда формулируется в терминах таблиц сопряжённости как задача поиска таблицы сопряжённости с заданными маргинальными частотами. Ещё одна формулировка задачи возможна в терминах последовательностей степеней простых ориентированных графов с не более чем одной петлёй в каждой вершине. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа, и задача формулируется так: «Верно ли, что пары неотрицательных чисел соответствуют парам полустепеней захода и исхода некоторого ориентированного графа с не более чем одной петлёй в каждой вершине?»

Связанные задачи

[править | править код]

Аналогичные задачи описывают последовательности степеней простых графов и простых ориентированных графов. Соответствующие задачи известны как задача о реализации графа и задача реализации ориентированного графа[англ.].

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

Задача равномерной выборки двудольного графа с фиксированной последовательностью степеней заключается в построении решения задачи двудольной реализации с дополнительным ограничением, что каждое такое решение получается с одной и той же вероятностью. Как показала Катерина Гринхил, эта задача принадлежит классу FPTAS для регулярных двудольных графов без 1-фактора[2]. В дальнейшем Эрдёш с соавторами показали принадлежность данному классу для полурегулярных последовательностей[3]. В случае произвольных двудольных графов задача остаётся нерешённой.

Примечания

[править | править код]
  1. Транспортная задача, в которой существуют дуги от каждого поставщика к каждому потребителю, известна как транспортная задача Хичкока или транспортная задача Хичкока — Купманса(Беллман, Дрейфус 1965, 103). В российской литературе она больше известна как транспортная задача в матричной постановке.
  2. Greenhill, 2011.
  3. Erdős, Kiss, Miklós, Soukup, 2015.

Литература

[править | править код]
  • Gale D. A theorem on flows in networks // Pacific J. Math.. — 1957. — Т. 7, вып. 2. — С. 1073–1082. — doi:10.2140/pjm.1957.7.1073.
  • Ryser H. J. Combinatorial Mathematics. — John Wiley & Sons, 1963.
  • Catherine Greenhill. A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs // Electronic Journal of Combinatorics. — 2011. — Т. 18, вып. 1. — С. 234. — Bibcode2011arXiv1105.0457G. — arXiv:1105.0457.
  • Erdős P.L., Kiss S.Z., Miklós I., Soukup L. Approximate Counting of Graphical Realizations // PLOS ONE. — 2015. — Т. 10, вып. 7. — С. e0131300. — doi:10.1371/journal.pone.0131300. — Bibcode2015PLoSO..1031300E. — arXiv:1301.7523.
  • Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. — Москва: «Наука» Главная редакция физико-математической литературы., 1965.