Русская Википедия:Задача двудольной реализации
Задача двудольной реализации — это классическая задача разрешимости в теории графов. Даны две конечные последовательности натуральных чисел <math>(a_1,\dots,a_n)</math> и <math>(b_1,\dots,b_n)</math>, спрашивается, существует ли простой двудольный граф такой, что <math>(a_1,\dots,a_n),(b_1,\dots,b_n)</math> являются последовательностями степеней этого двудольного графа.
Решения
Задача принадлежит классу сложности P. Согласно Шаблон:Не переведено 5, для решения данной задачи нужно проверить, что <math display="inline">\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n b_i</math>, а также что для каждого <math>k\leq n</math> верно, что <math display="inline">\sum\limits_{i=1}^k a_i \leq \sum\limits_{i=1}^n \min(b_i, k)</math>.
В других обозначениях
Задача может быть поставлена в терминах матриц из нулей и единиц. Если такой двудольный граф существует, то у его матрицы бисмежности суммы столбцов и суммы строк соответствуют <math>(a_1,\ldots,a_n)</math> и <math>(b_1,\ldots,b_n)</math>. Таким образом, задача может быть сформулирована как поиск 0-1-матрицы для данных сумм столбцов и строк. В классической литературе задача иногда формулируется в терминах таблиц сопряжённости как задача поиска таблицы сопряжённости с заданными маргинальными частотами. Ещё одна формулировка задачи возможна в терминах последовательностей степеней простых ориентированных графов с не более чем одной петлёй в каждой вершине. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа, и задача формулируется так: «Верно ли, что пары неотрицательных чисел <math>((a_1,b_1), \dots, (a_n,b_n))</math> соответствуют парам полустепеней захода и исхода некоторого ориентированного графа с не более чем одной петлёй в каждой вершине?»
Связанные задачи
Аналогичные задачи описывают последовательности степеней простых графов и простых ориентированных графов. Соответствующие задачи известны как задача о реализации графа и Шаблон:Не переведено 5.
Задачу двудольной реализации можно также ставить в виде вопроса о том, существует ли подграф полного двудольного графа с заданной последовательностью степеней. В задаче Хичкока[1] необходимо найти подграф с заданными степенями вершин, который при этом также минимизирует сумму цен, заданных для каждого ребра полного двудольного графа. Другим обобщением двудольной реализации является о f-факторе для двудольных графов, в которой подграф, вершины которого обладают заданными степенями, нужно найти у некоторого заданного двудольного графа.
Задача равномерной выборки двудольного графа с фиксированной последовательностью степеней заключается в построении решения задачи двудольной реализации с дополнительным ограничением, что каждое такое решение получается с одной и той же вероятностью. Как показала Катерина Гринхил, эта задача принадлежит классу FPTAS для регулярных двудольных графов без 1-фактораШаблон:Sfn. В дальнейшем Эрдёш с соавторами показали принадлежность данному классу для полурегулярных последовательностейШаблон:Sfn. В случае произвольных двудольных графов задача остаётся нерешённой.
Примечания
Литература
Шаблон:Rq Шаблон:Изолированная статья
- ↑ Транспортная задача, в которой существуют дуги от каждого поставщика к каждому потребителю, известна как транспортная задача Хичкока или транспортная задача Хичкока — КупмансаШаблон:Harv. В российской литературе она больше известна как транспортная задача в матричной постановке.
