Чичкань, Сергій2016-02-172016-02-172003Чичкань Сергій Михайлович. Алгоритм перевірки графів на ізомофність з використанням локальних інваріантів / С. М. Чичкань // Наукові записки НаУКМА : Комп'ютерні науки. - 2003. - Т. 21. - С. 5-10.https://ekmair.ukma.edu.ua/handle/123456789/8413Одним із способів зниження часової складності перевірних задач є впорядкування множини вхідних даних, що дає змогу ідентифікувати їх незалежно від порядку зберігання чи переліку. Для цього кожному елементу множини приписується чисельна характеристика (вага). Якщо метою перебору є встановлення еквівалентності двох множин і всім елементам множини можна приписати різну вагу, швидке сортування обох множин за час O(Nlog2N) практично розв 'язує задачу, оскільки після впорядкування залишається за час 0(N) перевірити еквівалентність упорядкованих масивів, які містять елементи множини. У цій роботі наведено алгоритм перевірки графів на ізоморфність, що базується на впорядкуванні вершинних інваріантів локального порядку.ukвхідні данівпорядкуванняізомофністьвершинний інваріантArticle