WikiDer > Проблема реализации орграфа - Википедия

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

Решения

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

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

Проблема также может быть сформулирована в терминах нуля или единицы. матрицы. Связь можно увидеть, если понять, что каждый ориентированный граф имеет матрица смежности где суммы столбцов и суммы строк соответствуют ${ Displaystyle (а_ {1}, cdots, а_ {п})}$ и ${ 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