Канонизация графа - Graph canonization

В теория графов, раздел математики, канонизация графа проблема с поиском каноническая форма данного графа грамм. Каноническая форма - это помеченный график Canon (грамм) то есть изоморфный к грамм, такой, что любой граф, изоморфный грамм имеет ту же каноническую форму, что и грамм. Таким образом, из решения проблемы канонизации графа, можно было бы также решить проблему изоморфизм графов: проверить, есть ли два графика грамм и ЧАС изоморфны, вычислить их канонические формы Canon (грамм) и Canon (ЧАС) и проверьте, идентичны ли эти две канонические формы.

Каноническая форма графа является примером полный инвариант графа: каждые два изоморфных графа имеют одну и ту же каноническую форму, а любые два неизоморфных графа имеют разные канонические формы.[1][2] И наоборот, любой полный инвариант графов можно использовать для построения канонической формы.[3] Множество вершин п-вершинный граф можно отождествить с целые числа от 1 до п, и с использованием такой идентификации каноническая форма графа также может быть описана как перестановка его вершин. Канонические формы графа также называют канонические обозначения,[4] канонизация графов также иногда называется канонизация графа.

Вычислительная сложность

Ясно, что проблема канонизации графа не меньше, чем вычислительно сложный как проблема изоморфизма графов. На самом деле изоморфизм графов четный AC0 -сводимый к канонизации графа. Однако вопрос о том, являются ли эти две проблемы эквивалент полиномиального времени.[2]

Хотя существование (детерминированных) полиномиальных алгоритмов для изоморфизма графов все еще остается открытой проблемой в теория сложности вычислений, в 1977 г. Ласло Бабай сообщил, что с вероятностью не менее 1 - exp (−O (п)), простой алгоритм классификации вершин производит каноническую разметку графа, выбираемого равномерно случайным образом из множества всех п-вершинные графы всего после двух шагов уточнения. Небольшие доработки и добавленное поиск в глубину step производят каноническую разметку таких равномерно выбранных случайных графов за линейное ожидаемое время. Этот результат проливает свет на то, почему многие известные алгоритмы изоморфизма графов хорошо себя ведут на практике.[5][6] Это был важный прорыв в вероятностная теория сложности который стал широко известен в своей рукописной форме и все еще цитировался как «неопубликованная рукопись» еще долгое время после того, как о нем доложили на симпозиуме.

Общеизвестной канонической формой является лексикографически наименьший график в класс изоморфизма, который является графом класса с лексикографически наименьшим матрица смежности рассматривается как линейная строка, однако вычисление лексикографически наименьшего графа выполняется NP-жесткий.[1]

Для деревьев краткий алгоритм канонизации полиномов, требующий O (n) пространства, представлен следующим образом: Читать (1972).[7] Начните с маркировки каждой вершины строкой 01. Итеративно для каждого нелистового x удалите начальный 0 и конечный 1 из метки x; затем отсортируйте метку x вместе с метками всех соседних листьев в лексикографическом порядке. Объедините эти отсортированные метки, добавьте обратно 0 в начале и 1 в конце, сделайте это новой меткой x и удалите соседние листья. Если остались две вершины, соедините их метки в лексикографическом порядке.

Приложения

Канонизация графов - это суть многих алгоритмов изоморфизма графов. Один из ведущих инструментов - Nauty.[8]

Обычное применение канонизации графов - в графическом сбор данных, в частности в химическая база данных Приложения.[9]

Номер идентификаторы за химические субстанции, Такие как Улыбки и ИнЧИ использовать этапы канонизации в своих вычислениях, которые по сути являются канонизацией графа, представляющего молекулу.[10][11][12]Эти идентификаторы предназначены для предоставления стандартного (а иногда и удобочитаемого) способа кодирования молекулярной информации и облегчения поиска такой информации в базах данных и в Интернете.

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

  1. ^ а б Арвинд, Викраман; Дас, Бирешвар; Кёблер, Йоханнес (2008), "Алгоритм лог-пространства для частичной канонизации двух деревьев", Компьютерные науки - теория и приложения: Третий международный симпозиум по компьютерным наукам в России, CSR 2008 Москва, Россия, 7-12 июня 2008 г., Труды, Конспект лекций по вычисл. Наук, 5010, Springer, Berlin, стр. 40–51, Дои:10.1007/978-3-540-79709-8_8, МИСТЕР  2475148.
  2. ^ а б Арвинд, В .; Дас, Бирешвар; Кёблер, Йоханнес (2007), "Пространственная сложность k-дерево изоморфизм ", Алгоритмы и вычисления: 18-й Международный симпозиум, ISAAC 2007, Сендай, Япония, 17-19 декабря 2007 г., Труды, Конспект лекций по вычисл. Наук, 4835, Springer, Berlin, стр. 822–833, Дои:10.1007/978-3-540-77120-3_71, МИСТЕР  2472661.
  3. ^ Гуревич, Юрий (1997), «От инвариантов к канонизации» (PDF), Бюллетень Европейской ассоциации теоретической информатики (63): 115–119, МИСТЕР  1621595.
  4. ^ Бабай, Ласло; Люкс, Евгений (1983), «Каноническая разметка графов», Proc. 15-й симпозиум ACM по теории вычислений, стр. 171–183, Дои:10.1145/800061.808746.
  5. ^ Бабай, Ласло (1977), К проблеме изоморфизма, неопубликованная рукопись.
  6. ^ Бабай, Ласло; Кучера, Л. (1979), "Каноническая маркировка графиков за линейное среднее время", Proc. 20-й ежегодный симпозиум IEEE по основам компьютерных наук, стр. 39–46, Дои:10.1109 / SFCS.1979.8.
  7. ^ Рид, Рональд С. (1972), «Кодирование различных видов немаркированных деревьев», Теория графов и вычисления, Academic Press, New York, pp. 153–182, МИСТЕР  0344150.
  8. ^ Маккей, Брендан Д .; Пиперно, Адольфо (2014), «Журнал символических вычислений», Практический изоморфизм графов, II, стр. 94–112, ISSN  0747-7171.
  9. ^ Кук, Дайан Дж .; Холдер, Лоуренс Б. (2007), «6.2.1. Каноническая маркировка», Данные графа майнинга, стр. 120–122, ISBN  0-470-07303-9.
  10. ^ Вейнингер, Дэвид; Вейнингер, Артур; Вейнингер, Джозеф Л. (май 1989 г.). «SMILES. 2. Алгоритм генерации уникальной нотации SMILES». Журнал химической информации и моделирования. 29 (2): 97–101. Дои:10.1021 / ci00062a008.
  11. ^ Келли, Брайан (май 2003 г.). «Каноникализация графа». Журнал доктора Добба.
  12. ^ Шайдер, Надин; Sayle, Roger A .; Ландрам, Грегори А. (октябрь 2015 г.). «Приведите свои атомы в порядок - реализация нового и надежного алгоритма молекулярной канонизации с открытым исходным кодом». Журнал химической информации и моделирования. 55 (10): 2111–2120. Дои:10.1021 / acs.jcim.5b00543. PMID  26441310.