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