АНАЛІЗ ВПЛИВУ АВТОМОРФІЗМУ ГРАФУ НА СХЕМИ НАПРАВЛЕНОГО ПЕРЕБОРУ

K. D. Karavaiev; V. A. Turchyna

doi:10.15421/322110

K. D. Karavaiev
V. A. Turchyna

Ключові слова: дискретна оптимізація, теорія розкладів, оптимальні упорядкування, метод гілок та меж, перерахування без ізоморфізму

Анотація

У статі досліджується залежність між наявністю автоморфізму у графі та ізоморфізмом його підграфів, отриманих шляхом видаленням з нього відкритих вершин. Запропоновано алгоритм для скорочення кількості розгалужень у методі гілок та меж для задачі паралельного упорядкування вершин орграфів. Показано, що результуюча множина містить всі неізоморфні підграфи, проте також може містити й ізоморфні.