Задача реализации графа - Graph realization problem

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

Решения

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

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

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

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

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

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

Рекомендации