Проблема реализации орграфа - Digraph realization problem - Wikipedia

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

Решения

Задача относится к классу сложности п. Известно два алгоритма, подтверждающие это. Первый подход дается Алгоритмы Клейтмана – Ванга построение специального решения с использованием рекурсивный алгоритм. Второй - характеристика Теорема Фулкерсона – Чена – Ансти, т.е. необходимо проверить правильность ${\displaystyle n}$ неравенства.

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

Проблема также может быть сформулирована в терминах нуля или единицы. матрицы. Связь можно увидеть, если понять, что каждый ориентированный граф имеет матрица смежности где суммы столбцов и суммы строк соответствуют ${\displaystyle (a_{1},\cdots ,a_{n})}$ и ${\displaystyle (b_{1},\ldots ,b_{n})}$. Обратите внимание, что диагональ матрицы содержит только нули. Проблема тогда часто обозначается 0-1-матрицы для заданных сумм строк и столбцов. В классической литературе проблема иногда формулировалась в контексте таблицы непредвиденных обстоятельств к таблицы непредвиденных обстоятельств с заданными маржинальными числами.

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

Подобные проблемы описывают последовательности степеней из простые графики, простые ориентированные графы с петли, и простые двудольные графы. Первая проблема - это так называемая задача реализации графа. Второй и третий эквивалентны и известны как проблема двусторонней реализации. Чен (1966) дал характеристику направленные мультиграфы с ограниченным числом параллельных дуг и петель до заданного последовательность степеней. Дополнительное ограничение ацикличности ориентированного графа известно как осознание дага. Нихтерляйн и Хартунг (2012) доказал NP-полнота этой проблемы. Бергер и Мюллер-Ханнеманн (2011) показал, что класс противоположные последовательности в п. Проблема равномерная выборка ориентированного графа с фиксированной степенью последовательности состоит в том, чтобы построить решение проблемы реализации орграфа с дополнительным ограничением, что каждое такое решение приходит с одинаковой вероятностью. Эта проблема была показана в FPTAS за регулярные последовательности к Кэтрин Гринхилл  (2011 ) Общая проблема до сих пор не решена.

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

• Чен, Вай-Кай (1966), «О реализации (п,s) -график с заданными степенями », Журнал Института Франклина, 103: 406–422
• Нихтерлейн, Андре; Хартунг, Сепп (2012), "NP-твердость и управляемость с фиксированными параметрами реализации последовательностей степеней с направленными ациклическими графами", Журнал Института Франклина, 7318: 283–292
• Бергер, Аннабель; Мюллер-Ханнеманн, Маттиас (2011), «Даг-реализации направленных последовательностей степеней», Материалы 18-й Международной конференции по основам теории вычислений.: 264–275
• Гринхилл, Кэтрин (2011), «Полиномиальная оценка времени перемешивания цепи Маркова для выборки регулярных ориентированных графов», Электронный журнал комбинаторики, 18