Задача реализации графа

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

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

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

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

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

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

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

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

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