Задача о реализации графа — задача разрешимости в теории графов. Задана конечная последовательность натуральных чисел, задача спрашивает, существует ли такой простой граф, в котором — последовательность степеней вершин этого графа.
Решения
Задача может быть решена за полиномиальное время. Одним из примеров таких решений является алгоритм Гавела — Хакими, в основе которого лежит рекурсия. .. Задачу также можно решить путем проверки справедливости неравенств, используя теорему Эрдёша — Галлаи. .
Примечания
Категория:Вычислительные задачи теории графов