Задача двудольной реализации — это классическая задача разрешимости в теории графов. Даны две конечные последовательности натуральных чисел и , спрашивается, существует ли простой двудольный граф такой, что являются последовательностями степеней этого двудольного графа.
Решения Задача принадлежит классу сложности P. Согласно , для решения данной задачи нужно проверить, что , а также что для каждого верно, что .
В других обозначениях Задача может быть поставлена в терминах матриц из нулей и единиц. Если такой двудольный граф существует, то у его матрицы бисмежности суммы столбцов и суммы строк соответствуют и . Таким образом, задача может быть сформулирована как поиск 0-1-матрицы для данных сумм столбцов и строк. В классической литературе задача иногда формулируется в терминах таблиц сопряжённости как задача поиска таблицы сопряжённости с заданными маргинальными частотами. Ещё одна формулировка задачи возможна в терминах последовательностей степеней простых ориентированных графов с не более чем одной петлёй в каждой вершине. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа, и задача формулируется так: «Верно ли, что пары неотрицательных чисел соответствуют парам полустепеней захода и исхода некоторого ориентированного графа с не более чем одной петлёй в каждой вершине?»
Связанные задачи Аналогичные задачи описывают последовательности степеней простых графов и простых ориентированных графов. Соответствующие задачи известны как задача о реализации графа и .
Задачу двудольной реализации можно также ставить в виде вопроса о том, существует ли подграф полного двудольного графа с заданной последовательностью степеней. В задаче ХичкокаТранспортная задача, в которой существуют дуги от каждого поставщика к каждому потребителю, известна как транспортная задача Хичкока или транспортная задача Хичкока — Купманса. В российской литературе она больше известна как транспортная задача в матричной постановке. необходимо найти подграф с заданными степенями вершин, который при этом также минимизирует сумму цен, заданных для каждого ребра полного двудольного графа. Другим обобщением двудольной реализации является о f-факторе для двудольных графов, в которой подграф, вершины которого обладают заданными степенями, нужно найти у некоторого заданного двудольного графа.
Задача равномерной выборки двудольного графа с фиксированной последовательностью степеней заключается в построении решения задачи двудольной реализации с дополнительным ограничением, что каждое такое решение получается с одной и той же вероятностью. Как показала Катерина Гринхил, эта задача принадлежит классу FPTAS для регулярных двудольных графов без 1-фактора. В дальнейшем Эрдёш с соавторами показали принадлежность данному классу для полурегулярных последовательностей. В случае произвольных двудольных графов задача остаётся нерешённой.
Примечания
Литература
Категория:Вычислительные задачи теории графов Категория:Двудольные графы