Обычно каждый строит граф, а затем задает вопросы о разложении собственных значений матрицы смежности (или некоторого близкого родственника, такого как лапласиан ) (также называемого спектрами графа ).
Но как насчет обратной проблемы? Учитывая собственных значений, можно (эффективно) найти граф, который имеет эти спектры?
Я подозреваю, что в целом это трудно сделать (и может быть эквивалентно GI), но что, если вы немного ослабите некоторые условия? Что если вы поставите условия, при которых не существует множества собственных значений? Как насчет разрешения графиков, которые имеют "близкие" спектры по некоторой метрике расстояния?
Любые ссылки или идеи будут приветствоваться.
РЕДАКТИРОВАТЬ :
Как указывает Суреш, если вы разрешаете неориентированные взвешенные графы с помощью собственных циклов, эта проблема становится довольно тривиальной. Я надеялся получить ответы на множестве неориентированных невзвешенных простых графов, но я был бы счастлив и простыми невзвешенными ориентированными графами.
Ответы:
Cvetcovic и др все в разделе 3.3 «Последние результаты в теории спектров графов» переходит алгоритмы для построения графов определенного спектра в некоторых особых случаях
источник
Даже вопрос о том, существует ли граф с заданным спектром, является сложным вопросом. Об этом свидетельствует открытая проблема определения, существует ли график обхвата 5 диаметром 2 и порядка 3250, спектр которого (если он существует) известен.
источник
Еще одно препятствие в определении вашего вопроса состоит в том, что это изоспектральные (те же самые собственные значения), но неизоморфные графы. Итак, учитывая список собственных значений в таком случае, какой график вы хотите? Может быть, вы просто хотите, чтобы алгоритм возвращал один случайный элемент из множества таких неизоморфных графов?
источник