Канонизация графа
В теории графов , разделе математики, канонизация графов — это проблема нахождения канонической формы данного 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-трудным . [7]
Для деревьев краткий алгоритм полиномиальной канонизации, требующий пространства O(n), представлен Ридом (1972) . [8] Начните с маркировки каждой вершины строкой 01. Итеративно для каждого нелистового x удалите начальный 0 и конечную 1 из метки x; затем отсортируйте метку x вместе с метками всех соседних листьев в лексикографическом порядке. Объедините эти отсортированные метки, добавьте начальный 0 и конечную 1, сделайте это новой меткой x и удалите соседние листья. Если осталось две вершины, соедините их метки в лексикографическом порядке.
Приложения [ править ]
Канонизация графов является сутью многих алгоритмов изоморфизма графов. Одним из ведущих инструментов является Nauty. [9]
Распространенным применением канонизации графов является интеллектуальный анализ графических данных , в частности, приложения химических баз данных . [10]
Ряд идентификаторов химических веществ , таких как SMILES и InChI, используют этапы канонизации в своих вычислениях, что, по сути, представляет собой канонизацию графа, представляющего молекулу. [11] [12] [13] Эти идентификаторы предназначены для обеспечения стандартного (а иногда и удобочитаемого) способа кодирования молекулярной информации и облегчения поиска такой информации в базах данных и в Интернете.
Ссылки [ править ]
- ^ Арвинд, Викраман; Дас, Бирешвар; Кёблер, Йоханнес (2008), «Алгоритм логического пространства для частичной канонизации двух деревьев», Информатика – теория и приложения: Третий международный симпозиум по компьютерным наукам в России, CSR 2008 Москва, Россия, 7–12 июня 2008 г., Труды , Лекция Заметки в Comput. наук, том. 5010, Springer, Berlin, стр. 40–51, номер документа : 10.1007/978-3-540-79709-8_8 , MR 2475148 .
- ^ Jump up to: Перейти обратно: а б Арвинд, В.; Дас, Бирешвар; Кёблер, Йоханнес (2007), «Пространственная сложность изоморфизма k -дерева», Алгоритмы и вычисления: 18-й международный симпозиум, ISAAC 2007, Сендай, Япония, 17–19 декабря 2007 г., Труды , Конспекты лекций по вычислительной технике. наук, том. 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. 15-й симпозиум ACM по теории вычислений , стр. 171–183, doi : 10.1145/800061.808746 .
- ^ Бабай, Ласло (1977), О проблеме изоморфизма , неопубликованная рукопись .
- ^ Бабай, Ласло ; Кучера, Л. (1979), "Каноническая разметка графов в линейное среднее время", Proc. 20-й ежегодный симпозиум IEEE по основам информатики , стр. 39–46, doi : 10.1109/SFCS.1979.8 , S2CID 14697933 .
- ^ Бабай, Ласло ; Лукс, Э. (1983), "Каноническая разметка графов", Proc. 15-й симпозиум ACM по теории вычислений , стр. 171–183.
- ^ Рид, Рональд К. (1972), «Кодирование различных видов немаркированных деревьев», Теория графов и вычисления , Academic Press, Нью-Йорк, стр. 153–182, MR 0344150 .
- ^ Маккей, Брендан Д.; Пиперно, Адольфо (2014), «Журнал символических вычислений», Практический изоморфизм графов, II , том. 60, стр. 94–112, arXiv : 1301.1493 , doi : 10.1016/j.jsc.2013.09.003 , ISSN 0747-7171 , S2CID 17930927 .
- ^ Кук, Дайан Дж .; Холдер, Лоуренс Б. (2007), «6.2.1. Каноническая маркировка», Mining Graph Data , John Wiley & Sons, стр. 120–122, ISBN 978-0-470-07303-2 .
- ^ Вейнингер, Дэвид; Вейнингер, Артур; Вайнингер, Джозеф Л. (май 1989 г.). «УЛЫБКИ. 2. Алгоритм формирования уникальной SMILES-нотации». Журнал химической информации и моделирования . 29 (2): 97–101. дои : 10.1021/ci00062a008 . S2CID 6621315 .
- ^ Келли, Брайан (май 2003 г.). «Канонизация графа» . Журнал доктора Добба .
- ^ Шайдер, Надин; Сэйл, Роджер А.; Ландрам, Грегори А. (октябрь 2015 г.). «Приведите свои атомы в порядок — реализация с открытым исходным кодом нового и надежного алгоритма молекулярной канонизации». Журнал химической информации и моделирования . 55 (10): 2111–2120. doi : 10.1021/acs.jcim.5b00543 . ПМИД 26441310 .