Проблема реализации орграфа

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

Решения [ править ]

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

Другие обозначения [ править ]

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

Связанные проблемы [ править ]

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

Ссылки [ править ]

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