Алгоритм перевірки графів на ізомофність з використанням локальних інваріантів

Loading...
Thumbnail Image
Date
2003
Authors
Чичкань, Сергій
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Одним із способів зниження часової складності перевірних задач є впорядкування множини вхідних даних, що дає змогу ідентифікувати їх незалежно від порядку зберігання чи переліку. Для цього кожному елементу множини приписується чисельна характеристика (вага). Якщо метою перебору є встановлення еквівалентності двох множин і всім елементам множини можна приписати різну вагу, швидке сортування обох множин за час O(Nlog2N) практично розв 'язує задачу, оскільки після впорядкування залишається за час 0(N) перевірити еквівалентність упорядкованих масивів, які містять елементи множини. У цій роботі наведено алгоритм перевірки графів на ізоморфність, що базується на впорядкуванні вершинних інваріантів локального порядку.
Description
Keywords
вхідні дані, впорядкування, ізомофність, вершинний інваріант
Citation
Чичкань Сергій Михайлович. Алгоритм перевірки графів на ізомофність з використанням локальних інваріантів / С. М. Чичкань // Наукові записки НаУКМА : Комп'ютерні науки. - 2003. - Т. 21. - С. 5-10.