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

Проблема реализации графа является проблемой решения в теории графов . Учитывая конечную последовательность $(d_{1},\dots ,d_{n})$ натуральных чисел, проблема состоит в том, существует ли помеченный простой граф такой, что $(d_{1},\dots ,d_{n})$ — последовательность степеней этого графа.

Решения

Задача может быть решена за полиномиальное время . Один из методов демонстрации этого использует алгоритм Гавела – Хакими, строящий специальное решение с использованием рекурсивного алгоритма . В качестве альтернативы, следуя характеристике, данной теоремой Эрдеша – Галлаи , проблему можно решить, проверив справедливость $n$ неравенства.

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

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

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

Подобные задачи описывают последовательности степеней простых двудольных графов или степеней последовательности простых ориентированных графов . Первая проблема — это так называемая проблема двудольной реализации . Вторая известна как проблема реализации орграфа .

показали, что задача построения решения задачи реализации графа с дополнительным ограничением того, что каждое такое решение приходит с одинаковой вероятностью, имеет схему аппроксимации с полиномиальным временем для последовательностей степеней регулярных графов . Купер, Мартин и Гринхилл Общая проблема до сих пор не решена.