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

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

Решения

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

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

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

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

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

Ссылки

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