СПЕКТР РЕБЕРНОГО РОЗРІЗУ ГРАФА ТА ЗАДАЧА ІЗОМОРФІЗМУ

Анотація

Робота присвячена одній з основоположних структур у графі – реберному розрізу графа. У статті наведені формальні визначення центрального і реберного розрізів графа. Показано зв’язок між центральними розрізами і квалірозрiзами у графі. На основі поняття реберного розрізу і операції породження будується спектр реберних розрізів, що характеризується множиною ребер визначеного рівня. Показано, що спектр реберних розрізів графа може бути застосований для задачі розпізнавання ізоморфізму графів.