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

Digraph realization problem - Wikipedia

В задача реализации орграфа это проблема решения в теория графов. Даны пары неотрицательных целые числа , проблема спрашивает, есть ли помеченный простой ориентированный граф так что каждый вершина имеет степень и превосходить .

Решения

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

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

Проблема также может быть сформулирована в терминах нуля или единицы. матрицы. Связь можно увидеть, если понять, что каждый ориентированный граф имеет матрица смежности где суммы столбцов и суммы строк соответствуют и . Обратите внимание, что диагональ матрицы содержит только нули. Проблема тогда часто обозначается 0-1-матрицы для заданных сумм строк и столбцов. В классической литературе проблема иногда формулировалась в контексте таблицы непредвиденных обстоятельств к таблицы непредвиденных обстоятельств с заданными маржинальными числами.

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

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

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

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