Browsing by Author "Білаль Раді А’Ґґель Аль-Забі"

Now showing 1 - 1 of 1

Нові інваріанти встановлення ізоморфізму графів
(Видавництво Національного університету "Львівська політехніка", 2008) Білаль Раді А’Ґґель Аль-Забі; Керницький, А. Б.; Лобур, М. В.; Ткаченко, С. П.
Проблеми встановлення ізоморфізму графів стосується доволі велика кількість робіт, одними з найхарактерніших є [1–4]. Низка узагальнень наводиться також у таких роботах, як [5–9]. Показано [3], що подібні задачі є комбінаторними важкорозв’язуваними задачами факторіального ступеня складності, у зв’язку з чим для їхнього розв’язання прийнятними залишаються лише евристичні прийоми [1, 10, 11]. Тому тут не будуть ефективними ні метод гілок і границь, ні методи математичногом програмування, які у кращому випадку понижують складність задачі від факторіальної залежності до показникової (відносно, як правило, кількості вершин графа), а це є неприйнятним для задач практичної розмірності. Водночас існуючі евристичні прийоми розв’язання задачі (а точніше, спроби її розв’язання) мають, як правило, часову складність O(Nc), де с=4¸6 [3, 8], що також різко обмежує розмірність задач, які розв’язуються, оскільки для розв’язання задач за прийнятний час необхідно, щоб було с≤3.