Проблема двусторонней реализации - Bipartite realization problem

В проблема двусторонней реализации это классический проблема решения в теория графов, филиал комбинаторика. Для двух конечных последовательностей ${ Displaystyle (а_ {1}, точки, а_ {п})}$ и ${ displaystyle (b_ {1}, dots, b_ {n})}$ натуральных чисел, задача спрашивает, есть ли помеченные простой двудольный граф такой, что ${ displaystyle (a_ {1}, dots, a_ {n}), (b_ {1}, dots, b_ {n})}$ это последовательность степеней этого двудольного графа.

Решения

Задача относится к классу сложности п. Это можно доказать с помощью Теорема Гейла – Райзера, т.е. необходимо проверить правильность ${ displaystyle n}$ неравенства.

Другие обозначения

Проблема также может быть сформулирована в терминах нуля или единицы. матрицы. Связь можно увидеть, если понять, что каждый двудольный граф имеет матрица двойственности где суммы столбцов и суммы строк соответствуют ${ Displaystyle (а_ {1}, ldots, а_ {п})}$ и ${ displaystyle (b_ {1}, ldots, b_ {n})}$ . Проблема тогда часто обозначается 0-1-матрицы для заданных сумм строк и столбцов. В классической литературе проблема иногда формулировалась в контексте таблицы непредвиденных обстоятельств к таблицы непредвиденных обстоятельств с заданными маржинальными числами. Третья формулировка заключается в последовательности степеней простых ориентированных графов с не более чем одной петлей на вершину. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа. Когда пары неотрицательных целых чисел ((а₁,б₁), ..., (а_п,б_п)) пары степень-выход помеченного ориентированного графа с не более чем одной петлей на вершину?

Связанные проблемы

Подобные проблемы описывают последовательности степеней из простые графики и простые ориентированные графы. Первая проблема - это так называемая задача реализации графа. Второй известен как задача реализации орграфа. Проблема двудольной реализации эквивалентна вопросу, существует ли помеченная двудольная подграф из полный двудольный граф в заданной степени последовательности. В проблема Хичкока запрашивает такой подграф, минимизирующий сумму затрат на каждое ребро, которые даны для полного двудольного графа. Дальнейшее обобщение - это Проблема f-фактора для двудольных графов, т.е. для данного двудольного графа ищется подграф, обладающий некоторой последовательностью степеней. Проблема равномерная выборка двудольного графа с фиксированной степенью последовательности состоит в том, чтобы построить решение для задачи двусоставной реализации с дополнительным ограничением, что каждое такое решение приходит с одинаковой вероятностью. Эта проблема оказалась в FPTAS за регулярные последовательности к Кэтрин Гринхилл ^[1] (для правильных двудольных графов с запрещенным 1-факторный ) и для полурегулярные последовательности Эрдеш и др.^[2] Общая проблема до сих пор не решена.

Проблема двусторонней реализации - Bipartite realization problem

Содержание

Решения

Другие обозначения

Связанные проблемы

Рекомендации