В теории графов , раздел математики, граф канонизации является проблема нахождения канонической формы данного графа G . Каноническая форма представляет собой помеченный граф Canon ( G ), которая изоморфна с G , таким образом, что каждый граф, изоморфный G имеет такой же вид , как и канонический G . Таким образом, из решения проблемы канонизации графов можно также решить проблему изоморфизма графов : чтобы проверить, изоморфны ли два графа G и H , вычислить их канонические формы Canon ( G ) и Canon (H ) и проверьте, идентичны ли эти две канонические формы.
Каноническая форма графа является примером инварианта полного графа : каждые два изоморфных графа имеют одинаковую каноническую форму, и каждые два неизоморфных графа имеют разные канонические формы. [1] [2] И наоборот, любой полный инвариант графов может использоваться для построения канонической формы. [3] Множество вершин графа с n вершинами может быть идентифицировано целыми числами от 1 до n , и с использованием такой идентификации каноническая форма графа также может быть описана как перестановка его вершин. Канонические формы графы также называются каноническими маркировки , [4] и график канонизация также иногда называют графом канонизацию .
Вычислительная сложность
Ясно, что проблема канонизации графов не менее вычислительно сложна, чем проблема изоморфизма графов . На самом деле, изоморфизм графов даже AC 0 - приводимое в графе канонизации. Однако до сих пор остается открытым вопрос, эквивалентны ли эти две задачи по полиномиальному времени . [2]
Хотя существование (детерминированных) полиномиальных алгоритмов для изоморфизма графов все еще остается открытой проблемой в теории вычислительной сложности , в 1977 году Ласло Бабай сообщил, что с вероятностью не менее 1 - exp (−O ( n )) простой алгоритм классификации вершин дает каноническая разметка графа, выбираемого равномерно случайным образом из множества всех n- вершинных графов после всего лишь двух шагов уточнения. Небольшие модификации и добавленный шаг поиска в глубину производят каноническую маркировку таких равномерно выбранных случайных графов за линейное ожидаемое время. Этот результат проливает свет на то, почему многие известные алгоритмы изоморфизма графов хорошо себя ведут на практике. [5] [6] Это был важный прорыв в теории вероятностной сложности, которая стала широко известна в своей рукописной форме и все еще цитировалась как «неопубликованная рукопись» еще долгое время после того, как о ней было доложено на симпозиуме.
Общеизвестной канонической формой является лексикографически наименьший граф в классе изоморфизма , который представляет собой граф класса с лексикографически наименьшей матрицей смежности, рассматриваемый как линейная строка. Однако вычисление лексикографически наименьшего графа является NP-трудным . [1]
Для деревьев краткий алгоритм полиномиальной канонизации, требующий пространства O (n), представлен Ридом (1972) . [7] Начните с пометки каждой вершины строкой 01. Итеративно для каждого нелистового x удалите начальный 0 и конечный 1 из метки x; затем отсортируйте метку x вместе с метками всех соседних листьев в лексикографическом порядке. Объедините эти отсортированные метки, добавьте обратно 0 в начале и 1 в конце, сделайте это новой меткой x и удалите соседние листья. Если остались две вершины, соедините их метки в лексикографическом порядке.
Приложения
Канонизация графов - это суть многих алгоритмов изоморфизма графов. Один из ведущих инструментов - Nauty. [8]
Обычное применение канонизации графов - это анализ графических данных , в частности, в приложениях для химических баз данных . [9]
Ряд идентификаторов для химических веществ , такие , как улыбки и InChI шагов использования канонизации в их вычислениях, которая является по существу канонизации графа , который представляет собой молекулу. [10] [11] [12] Эти идентификаторы предназначены для предоставления стандартного (а иногда и удобочитаемого) способа кодирования молекулярной информации и облегчения поиска такой информации в базах данных и в Интернете.
Рекомендации
- ^ а б Арвинд, Викраман; Дас, Бирешвар; Кёблер, Йоханнес (2008), "Алгоритм логического пространства для частичной канонизации двух деревьев", Компьютерные науки - теория и приложения: Третий международный симпозиум по информатике в России, CSR 2008 Москва, Россия, 7-12 июня 2008 г., Труды , Лекция Заметки в Comput. Sci . , 5010 ., Springer, Berlin, стр 40-51, DOI : 10.1007 / 978-3-540-79709-8_8 , MR 2475148.
- ^ а б Арвинд, В .; Дас, Бирешвар; Кёблер, Йоханнес (2007), "Пространственная сложность изоморфизма k- деревьев", Алгоритмы и вычисления: 18-й Международный симпозиум, ISAAC 2007, Сендай, Япония, 17-19 декабря 2007 г., Труды , Конспекты лекций в Comput. Sci . , 4835 ., Springer, Berlin, С. 822-833, DOI : 10.1007 / 978-3-540-77120-3_71 , MR 2472661.
- ^ Гуревич, Юрий (1997), «От инвариантов к канонизации» (PDF) , Бюллетень Европейской ассоциации теоретической информатики (63): 115–119, MR 1621595.
- ^ Бабай, Ласло ; Люкс, Евгений (1983), "Каноническая маркировка графов", Proc. Пятнадцатый ACM симпозиум по теории вычислений ., Стр 171-183, DOI : 10,1145 / 800061,808746.
- ^ Бабай, Ласло (1977), О проблеме изоморфизма , неопубликованная рукопись.
- ^ Бабай, Ласло ; Кучера, Л. (1979), "Каноническая разметка графиков в линейное среднее время", Proc. Двадцатый ежегодный IEEE симпозиум по Основы информатики , 39-46,. Дои : 10,1109 / SFCS.1979.8.
- ^ Рид, Рональд С. (1972), «Кодирование различных видов немаркированных деревьев», Graph Theory and Computing , Academic Press, New York, pp. 153–182, MR 0344150.
- ^ Маккей, Брендан Д .; Пиперно, Адольфо (2014), «Журнал символьных вычислений», Практический изоморфизм графов, II , стр. 94–112, ISSN 0747-7171.
- ^ Кук, Дайан Дж .; Холдер, Лоуренс Б. (2007), «6.2.1. Каноническая маркировка», Mining Graph Data , стр. 120–122, ISBN 0-470-07303-9.
- ^ Вейнингер, Дэвид; Вейнингер, Артур; Вейнингер, Джозеф Л. (май 1989 г.). «УЛЫБКИ. 2. Алгоритм генерации уникальной нотации УЛЫБКИ». Журнал химической информации и моделирования . 29 (2): 97–101. DOI : 10.1021 / ci00062a008 .
- ^ Келли, Брайан (май 2003 г.). «Каноникализация графа» . Журнал доктора Добба .
- ^ Шайдер, Надин; Sayle, Roger A .; Ландрам, Грегори А. (октябрь 2015 г.). «Приведите свои атомы в порядок - реализация нового и надежного алгоритма молекулярной канонизации с открытым исходным кодом». Журнал химической информации и моделирования . 55 (10): 2111–2120. DOI : 10.1021 / acs.jcim.5b00543 . PMID 26441310 .